Экзаменационные вопросы по Алгоритмам и структурам данных

Экзаменационные вопросы по Алгоритмам и структурам данных

1. Понятие типов и структур данных. Оперативные и внешние структуры.

2. Стандартные и пользовательские типы данных.

3. Определение и представление структур данных.

4. Классификация структур данных. Векторы и массивы как статистические структуры.

5. Записи и таблицы как статические структуры.

6. Понятие списковой структуры. Стек как полустатическая структура. Операция над стеками

7. Очередь как полустатическая структура. Операции над очередью.

8. Недостатки полустатической очереди, методы их исправления. Очередь со сдвигом.

9. Кольцевая полустатическая очередь. Операции над кольцевой очередью. Деки, операции над ними.

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

11. Реализация стеков с помощью списков.

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

13. Очередь и операции над ней при реализации связными списками

14. Операции вставки и извлечения элементов из списка. Сравнение этих операций с аналогичными в массивах. Недостаток связного списка по сравнению с массивом.

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

16. Пример алгоритма решения задачи вставки заданного элемента в упорядоченный список.

17. Элементы заголовков в списках; нелинейные связные структуры.

18. Понятие рекурсивных структур данных. Деревья, их признаки и представления.

19. Алгоритм сведения m-арного дерева к бинарному; основные операции над деревьями; виды обхода.

20. Алгоритм создания дерева бинарного поиска.

------------------------------------------------------------------------------------------------

21. Нерекурсивный алгоритм обхода бинарного дерева.

22. Рекурсивные алгоритмы обхода (прохождения) бинарных деревьев.

23. Пояснение рекурсии обхода.

24. Понятие поиска и ключей; назначение и структуры алгоритмов поиска.

25. Последовательный поиск и его эффективность.

26. Индексно-последовательный поиск.

27. Оптимизация поиска. Переупорядочивание таблицы с учетом вероятности поиска элемента. Дерево оптимального поиска.

28. Метод оптимизации поиска путем перестановки в начало списка.

29. Метод транспозиции при оптимизации поиска.

30. Бинарный поиск.

31. Поиск по бинарному дереву. Эффективность поиска по бинарному дереву.

32. Поиск по бинарному дереву с включением.

33. Поиск по бинарному дереву с удалением.

34. Понятие сортировки, ее эффективность; классификация методов сортировки.

35. Сортировка методом прямого выбора.

36. Сортировка методом прямого включения.

37. Сортировка методом прямого обмена.

38. Быстрая сортировка.

39. Сортировка Шелла.

40. Сортировка с помощью бинарного дерева.

---------------------------------------------------------------------------------------------