Вопросы к зачету. Осень 2016.

1. Асимптотические обозначения (Ο, Θ, Ω). Теорема 3.1 c доказательством. Доказательство правила сумм.
2. Сортировка вставками. Доказательство корректности сортировки вставками (с помощью инварианта цикла).
3. Сортировка вставками. Точная и асимптотическая оценки времени работы сортировки вставками (с доказательством).
4. Сортировка слиянием. Анализ времени работы алгоритма сортировки слиянием.
5. Двоичная куча. Определения. Сортировка кучей. Доказательство корректности и оценка времени работы каждой из процедур Heapify, BuildHeap, HeapSort.
6. Сортировки, работающие за линейное время. Доказательство нижней оценки на время работы сортировок, основанных на сравнениях. Сортировка подсчетом, цифровая сортировка.
7. Стеки, очереди, списки (односвязные, двусвязные, циклические) и операции с ними. Очередь с приоритетами.
8. Бинарное дерево поиска. Терминология. Симметричный обход бинарного дерева поиска. Доказательство оценки времени работы. Поиск элемента по ключу.
9. Операции, выполняемые с бинарными деревьями поиска: поиск минимума и максимума, поиск предшествующего и последующего элементов (с пояснениями, почему описанные методы работают корректно).
10. Операции, выполняемые с бинарными деревьями поиска: вставка и удаление (с пояснениями, почему описанные методы работают корректно).
11. Хеш-таблицы с закрытой адресацией: вставка, поиск и удаление. Представление строковых ключей как целых неотрицательных чисел. Метод деления, метод умножения. Примеры.
12. Хеш-таблицы с открытой адресацией: вставка, поиск и удаление. Линейное исследование, квадратичное исследование, двойное хеширование (со сравнительным анализом качества хеширования в этих подходах на основе числа исследуемых последовательностей). Примеры.