Программа экзамена по курсу «Структуры данных и их анализ»




Скачать 34.1 Kb.
Дата 16.09.2016
Размер 34.1 Kb.
Программа экзамена по курсу «Структуры данных и их анализ»
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 числа сравнений при вставке, успешном и неудачном поиске в случае линейного хеширования через коэффициент заполнения таблицы.


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница