Программа экзамена по курсу «Структуры данных и их анализ»
1. Структуры данных. Понятия структуры данных, элемента структуры, ключа, линейно упорядоченной структуры. Основные операции над структурами. Анализ времени выполнения операций и числа осуществляемых сравнений.
2. Связные списки. Понятия однократно и двукратно связанного линейного списка, отсортированного списка. Алгоритмы выполнения операций над списками и их оптимизация. Оценки времени выполнения и числа сравнений для операций над списками.
3. Списки с различной вероятностью доступа к элементам. Оценка m числа сравнений при успешном поиске в случае, когда известны вероятности запроса каждого элемента, и для самоорганизующегося списка. Связь между ними.
4. Прямая и хэш-адресация. Понятия таблицы с прямой адресацией и хэш-таблицы. Хэш-функции. Проблема разрешения коллизий.
5. Хэш-функции. Методы деления и умножения и их реализация. Условие простого равномерного хеширования. Оптимизация методов в случае, когда не все наборы хранимых значений ключей равновероятны.
6. Универсальные множества хэш-функций. Понятие универсального множества хэш-функций. Пример универсального множества хэш-функций.
7. Разрешение коллизий методом цепочек. Идея метода разрешения коллизий методом цепочек. Оценки времени выполнения и числа сравнений для всех операций при условии, что хэш-функция удовлетворяет условию простого равномерного хеширования или выбирается из универсального множества хэш-функций.
8. Разрешение коллизий методом открытой адресации. Идея метода разрешения методом открытой адресации. Алгоритмы вставки и поиска. Возможные алгоритмы удаления. Оценки времени выполнения и числа сравнений для всех несловарных операций.
9. Равномерное хеширование с открытой адресацией. Понятие равномерного хеширования с открытой адресацией. Оценки m числа сравнений при вставке, успешном и неудачном поиске в случае равномерного хеширования.
10. Линейное хеширования с открытой адресацией. Понятие линейного хеширования с открытой адресацией. Оценки m числа сравнений при вставке, успешном и неудачном поиске в случае линейного хеширования.
Вопросы к экзамену по курсу «Структуры данных и их анализ»
1. Понятия однократно и двукратно связанного линейного списка, отсортированного списка. Оценки времени выполнения и числа сравнений для словарных операций над списками.
2. Оценка m числа сравнений при успешном поиске в случае, когда известны вероятности запроса каждого элемента. Пример с распределением Зипфа.
3. Оценка m числа сравнений при успешном поиске в случае самоорганизующегося списка. Леммы 1 и 2.
4. Оценка m числа сравнений при успешном поиске в случае самоорганизующегося списка. Леммы 3, 4, 5.
5. Оценка m числа сравнений при успешном поиске в случае самоорганизующегося списка. Формулировки лемм и доказательство предложения.
6. Оценка m числа сравнений при успешном поиске в случае самоорганизующегося списка. Пример с распределением Зипфа и связь с m числом сравнений при успешном поиске в случае, когда известны вероятности запроса каждого элемента.
7. Методы деления и умножения и их реализация. Оптимизация методов в случае, когда не все наборы хранимых значений ключей равновероятны.
8. Условие простого равномерного хеширования и соответствие ему методов деления и умножения.
9. Понятие универсального множества хэш-функций. Пример универсального множества хэш-функций.
10. Идея метода разрешения коллизий методом цепочек. Оценки времени выполнения и числа сравнений для всех операций при условии, что хэш-функция удовлетворяет условию простого равномерного хеширования
11. Оценки времени выполнения и числа сравнений для всех словарных операций при условии, что используется разрешение коллизий методом цепочек и хэш-функция выбирается из универсального множества хэш-функций.
12. Идея метода разрешения методом открытой адресации. Алгоритмы вставки и поиска. Возможные алгоритмы удаления. Оценки времени выполнения и числа сравнений для всех несловарных операций.
13. Оценка m числа сравнений при вставке и неудачном поиске в случае равномерного хеширования. Леммы 1 и 2.
14. Оценка m числа сравнений при вставке и неудачном поиске в случае равномерного хеширования. Лемма 3 и доказательство предложения.
15. Оценка m числа сравнений при успешном поиске в случае равномерного хеширования.
16. Оценка m числа сравнений при вставке и неудачном поиске в случае линейного хеширования. Леммы 1–4.
17. Оценка m числа сравнений при вставке и неудачном поиске в случае линейного хеширования. Леммы 5, 6.
18. Оценка m числа сравнений при вставке и неудачном поиске в случае линейного хеширования. Леммы 7, 8 и доказательство предложения.
19. Оценка m числа сравнений при успешном поиске в случае линейного хеширования.
20. Оценка m числа сравнений при вставке, успешном и неудачном поиске в случае линейного хеширования через коэффициент заполнения таблицы.
|