Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Стандартная библиотека шаблонов STL

Вопросы к экзамену по дисциплине

Структуры и алгоритмы обработки данных

Курс, 5 семестр, 2014г.

Очное отделение

 

Структуры данных

1. Понятие абстрактного типа данных (АТД).

2. Линейные структуры данных. Области применения.

3. Абстрактный список. Определение, свойства, операции.

4. Реализация списков в виде массива и на основе указателей.

5. Работа со связанными списками: вывод на экран, удаление и вставка узла.

6. Абстрактный стек. Определение, свойства, операции.

7. Реализация стека с помощью массива и односвязного списка.

8. Абстрактная очередь. Определение, свойства, операции.

9. Нелинейные структуры данных. Области применения.

10. Деревья. Рекурсивное определение. Основные понятия.

11. Области применения деревьев.

12. Обход дерева: прямой, обратный, симметричный.

13. Операторы работы с деревьями.

14. Абстрактное бинарное дерево. Определение, свойства, операции.

15. Полное, совершенное и сбалансированное бинарные деревья.

16. АВЛ — деревья.

17. Реализация бинарного дерева в виде массива и с помощью указателей.

18. Двоичное дерево поиска.

19. Ориентированный граф. Основные понятия и терминология. Операторы работы с орографом.

20. Реализация ориентированного графа с помощью матрицы смежности и списков смежности.

21. Неориентированный граф. Основные понятия и терминология. Неориентированный граф и операторы работы с ним.

22. Реализация неориентированного графа с помощью матрицы смежности и списков смежности.

23. Графы как абстрактные типы данных.

24. Области применения графов.

25. Задача о «Кенигсбергских мостах».

26. В-деревья. Основные понятия, определения и примеры использования.

27. Таблицы с прямым доступом и хэш – таблицы.

28. Понятие хеш-функции, требования к хеш-функции, примеры таких функций. Понятие коллизии.

29. Разрешение коллизий с помощью метода цепочек.

30. Методы расстановки: деление, умножение, универсальное хэширование.

31. Открытое и закрытое хеширование.

 

Алгоритмы

32. Простой алгоритм внутренней сортировки (вставками).

33. Простой алгоритм внутренней сортировки (выбором).

34. Простой алгоритм внутренней сортировки (пузырьковая).

35. Усовершенствованные алгоритмы внутренней сортировки (быстрая сортировка).

36. Алгоритм внешней сортировки (сортировка слиянием).

37. Алгоритм внешней сортировки (сортировка Шелла).

38. Последовательный поиск.

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

40. Поиск по вторичным ключам. Организация инвертированных индексов.

41. Использование деревьев в задачах поиска.

42. Поиск подстрок в тексте (Прямой поиск).

43. Поиск подстрок в тексте (Алгоритм Кнута, Мориса, Пратта).

44. Поиск подстрок в тексте (Алгоритм Боуера, Мура, Хорспула).

45. Алгоритмы на графах (поиск в глубину).

46. Алгоритмы на графах (поиск в ширину).

47. Отношение порядка и его свойства.

48. Алгоритмы на графах (топологическая сортировка).

49. Кратчайшие пути в графе. Алгоритм Дейкстры.

50. Кратчайшие пути в графе. Алгоритм Беллмана-Форда.

51. Кратчайшие пути в графе. Алгоритм Флойда-Уоршелла.

52. Переборные алгоритмы.

53. Рекурсия. Выполнение рекурсивного вызова, использование стека.

54. Рекурсия с возвратом. Решение задачи об обходе конём шахматной доски.

55. Понятие сложности и эффективность алгоритмов обработки структур данных.

56. Эффективность алгоритмов сортировки и поиска.

57. Основные понятия кодирования и сжатия данных.

58. Алгоритм кодирования Хаффмана.

59. Алгоритм сжатия Лемпеля-Зива-Велча.

 

Стандартная библиотека шаблонов STL

60. Общие положения STL.

61. Понятие шаблона (шаблонные функции, шаблонные классы).

62. Пространства имен.

63. Основные составляющие STL (контейнеры, алгоритмы, итераторы).

64. Последовательные контейнеры (векторы, списки, двусторонние очереди).

65. Методы работы с последовательными контейнерами.

66. Алгоритм сортировки в STL.

67. Алгоритм поиска в STL.

68. Алгоритм копирования и итератор вставки.

69. Алгоритм слияния в STL.

70. Категории итераторов.

71. Алгоритмы replace и reverse в STL.

72. Алгоритм accumulate в STL.

73. Алгоритм count в STL.

74. Функциональные объекты, определенные в STL.

75. Ассоциативные контейнеры в STL.

76. Методы и свойства ассоциативных контейнеров.

77. Множества и словари.

78. Множества и словари с дубликатами.

79. Понятие пары в STL.

80. Приемы работы со словарем.

81. Адаптеры контейнеров.

82. Понятие задач класса Р.

83. NP-полная задача. Примеры.

84. Методы разработки алгоритмов. Метод декомпозиции.

85. Методы разработки алгоритмов. Динамическое программирование.

86. Методы разработки алгоритмов. Поиск с возвратом.

87. Методы разработки алгоритмов. Метод ветвей и границ.

88. Методы разработки алгоритмов. Метод альфа-бета отсечения.

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.