Файл: Экзаменационные вопросы по курсу Структуры и алгоритмы обработки данных.pdf

Курс «Структуры и алгоритмы обработки данных», СибГУТИ. Весенний семестр, 2023 г.
1
Экзаменационные вопросы по курсу
«Структуры и алгоритмы обработки данных»
(Весенний семестр, 2023 г., 1-й курс)
1. Понятие алгоритма. Свойства алгоритмов. Показатели эффективности алгоритмов.
Анализ времени выполнения алгоритмов.
2. Асимптотический анализ вычислительной сложности алгоритмов. Анализ вычисли- тельной сложности в худшем, среднем и лучшем случаях. Асимптотические обозначе- ния O, , . Основные классы сложности алгоритмов.
Θ Ω
3. Анализ рекурсивных алгоритмов. Стек вызовов функций. Виды рекурсии. Решение ре- куррентных уравнений. Основная теорема (master method). Анализ эффективности ал- горитма сортировки слиянием.
4. Задача сортировки. Виды алгоритмов сортировки: устойчивые алгоритмы, сортировки сравнением, сортировки на месте (in-place). Сортировка вставками. Сортировка слия- нием. Быстрая сортировка. Пирамидальная сортировка. Поразрядная сортировка.
5. Поиск элемента по ключу. Линейный поиск. Бинарный поиск. Экспоненциальный по- иск (galloping search).
6. Абстрактный тип данных «список». Связный список. Односвязный список, двусвязный список. Основные операции и их вычислительная сложность.
7. Стек. Способы реализации стека. Основные операции и их вычислительная сложность.
8. Очередь. Способы реализации очереди. Основные операции и их вычислительная сложность. Реализация очереди на основе циклического массива. Двухсторонняя оче- редь (дек, deque).
9. Абстрактный тип данных «словарь». Основные операции словаря. Бинарные деревья поиска. Основные операции, их вычислительная сложность. Анализ эффективности бинарного дерева поиска в среднем и худшем случае.
10. Абстрактный тип данных «словарь». Хеш-таблицы. Основные операции хеш-таблицы.
Хеш-функции. Методы разрешения коллизий.
11. Очереди с приоритетом. Бинарные кучи. Реализация бинарной кучи на основе масси- ва. Построение бинарной кучи за время O(n).
12. Графы. Виды графов. Способы представления графов в памяти. Реализация графа на основе матрицы смежности.
13. Обход графа. Обход в глубину (DFS). Обход в ширину (BFS).
14. Задача поиска кратчайшего пути в графе. Постановки задачи о кратчайшем пути. Ал- горитмы поиска кратчайшего пути в графе. Алгоритм Дейкстры. Вычислительная сложность алгоритма Дейкстры.
15. Остовные деревья минимальной стоимости (minimum spanning tree, MST). Алгоритмы построения MST. Система непересекающихся множеств. Алгоритм Крускала. Алгоритм
Прима.
16. Основные методы разработки алгоритмов. Метод «грубой силы» (brute force). Метод декомпозиции. Алгоритмы, основанные на методе декомпозиции.
17. Методы разработки алгоритмов. Динамическое программирование. «Жадные» алго- ритмы (greedy algorithms). Код Хаффмана. Поиск с возвратом (backtracking). Задача о восьми ферзях. Задача о раскраске графа в k цветов. Локальный поиск.
18. Трудноразрешимые задачи. Классы сложности P. Класс сложности NP. Гамильтонов цикл. Задача коммивояжёра. Задача упаковки корзин. Сводимость задач. NP-полнота.