1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 38
Текст из файла (страница 38)
4.1, достаточное для упорядочения любой последовательности из п элементов. Что можно сказать о сложности выполнения потока из п операций, выбранных из вашего подмножества? 4.2. Пусть элементами являются цепочки из букв и используется следующая функция расстановки для таблиць1 размера т=б: сложить "значения" букв, где А имеет значение 1,  — значение 2 и т. д.; разделить результат иа 5 и взять остаток.
Выпишите содержимое таблицы расстановки и списков, при условии что вставляются цепочки ОАЗНЕК, ОАМСЕК, РКАНСЕК, У1ХЕН, СОМЕТ, СОР1Р, ОСИЕК, В(.1ТХЕК. 4.3. Вставьте восемь цепочек из упр. 4.2 в дерево двоичного поиска. Какую последовательность узлов надо посетить, чтобы проверить, принадлежит ли КБЭО).РН этому множеству? 4.4. Покажите, что процедура ПОИСК (рис. 4.3) дает наименьшее возможное среднее время поиска, если все элементы универсального множества разыскиваются с равной вероятностью. 4.5. Найдите оптимальное дерево двоичного поиска для а, 5, ...,А, если эти элементы имеют вероятности соответственно О,1; 0,2; 0,05; 0,1; 0,3; 0,05; 0,15; 0,05, а вероятность всех остальных равна О. **4.6. Покажите, что в алгоритме 4.2 можно ограничить поиск числа т в строке 8 иа рис.
4.9 областью позиций от г, з, до гг„; и все равно с гарантией находить максимум. *4.7. Используйте упр. 4.6 для такого изменения алгоритма 4.2, чтобы он работал время 0(п'). 4.8. Закончите доказательство теоремы 4.2, показав, что алгоритм построения дерева на рис. 4.10 работает правильно. 4.9. Закончите доказательство теоремы 4.3. *4,10. Постройте интерфейс для перевода множества и внешних имен, лежащих между 1 и г, в множество внутренних имен, состоящее из целых чисел от 1 до и. Этот интерфейс должен переводить в обе стороны в предположении, что г~~п. (а) Разработайте интерфейс с хорошим поведением в среднем.
(б) Разработайте интерфейс с хорошим поведением в худшем случае. ВВЕ гл, к стггктггы длнных для задач с множвствхми *4.1!. Найдите эффективную структуру данных для представления подмножества 5 целых чисел, лежащих между 1 и п. Мы хотим выполнять на множестве следующие операции: 1) выбирать и удалять из него какой-то один его элемент, 2) добавлять в него целое число 1. Предполагается, что механизм не должен добавлять в 5 целое число Ь если оио уже есть там.
Структура данных должна быть такой, чтобы время на выборку и удаление элемента и время на добавление элемента не зависели от !Щ. 4.12. Найдите дерево, которое получается, когда алгоритм 4.3 выполняет последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, порождаемую следующей программой. Допустим, что множество ! вначале есть (1) для 1(1(16. Ьен!п 1ог ! -1 з(ер 2 пп111 15 до ОБЪЕДИНИТЬ(1,1+1,1); 1ог 1 1 э1ер 4 пп6! 13 до ОБЪЕДИНИТЬ(1, !+2, 1); ОБЪЕДИНИТЬ (1, б, 1); ОБЪЕДИНИТЬ(9, 13, 9); ОБЪЕДИНИТЬ (1, 9, 1); 1ог 1 — 1 з1ер 4 пп111 13 до НАЙТИ(!) епд 4.13.
Пусть о — последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, причем все операции ОБЪЕДИНИТЬ входят в о перед операциями НАЙТИ. Докажите, что алгоритм 4.3 выполняет о за время, пропорциональное )о!. 4.!4. 5,-деревом назовем дерево, состоящее из единственного узла. 5пдерево для 1)0 получается операцией, которая делает корень одного 5,,-дерева сыном корня другого 5;,-дерева.
До- кажите, что (а) 5„-дерево имеет („") узлов высоты й, (б) 5„-дерево можно получить из 5„-дерева, т(п, заменив каждый узел 5„-дерева на 5„„-дерево так, что сыновья этого узла становятся сыновьями корня подставляемого 5 „„-дерева, (в) 5„-дерево содержит узел с а сыновьями; они служат корнями 5гь 5 -, ..., 5„,-деревьев. 4.13. Рассмотрим алгоритм объединения непересекающихся множеств, который делает корень дерева с меньшим числом узлов (в случае одинакового количества узлов выбор дерева произволен) УПРАЖНЕНИЯ сыном корня большего дерева, ио не использует сжатие путей. Докажите, что верхнюю границу О (и !од и) нельзя улучшить.
Инымн словами покажите, что для некоторой постоянной с и произвольно больших значений и существуют последовательности операций ОБЪЕДИНИТЬ и НАЙТИ, требующие сп !ори шагов. Я*4.16. Пусть Т(п) — временная сложность (в худшем случае) выполнения а операций ОБЪЕДИНИТЬ и НАЙТИ при условии, что применяется древовидная структура из разд. 4.7 и сжатие путей для операций НАЙТИ, но операция ОБЪЕДИНИТЬ(А, В, С) выполняется так: корень дерева А становится сыном корня дерева В независимо от того, какое множество больше, Покажите, что Т(п))й,п 1ояп для некоторой постоянной й,= О.
**4.17. Покажите, что Т(п)(й,а !опп для некоторой постоянной йм где Т (п) обозначает то же, что и в упр. 4.16. *Я4.18. Покажите, как можно выполнить последовательность из п операций ОБЪЕДИНИТЬ, НАЙТИ, ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ на множестве целых чисел 1, 2,..., и за время О (пб(п)).
При этом считайте, что УДАЛИТЬ(1, 5) делает ! членом нового множества и, которому надо присвоить (произвольное) имя. Это множество можно впоследствии слить с другим. Кроме того, предположите, что никакой элемент не принадлежит более чем одному множа~ ву. 4.19. Обобщите М1Х-задачу для свободного режима так, чтобы можно было выполнять операцию М1Х вида М1Х(1), которая находит все целые числа, меньшие 1, вставленные до нее и еще ие найдезные предыдущей операцией М1Х.
4.20. Разработайте полную структуру данных для М!Х-задачи в свободном режиме, включающую представление деревьев массивами, и напишите программу, в которой употребляются массивы, а не команды высокого уровня, используемые алгоритмом объединения непересекающихся множеств. 4.21. Обобщите М1Х-задачу для свободного режима следующим образом. Пусть Т вЂ” дерево с п узлами. Каждому узлу ставится в соответствие целое число от 1 до и. Некоторым узлам приписаны операции ИЗВЛЕЧЬ М1Х. Пройдите дерево в обратном порядке.
Встретив операцию ИЗВЛЕЧЬ М1Х в узле и, найдите в дереве с корнем о наименьшее целое число (исключая число в самом узле о) среди тех чисел, которые не были удалены раисе, и удалите его. Укажите алгоритм для этого процесса, работающий в свободном режиме и имеющий сложность 0(пб(п)). *э4.22. Разработайте алгоритм сложности О (и !он !они) для задачи ОБЪЕДИНИТЬ вЂ” НАЙТИ, пользуясь структурой данных, со- !и гл, и стииктииы дхииых для зхдхч с множествами стоящей из дерева, каждый лист которого отстоит от корня на расстояние 2. Ограничьте степень корня числом между 1 и лЛойп, а степень каждого его сына — числом между 1 и !оип.
Как модифицировать этот алгоритм, чтобы он делал не более 0 (п !оп !оя !оя л) шагов? Какую наилучшую границу на время можете вы получить, обобщая этот метод? 4.23. Покажите, как можно хранить в таблице символов смещения от начала отсчета, упомянутые в приложении 2 равд. 4,8, Указание: Примените технику, использованную для определения глубины. 4.24. Напишите программу для операций ОБЪЕДИНИТЬ и НАЙТИ, осуществляющую вычисления с весом, как в приложении 2 разд. 4.8. 4.25.
С помощью алгоритма на рис. 4.25 выясните эквивалентность конечных автоматов Вход О 1 Вход О 1 Теснее сссоголиие Тск1атис С иитаюиии Пииддюиссс состиинии Сседрж~ви соаюоииие Начальными состояниями являются 1 и А соответственно, а мно- жествами заключительных состояний — множества Щ и (С, Е) соответственно. 4.26. Напишите полные программы для выполнения операций на 2-3-деревьях: (а) УДАЛИТЬ, (б) ОБЪЕДИНИТЬ, (в) ПРИНАДЛЕЖАТЬ (в предположении, что множество листьев упорядочено и каждый узел помечен номером самого высокого листа среди всех листьев, с которыми он соединен), (г) РАСЦЕПИТЬ (в предположении, что задан лист, по которому производится расцепление, и множество листьев упорядочено). УПРАЖНЕНИЯ 4.27. Напишите полную программу для вставки нового узла в 2-3-дерево, предполагая, что множество листьев упорядочено. 4.28.
Напишите программы для основных операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ, МЩ ОБЪЕДИНИТЬ и НАЙТИ, используя 2-3-деревья с метками НАИМЕНЬШИЙ нз равд. 4.11. Универсальным множеством считайте (1, 2, „и). 4.29. Рассмотрите реализацию сливаемого дерева в виде 2-3- дерева (ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, М!И). Считайте при этом, что универсум, из которого берутся элементы, велик. Опишите, как реализовать НАЙТИ за 0(1оя л) шагов на одну операцию, где а — общее число элементов во всех соединяемых деревьях.
Определение, АВЛ-деревом ') называют такое дерево двоичного поиска, что для каждого узла о высоты его левого и правого поддеревьев отличаются не более чем на единицу. Если какого-то поддерева нет, его "высота" считается равной — 1. Пример 4.14, Дерево на рис. 4.37 не является АВЛ-деревом, потому что высота левого поддерева узла в равна 2, а правого — О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
