ВУЗ:
Составители:
Рубрика:
Познакомьтесь с понятиями хеширования (рассеянной памяти), хеш-функции и коллизии. Изучите два ос-
новных типа хеш-функций, один из которых основан на делении, а другой на умножении. Обратите внимание
на то, каким двум требованиям должна удовлетворять хорошая хеш-функция. Познакомьтесь с понятием раз-
решения коллизий. Рассмотрите разрешение коллизии методом цепочек, состоящее в том, чтобы поддерживать
несколько связанных списков, по одному на каждый возможный хеш-адрес. Изучите алгоритм С поиска со
вставкой по рассеянной таблице с цепочками и оцените его быстродействие. Рассмотрите другой способ реше-
ния проблемы коллизий, называемый разрешением коллизий "открытой адресацией" и состоящий в том, чтобы
полностью отказаться от ссылок и просто просматривать один за другим различные элементы таблицы, пока не
будет найден ключ или свободная позиция. Изучите алгоритм L поиска со вставкой по открытой рассеянной
таблице и познакомьтесь с результатами экспериментов с линейным опробыванием. Выполните сравнительный
анализ изученных методов поиска, чтобы руководствоваться им при выборе наилучшего метода для конкретно-
го приложения.
Вопросы для самопроверки
1. Какой смысл вкладывается в понятия поиск, ключ, таблица или файл, база данных, аргумент поиска,
удачный и неудачный поиск, поиск с вставкой?
2. Какой поиск называют внутренним и какой внешним?
3. Чем различаются статический и динамический методы поиска?
4. На каком примере можно показать существующую взаимосвязь между поиском и сортировкой?
5. Как Вы понимаете последовательный поиск?
6. Что подразумевается под удачным и неудачным исходами поиска?
7. Какой важный принцип убыстряет работу алгоритма последовательного поиска при условии, что запи-
сей не слишком мало?
8. Что понимается под последовательным поиском в упорядоченной таблице?
9. Какие алгоритмы поиска действуют быстрее в случаях удачного и неудачного поиска?
10. Что Вы понимаете под методами поиска, основанными на линейном упорядочении ключей?
11. Какова основная идея бинарного поиска?
12. Чем отличаются иллюстрации поведения алгоритма бинарного поиска в случаях, когда разыскивается
аргумент, равный имеющемуся в таблице, и когда разыскивается отсутствующий аргумент?
13. Как выглядит бинарное дерево решений алгоритма бинарного поиска?
14. В чем заключается важная модификация бинарного поиска, называемая однородным бинарным поис-
ком?
15. Как отличается быстродействие однородного бинарного поиска в сравнении с бинарным поиском?
16. Что обычно понимают под фибоначчиевым поиском?
17. Какова оценка быстродействия фибоначчиева поиска?
18. Для каких таблиц предназначены, главным образом, методы бинарного, однородного бинарного и фи-
боначчиева поиска?
19. Использование какой структуры данных позволяет осуществить эффективный поиск по динамически
изменяемой таблице?
20. В чем заключается основная идея поиска со вставкой по дереву?
21. Какова эффективность алгоритма поиска со вставкой по дереву в сравнении с алгоритмами бинарного
поиска?
22. Какое дерево является наилучшим для поиска по таблице, если ключи запрашиваются с данными час-
тотами?
23. По какому алгоритму можно найти оптимальное бинарное дерево поиска?
24. Что обычно понимают под высотой дерева, сбалансированным деревом и показателем сбалансирован-
ности?
25. Насколько далеко сбалансированное дерево отклоняется от оптимального?
26. Как работает алгоритм А поиска со вставкой по сбалансированному дереву, и каково его быстродейст-
вие?
27. Какой смысл вкладывают в понятия хеширования (рассеянной памяти), хеш-функции и коллизии?
28. На каких операциях основаны два основных типа хеш-функций?
29. Каким требованиям должна удовлетворять хорошая хеш-функция?
30. Что обычно понимают под разрешением коллизий?
31. В чем заключается разрешение коллизии методом цепочек?
32. Как работает алгоритм С поиска со вставкой по рассеянной таблице с цепочками, и каково его быстро-
действие?
33. В чем состоит способ решения проблемы коллизий, называемый разрешением коллизий "открытой ад-
ресацией"?
34. Какие результаты дают эксперименты с линейным опробыванием для алгоритма L поиска со вставкой
по открытой рассеянной таблице?
35. Что Вы можете сказать о сравнительном анализе изученных методов поиска, чтобы руководствоваться
им при выборе наилучшего метода для конкретного приложения?
Литература: [3, c. 464–650], [4, с. 53–69].
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
