AOP_Tom3 (1021738), страница 159
Текст из файла (страница 159)
14. (2з) (Э. В. Элькок (Е. Ъ'. Е1сосА).) Покажите, что большая хеш-таблица может Разделять иамлшь с другими связанными списками. Пусть каждое слово области списка имеет;шухбитовое поле ТАС и два ссылочных поля (ЫКК и АОХ), имеющих следующий смысл ТАС(Р) = О указывает на слово в списке свободного пространства, 11ЯК(Р) указывает на следующий элемент в списке, а АОХ(Р) не используется. ТАС(Р) = 1 указывает на используемое слово, где Р ие является хеш-адресом никакого ключа из хеш-таблицы; другие поля слова в позиции Р могут иметь любой формат.
ТАС(Р) = 2 указывает, что Р представляет собой хеш-адрес, по меньшей мере, одного ключа, АОХ(Р) указывает на связанный список, .определяемый всеми такими ключами, а Ь1КК(Р) указывает на другое слово в памяти списка. При каждом обращении к слову с ТАС(Р) = 2 во время обработки любого списка мы присваиваем Р э- 11уь(р) несколько раз до достижения слова с ТАО(Р) < 1.
(Для эффективности можно также изиенить предшествующие ссылки так, что не нужно будет пропускать одни и те же элементы снова и снова,) Определите подходящий алгоритм зля вставки и получения ключей из такой хеш-таблицы. 16. [10) Почему в алгоритмах Е и П стоит сообщать о переполнении при Ту = М вЂ” 1, а не приМ = М? 16. [10] В программе Ь говорится, что К не должно быть нулеи. А вдруг на саном деле она работает лри К = О? 17. [15[ Почему бы просто ие определить!лэ(К) =?л1 (К) в (25) при йл(К) ф О? ь 18. [61) с1то лучше использовать для замены строк 10-13 программы П вЂ” (31) или (ЗО)? Дайте ответ на основании средних значений И, 51 и С.
19. [40[ Проверьте эмпирически воздействие ограничения области значений йэ(К) в алгоритме П., так что: (а) 1 < йо(К) < г при г = 1,2,3,..., 10; (Ь) 1 < йэ(Л) < рМ прн 2 о 1о 1о .»о 20. [Мйб) (Р. Кругар (В.. Кгвгаг).) Измените алгоритм П следующим образом для удаления хеш-функцни?лэ(К): на шаге РЗ установите с в — О, а в начале шага П4 установите с в- с+ 1.
Докажите, что, если М = 2, соответствующая посзедовательность проб йл(К), (йл(К) — 1) шов) М, ..., (Ал(К) — ( )) лпог1 М будет перестановкой [О, 1,, М вЂ” 1). Еглн такой метод 'квадратичных проб" запрограммировать для компьютера 611, как будет выглядеть полученная программа по сравнению с программами, показанными на рис 42, в предположении, что алгоритм ведет себя, как при случайном опробовании с вторичной кластеризацией? ь 21. [20) Предположим, что необходимо удюлить запись из таблицы, построенной согласно алгоритму П, помечая ее как удаленную.
как было предложено в тексте. Следует ли при этом уменьшать значение переменной Х, используеиой для управления алгоритмом 17? 22. [27) Докажите, что алгоритм Н оставляет таблицу в таком виде, как будто ьйТЫ никогда не был вставлен. ь 23. [33) Разработайте алгоритм, аналогичный алгоритму К, для удаления элементоа из хеш-таблицы с цепочками, построенной пи алгоритиу С.
24. [МЯ0[ Предположим, что множество всех возможных ключей имеет МР элементов, из которых ровно Р ииеют некоторый данный хеш-адрес. (На практике Р очень велико; например, если ключи представляют собой произвольные десятиэначные числа и если М = 10э, то Р = 10~,) Положим М > 7 и Х = 7. Если из множества всех возможных ключей выбраны семь различных, то чему будет равна точная вероятность того, что будет получена хеш-последовательность 1 2 6 2 1 6 1 (т. е.
6(Кл) = 1, й(Кэ) = 2,..., 6(Кэ) = 1)? Выразите ответ в виде функции от М и Р. 25. [М10) Объясните, почему верна фориула (39). 26. [М20[ Чему равно количество хеш-последовательностей ал аэ.,ао, дающих при использовании линейного исследования картину занятых ячеек, приведенную в (21)? 27. [МЯ7) Завершите доказательство теоремы К, (Укаэание.
Пусть в(п,х, у) = ~~[ (х + й) (у — а) ' (у — п); для доказательства того, что в(л,х,у) = х(х + у)' + пв(п — 1, х+1, у — 1), используйте биномиальную теорему Абеля (1.2,6 — (16)).) 28. (МЗО) "В те времена укромные, теперь почти былинные*", когда компьютеры были очень медлительными, по скорости мигания лампочек на панели можно было увидеть, насколько быстро работает алгоритм Е.
Когда таблица заполнялась почти до конца, можно было заметить, что одни данные обрабатывались очень быстро, а другие — очень медленно. Эти наблюдения наталкивают на мысзль о большолл значении стандартного отклонония колнчества проб в случае неудачного поиска при использовании линейного нсщледоввння, Найдите формулу, выражаюп1ую дисперсию через функции 4„1, из теоремы К, и оцените ге значение при 31 = пМ и ЛХ -+ щл 29. (М91) (Задача о иаркоеке.) Предположим, существует некоторая улица с одностороннилл движением, имеющая т мест для парковки, пронумерованных от 1 до т В автомобиле рядом с водителем дремлет его жена, которая вдруг просыпаетсн и требует немедленно остановиться.
Муж послушно выполняет требование жены и останавливается ва первом свободном месте для парковки. Однако, если "нет нигде стоянки, Брайтон весь забит", т. е. впереди нет ни одного свободного места (жена проснулась в тот момент, когда автомобиль проезжал й-е место парковки, а все места й, й+ 1,..., т были заняты), законопослушность водителя перевешивает послушность жене и он, принеся свои извинения, едет дальше Предположим, что на одной улице оказалось и автомобилей с дремлюгдими женами, причем 1-я жена (имеется в виду, конечно же, жена 1ьго водителя - . Прим.
иерее.) просыпается напротив а,-го места парковки. Сказько последовательностей а;... а„позволят всем автомобилям успешно припарковаться, ешли продположитгв что первоначально улица была пуста и что ни один из припарковавшихся автомобилей не уехал. Например, при т = и = 9 и ал... ае = 3 1 4 1 5 9 2 6 5 автомобили будут припаркованы следующим образом. Г" ~2 ~ С~ 4л р ~~Т~-З С.~ З~"-3 Г~ 5л '-1 ~ 7~ 1 ~~ Г~-З ~'Д~ -З ~ Я ) 1Указание. Воспользуйтесь анализом линейного исследования.) 30. (МУВ) Покажите, что в задаче о парковке из упр. 29 при и = т все машины припарковываются тогда и только тогда, когда существует перестановка р~ рз...р„множества (1, 2,..., и), такая, что а„( р, для всех 1. 31.
(М491 При и = т в упр. 29 количество решений равно (и+ 1)" '. а из упр. 2.3.4 4 — 22 известно, что зто — число свободных деревьев на и + 1 помеченной вершина! Найдите нпгересную связь между последовательностью парковок и деревьями. 32. (М27) Докажите, что система уравнений (44) имеет единственное решение, (се, сп..., слг-~). при любых целых неотрицательных бо,бл,,бм и сумма которых л~еньше Лй 1лазработайте алгоритм для поиска етого решения.
ь ЗЗ. [Мйу) Объясните, почему (51) представляет собой только оценку истинного среднего количества проб, выполняемых алгоритмом П Что именно при выводе (51) привело к тому, что формула не абсолютно точна? ь 34. (МЯЛ) Назначение етого упражнения заключаотся в исследовании греднего количества проб в хеш-таблипе с цепочками, когда списки остаются раздельными, как на рнс. 38. а) Чему равна Рлчо вероятность того, что данный список имеет длину 1с, если все М хе (35) равновероятны? Ь) Найдите производящуло функцию Р„(д) = 2 ле Рдлдл.
с) Выразите среднее количество проб для успешного поиска через эту производящую функцию. * Цитаты нз произведений В. Высоцкого н В. Токарева. присутствующие в переводе данного н следующего унражненнй, в оригинальном издании, конечно же, отсутствуют. — Прим. нерее. г1) Выведите среднее количество проб в случае неудачного поиска, рассматривая варианты структур данных, в которых используются следующие соглашения; (1) хеш-адрес указывает заголовок списка (см. рнс.
38); (и) хеш-адрес указывает позицию в таблице (гм. рис. 40), но все ключи, кроме первого в списке, попадают в отдельную область перополнения, (ш) хеш-адрес указывает позицию в таблице, и все элементы находятся в хеш-таблице. Зб. (МЯ4) Продолжая унр. 34, найдите, чему равно среднее число проб прн неудачном поиске, когда отдельные списки упорядочены по значениям ключей' Рассмотрите структуры данных (1), (й) н (1п). 36. (ЛХЯЯ) Продолжая упр.
34,(д), найдите дисперсию числа проб при неудачном поиске с использованием структур данных (1) и (В). ь 37. (МЯЯ) Формула (19) дает сродное количество проб в случае успешного поиска по раздельным цепочкам. Чему равна дисперги.х полученного числа проот 38. (МЯЯ) (Хеигироеаиие с использованием деревьев.) Способный программист может попытаться использовать вместо линейных списков бинарные деревья поиска в методе цепочек, тем самым комбинируя ап оритм 6.2 2Т с хешированием Проанализируйте среднее число проб, которые требуются для такого комбинированного алгоритма как в случае успешного. так и в случае неуда шаго поиска. (Указание, См 5.2.1-(15).) 39.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
