Список вопросов по дисциплине «Структуры и алгоритмы обработки данных»

1. Понятия физической и логической, простой и интегрированной структур данных. Классификация структур: статические, динамические, связные и несвязные.

2. Тип «указатель» и ситуации его применения. Физическая структура указателя. Представление указателей в языке Паскаль. Операции над указателями.

3. Назначение хеширования данных. Открытое хеширование. Привести пример организации данных. Закрытое хеширование. Привести пример организации данных.

4. Понятие коллизий при закрытом хешировании. Способы разрешения коллизий в случае закрытого хеширования.

5. Абстрактный тип данных «список». Реализация списков с помощью указателей. Реализовать операцию вставки элемента в середину списка.

6. Абстрактный тип данных «очередь». Реализация очереди с помощью указателей. Операторы.

7. Абстрактный тип данных «стек». Реализация стека с помощью указателей. Операторы.

8. Особенности итерационного и рекурсивного вычислительных процессов. Структура итерационного процесса. Привести пример использования рекурсии и стека.

9. Различные формы представления выражений: постфиксная, префиксная, инфиксная. Использование стека операций для перевода выражений в обратную польскую запись. Привести алгоритм.

10. Абстрактный тип данных дерево. Способы изображения структуры дерева. Терминология дерева и отношения между его узлами. Понятие пути между узлами, длина пути.

11. Абстрактный тип данных дерево. Понятие обхода дерева. Привести пример рекурсивного определения прямого обхода бинарного дерева.

12. Абстрактный тип данных дерево. Понятие обхода дерева. Привести пример рекурсивного определения симметричного обхода бинарного дерева.

13. Абстрактный тип данных дерево. Понятие обхода дерева. Привести пример рекурсивного определения обратного обхода бинарного дерева.

14. Абстрактный тип данных дерево. Реализация бинарных деревьев с помощью указателей. Привести основные операторы, выполняемые над деревом.

15. Определение симметрично прошитого бинарного дерева. Привести пример построения дерева. Преимущества и недостатки прошивки.

16. Определение прямо прошитого бинарного дерева. Привести пример построения дерева. Преимущества и недостатки прошивки.

17. Метод сжатия данных кодами Хаффмана. Этапы построения дерева Хаффмана для заданных сообщений. Используемые структуры данных.

18. Определение идеально сбалансированного бинарного дерева. Алгоритм построения дерева. Преимущества и недостатки выполнения операций на таком дереве.

19. Абстрактный тип данных дерево. Построение бинарного дерева поиска. Реализация операций вставки и удаления узлов из дерева поиска.

20. Определение сбалансированного бинарного дерева. Алгоритм построения дерева. Сравнить сбалансированное и идеально сбалансированное бинарные деревья.

21. Определение бинарного АVL-дерева. Построение дерева. Реализация вставки и удаления узлов из АVL-дерева.

22. Определение ориентированного графа. Понятие вершины, дуги, пути, цикла. Помеченный орграф. Структуры данных для представления орграфов.

23. Метод нахождения кратчайшего пути на орграфе с помощью алгоритма Дейкстры. Используемые структуры данных.

24. Метод нахождения кратчайших путей на орграфе между парами вершин с помощью алгоритма Флойда. Используемые структуры данных.

25. Метод нахождения центра орграфа. Обход орграфа поиском в глубину.

26. Модель вычислений, использующих внешнюю память. Ускорение операций с файлами. Хешированные файлы.

27. Модель вычислений, использующих внешнюю память. Ускорение операций с файлами. Индексированные файлы.

28. Внешние деревья. Построение В-дерева. Поиск записей в В-дереве.

29. Внешние деревья. Вставка записей в В-дерево.

30. Внешние деревья. Удаление записей из В-дерева.