ВОПРОСЫ К ЭКЗАМЕНУ

1.      Последовательный поиск в массивах. Варианты усовершенствования (метод барьера, двойное продвижение).

2.      Последовательный поиск в списках. Самоорганизующиеся списки. Слоеные списки.

3.      Индексно-последовательный поиск.

4.      Двоичный поиск в массиве.

5.      Интерполяционный поиск в массиве.

6.      Поиск в двоичных деревьях.

7.      Оптимальные деревья двоичного поиска.

8.      Деревья, сбалансированные по высоте.

9.      Деревья, сбалансированные по весу.

10. Сбалансированные сильноветвящиеся деревья (m-арные).

11. Цифровой поиск.

12. Хеширование. Исключение коллизий методом цепочек.

13. Хеширование. Исключение коллизий методом открытой адресации.

14. Идеальное хеширование.

15. Алгоритм поиска подстрок Бойера-Мура.

16. Алгоритм поиска подстрок Рабина-Карпа.

17. Алгоритм поиска подстрок Кнута-Мориса-Пратта.

18. Алгоритмы подсчета числа единиц в двоичном наборе.

19. Генерация перестановок (лексикографический порядок, векторы инверсий, транспозиция смежных элементов, случайные перестановки).

20. Порождение подмножеств множества.

21. Коды Грея.

22. Алгоритм порождения сочетаний в лексикографическом порядке.

23. Решение задачи коммивояжера, задачи о рюкзаке и задачи о назначениях исчерпывающим перебором.

24. Алгоритм поиска с возвратом (решение задачи о расстановке n ферзей и задачи коммивояжера).

25. Метод ветвей и границ (решение задачи о назначениях, задачи о рюкзаке и задачи коммивояжера).

Примечание. При изложении ответа на вопрос необходимо привести оценку временной и емкостной сложности алгоритма, а также конкретные примеры с числовыми данными.