SPO / quest2_SPO
.doc
Системное программное обеспечение
Лекционный курс
доцента кафедры информационных систем и компьютерных технологий
Пановой Т.В.
Контрольные вопросы №2
-
Мультисписок, объединение двух линейных списков в мультисписок.
-
Что такое «таблица», «ключ», «табличная запись»?
-
Что такое «граф»? Дерево как частный случай графа.
-
Что такое «бинарное дерево»? Классификация бинарных деревьев.
-
Структуры хранения данных – вектор, список, сети.
-
Отображение структур данных – строки и массив – в структуры хранения.
-
Хранение массива в виде вектора. Функция упорядочения.
-
Хранение стека и очереди.
-
Хранение деревьев. Списочное представление бинарных деревьев.
-
Прохождение бинарных деревьев.
-
Идеально сбалансированное дерево.
-
Сортировка с прохождением бинарного дерева.
-
Сортировка методом турнира с выбыванием.
-
Представление арифметических выражений в виде дерева. Использование бинарных деревьев для вычисления арифметических выражений.
-
Какие таблицы являются постоянными, а какие – временными? Отображение таблиц в памяти. В чем состоит задача поиска данных в таблице? Основная характеристика способа организации таблицы.
-
Неупорядоченные таблицы.
-
Древовидные таблицы.
-
Упорядоченные таблицы.
-
Таблицы с вычисляемыми входами – таблицы с прямым доступом.
-
Таблицы с вычисляемыми входами – таблицы со случайным перемешиванием. Метод открытого перемешивания.
-
Таблицы со случайным перемешиванием. Перемешивание с цепочками переполнения.
-
Функция расстановки. Метод выделения части цифрового ключа.
-
Функция расстановки. Метод деления.
-
Поиск в таблице. Общие методы поиска.
-
Основные алгоритмы поиска – прямой поиск строки, алгоритм Кнута, Мориса и Пратта (КМП-поиск).
-
Основные алгоритмы поиска – алгоритм Боуера и Мура (БМ-поиск), бинарный поиск.
-
Что такое «таблица идентификаторов»? Абстрактные структуры данных.
-
Что такое «хеш-адресация»? Что такое «коллизии»?
-
Методы разрешения коллизий – метод цепочек.
-
Методы разрешения коллизий – метод открытой адресации.
-
Что такое «хеш-функция» и «хеширование»?
-
Метод организации таблиц идентификаторов, основанный на использовании хеш-адресации.
-
Построение таблиц идентификаторов на основе хеш-функций.
-
Рехеширование.
-
Построение таблиц идентификаторов по методу цепочек. Алгоритм работы метода цепочек.
-
Построение таблиц идентификаторов по методу цепочек. Алгоритм поиска элемента в таблице идентификаторов.
-
Комбинированные способы построения таблиц идентификаторов.