Реферат: Вопросы по структурам данных

Вопросы по структурам данных



Линейные списки. Определение. Свойства. Способы представления в памяти. Основные операции




Вирт



Полустатические структуры данных. Типы структур. Основные операции.




Вирт



Арифметические выражения. Вычисление выражений. Полиз. Преобразование арифметического выражения в полиз.




Вирт



Связные списки. Классификация. Основные операции и их реализация для линейных списков. Сравнительная характеристика списков.




Вирт



Циклические списки. Классификация. Работа с полиномами.




Вирт



Циклические списки. Классификация. Двухсвязные списки. Реализация основных операций.




Вирт



Иерархические структуры. Деревья. Типы деревьев. Бинарные деревья. Понятие высоты. Нахождение высоты.




Вирт



Бинарные деревья. Обход бинарного дерева. Типы обходов.




Вирт



Бинарные деревья. Деревья двоичного поиска. Построение ДДП. Способы отображения структуры деревьев.




Вирт



Бинарные деревья. Прошитые деревья. Формирование прошитых деревьев. Обход их. Удаление элементов прошитых деревьев.

З






Бинарные деревья. Способы представления в памяти. Представление БД в векторной памяти. Обход такого дерева. Добавление и удаление элементов в бинарных деревьях. Оценка трудоемкости операций.




Вирт



Бинарные деревья. Длина внешнего и внутреннего пути. Использование этих понятий для оценки трудоемкости операций.




Вирт



Лес. Сильноветвящиеся деревья. Способы представления в памяти. Обход сильноветвящегося дерева. Представление леса в виде бинарного дерева. Обратный алгоритм.









Бинарные деревья. Способы представления в памяти. Представление БД номерами Дьюи. Обход такого дерева. Нахождение высоты. Переход от представления номерами Дьюи к представлению дерева в векторной памяти.









Сбалансированные деревья. Строго сбалансированные деревья. Простейший алгоритм формирования сбалансированного дерева. АВЛ-деревья. операции для работы с АВЛ-деревьями.




Вирт



КЧД-деревья. операции для работы с КЧД-деревьями.









В-деревья порядка n (ВДПn). Определение. Формирование дерева.




Вирт



В-деревья порядка n (ВДПn). Поиск информации в дереве. Удаление информации. Оценка трудоемкости операций.




Вирт



Рекурсивные алгоритмы. Назначение. Примеры задач.









Графы. Типы графов. Сети. Способы задания графов. Подграфы. Пути. Маршруты. Типы путей. Циклы. Типы циклов.









Графы Способы обхода графов.








Понятие каркаса. Виды каркасов. Алгоритмы нахождения каркасов









Достижимость и контрдостижимость в графах. Сильносвязные компоненты. Граф конденсаций.









Алгоритм нахождения Эйлерова цикла.









Алгоритм нахождения Гамильтонова цикла









Фундаментальные циклы. Алгоритм нахождения фундаментальных циклов.









Алгоритм нахождения кратчайших путей(алгоритм Дейкстры, алгоритм Флойда)









Множество независимых вершин графа. Доминирующее множество. Раскраска графа.









Двудольные графы. Проверка на двудольность.









Поток. Сеть. Метод Форда- Фалкерсона нахождения максимального потока..









Поток. Сеть. Метод Эдмондса-Карпа нахождения максимального потока..









Поток. Сеть. Метод проталкивания предпотока.









Поток. Сеть. Метод поднять и в начало для нахождения максимального потока.









Методы нахождения максимального потока. Сравнительная характеристика методов.









Длинные числа. Способы представления в памяти. Основные операции и их программная реализация.









Сортировка. Классификация методов сортировки.









Методы внутренней сортировки. Сравнительная характеристика методов. Программная реализация метода сортировки выбором.









Программная реализация метода сортировки вставками.









Программная реализация обменной сортировки.









Улучшенные методы сортировки (шейкерная, уменьшающимися расстояниями, деревом, пирамидой, быстрая)









Методы внешней сортировки. Сравнительная характеристика методов. Программная реализация метода прямого слияния.









Программная реализация модифицированного метода прямого слияния.









Метод естественного слияния и его модификации.









Многопутевое слияние









Многофазная сортировка









Поиск подстрок. Сравнительная характеристика основных методов. Алгоритм Рабина-Карпа









Поиск подстрок. Алгоритм Кнута-Морриса-Карпа









Поиск подстрок. Алгоритм Бойера-Мура.









Таблицы. Назначение таблиц. Основные виды таблиц. Операции с таблицами









Таблицы. Методы уплотнения.









Динамическое программирование. Решение задач динамического программирования. Основные этапы и их характеристика.









Умножение матриц. Минимизация трудоемкости.









Решение задачи триангуляции









Нахождение наибольшей общей подпоследовательности.









Жадные алгоритмы. Примеры задач, к которым применимы жадные алгоритмы. Теоретическое обоснование. Матроиды.