Список вопросов к экзамену по предмету
«Структуры и алгоритмы обработки данных»
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. Иерархические структуры данных. Прошитое дерево. Представление в памяти. Сбалансированные по высоте (AVL) деревья поиска. Сильноветвящиеся деревья.
26. Обходы двоичного дерева.
27. Сортировка с прохождением бинарного дерева.
28. Сортировка методом турнира с выбыванием.
29. Применение бинарных деревьев для сжатия информации.
30. Представление выражений с помощью бинарных деревьев.
31. Хеширование данных. Хеш-функции. Хеш-таблицы. Представление в памяти.
32. Методы разрешения коллизий.
33. Рехеширование. Инвертированные индексы. Битовые карты.
34. Структуры данных для представления графов. Алгоритм определения наличия циклов в графе.
35. Обход графа в глубину.
36. Обход графа в ширину.
37. Поиск минимального остовного дерева (Дейктры-Прима).
38. Поиск минимального остовного дерева (Крускала).
39. Поиск кратчайшего пути (Дейкстры).
40. Топологическая сортировка.
41. Метод ветвей и границ.
42. Метод перебора с возвратом (расстановка 8 ферзей).
43. Понятие NP-задачи. Метод сведения одной задачи к другой. Применение «жадных алгоритмов» к решению задачи о коммивояжере.
44. NP-полные задачи. Задачи оптимизации и принятия решения. Применение «жадных алгоритмов» к решению задачи раскладки по ящикам.
45. Применение «жадных алгоритмов» к решению задач об упаковке рюкзака и о раскраске графа.
46. Вычислительные вероятностные алгоритмы.
47. Алгоритмы Монте-Карло.
48. Алгоритмы Лас-Вегаса.
49. Шервурдские алгоритмы.
50. Динамическое программирование. Принцип оптимальности. Динамическое программирование на основе массивов.
