Перечень вопросов по курсу Модели и структуры данных

Перечень вопросов по курсу " Модели и структуры данных "

Екзамен проводится письменно. Время проведения экзамена до 60 минут. В билете три вопроса – два теоретических и один практический.

1.	Определение и особенности алгоритма.
2.	Временная сложность алгоритма.
3.	Задача сортировки. Классификация методов сортировки.
4.	Алгоритм сортировки простыми включениями и его сложность.
5.	Алгоритм сортировки простым обменом и его сложность.
6.	Алгоритм шейкер-сортировки и его сложность.
7.	Алгоритм сортировки простым выбором и его сложность.
8.	Алгоритм быстрой сортировки и его сложность.
9.	Алгоритм сортировки подсчетом.
10.	Алгоритм поразрядной сортировки LSD и его сложность.
11.	Алгоритм поразрядной сортировки MSD и его сложность.
12.	Алгоритм сортировки слиянием и его сложность.
13.	Структура данных типа стек. Операции над стеком.
14.	Структура данных типа очередь. Операции над очередью.
15.	Структура данных типа список. Операции над списком.
16.	Основные понятия информационного поиска.
17.	Линейный поиск в массиве.
18.	Поиск с использованием индексации по ключам.
19.	Поиск в упорядоченном массиве. Последовательный поиск. Двоичный поиск.
20.	Поиск в упорядоченном массиве. Интерполяционный поиск. M -блочный поиск.
21.	Задача поиска в строке. Алгоритмы поиска в строке.
22.	Организация данных методом расстановки. Виды функций расстановки.
23.	Организация данных методом расстановки. Методы разрешения коллизий.
24.	Определение деревьев и способы их представления.
25.	Деревья двоичного поиска и операции с ними.
26.	Идеально сбалансированные и сбалансированные деревья. Алгоритм балансировки дерева.
27.	Определение графов и способы их представления.
28.	Постановка задачи поиска минимального остовного дерева. Алгоритм Краскала.
29.	Постановка задачи поиска минимального остовного дерева. Алгоритм Прима.
30.	Постановка задачи поиска кратчайших путей.
31.	Алгоритм Дейкстры поиска кратчайших путей из одной вершины.
32.	Алгоритм определения номеров вершин кратчайшего пути.
33.	Матричный метод определения кратчайших путей.

!!!! Еще будут вопроси и задачи по материалу “Поиск в строке”!!!

Перечень вопросов по курсу " Модели и структуры данных "

1.	Определение и особенности алгоритма. Определение понятия алгоритм. Примеры алгоритмов. Особенности алгоритма.
2.	Временная сложность алгоритма. Определение временной сложности алгоритма. Понятие О –обозначения. Пример сравнительной оценки сложности алгоритмов. Правила работы с О –символикой.
3.	Задача сортировки. Классификация методов сортировки. Задача и цель сортировки. Показатели качества алгоритмов сортировки. Классификация методов сортировки.
4.	Алгоритм сортировки простыми включениями и его сложность. Сущность алгоритма сортировки простыми включениями. Пример работы алгоритма сортировки. Достоинства, недостатки и анализ сложности алгоритма.
5.	Алгоритм сортировки простым обменом и его сложность. Сущность алгоритма сортировки простым обменом. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
6.	Алгоритм шейкер-сортировки и его сложность. Сущность алгоритма шейкер-сортировки. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
7.	Алгоритм сортировки простым выбором и его сложность. Сущность алгоритма сортировки простым выбором. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
8.	Алгоритм быстрой сортировки и его сложность. Сущность алгоритма быстрой сортировки. Выбор элемента разбиения. Анализ сложности быстрой сортировки.
9.	Алгоритм сортировки подсчетом. Сущность алгоритма сортировки подсчетом. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
10.	Алгоритм поразрядной сортировки LSD и его сложность. Сущность алгоритма LSD сортировки. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
11.	Алгоритм поразрядной сортировки MSD и его сложность. Сущность алгоритма MSD сортировки. Пример работы алгоритма сортировки. Достоинства, недостатки и сложность алгоритма.
12.	Структура данных типа стек. Операции над стеком. Определение и области применения стека. Операции над стеком. Реализация стека с помощью массива. Операции над стеком и их реализация.
13.	Структура данных типа стек. Операции над стеком. Определение и области применения стека. Реализация стека с помощью указателей. Операции над стеком и их реализация.
14.	Структура данных типа очередь. Операции над очередью. Определение и области применения очереди. Реализация очереди с помощью кольцевого массива. Операции над очередью и их реализация.
15.	Структура данных типа очередь. Операции над очередью. Определение и области применения очереди. Реализация очереди с помощью указателей. Операции над очередью и их реализация.
16.	Структура данных типа список. Операции над списком. Определение и области применения списка. Отличия списка от стека и очереди. Реализация списка с помощью массива. Операции над списком и их реализация.
17.	Структура данных типа список. Операции над списком. Определение и области применения списка. Отличия списка от стека и очереди. Реализация списка с помощью указателей. Операции над списком и их реализация.
18.	Основные понятия информационного поиска. Основные операции информационного поиска. Типы условий поиска.
19.	Линейный поиск в массиве. Алгоритм линейного поиска. Условия окончания алгоритма. Алгоритм линейного поиска с барьером. Сложность линейного поиска. Пример работы алгоритма поиска.
20.	Поиск с использованием индексации по ключам. Особенности алгоритма. Достоинства и недостатки алгоритма, его сложность. Пример работы алгоритма поиска.
21.	Поиск в упорядоченном массиве. Последовательный поиск. Двоичный поиск. Достоинства и недостатки упорядоченного поиска. Последовательный поиск. Пример работы алгоритма последовательного поиска. Достоинства, недостатки и сложность алгоритма. Алгоритм двоичного поиска. Пример работы алгоритма двоичного поиска. Достоинства, недостатки и сложность алгоритма.
22.	Поиск в упорядоченном массиве. Интерполяционный поиск. M -блочный поиск. Алгоритм интерполяционного поиска. Пример работы алгоритма интерполяционного поиска. Достоинства, недостатки и сложность алгоритма. Алгоритм M -блочного поиска. Пример работы алгоритма M-блочного поиска. Достоинства, недостатки и сложность алгоритма.
23.	Задача поиска в строке. Алгоритмы поиска в строке. Постановка задачи поиска в строке. Алгоритмы прямого поиска в строке, КМП-поиска, БМ-поиска, РК-поиска. Примеры работы алгоритмов. Сложность алгоритмов.
24.	Организация данных методом расстановки. Виды функций расстановки. Сущность, достоинства и недостатки прямой адресации. Сущность, достоинства и недостатки хеширования. Требования к функции расстановки. Виды функции расстановки.
25.	Организация данных методом расстановки. Методы разрешения коллизий внутри таблицы. Сущность, достоинства и недостатки хеширования. Сущность методов линейных проб, квадратичных проб, двойного хеширования. Показатели оценки эффективности методов разрешения коллизий внутри таблицы.
26.	Организация данных методом расстановки. Методы разрешения коллизий внутри таблицы. Сущность, достоинства и недостатки хеширования. Сущность метода двойного хеширования, метода двух аргументов, случайного метода. Показатели оценки эффективности методов разрешения коллизий внутри таблицы.
27.	Организация данных методом расстановки. Метод внешнего разрешения коллизий. Сущность, достоинства и недостатки хеширования. Сущность метода внешнего разрешения коллизий. Сложность операций поиска, вставки и удаления.
28.	Определение деревьев и способы их представления. Определение дерева и основных его компонентов (корень, лист, уровень узла, бинарное дерево и его виды). Операции над бинарное деревом. Обход дерева.
29.	Определение деревьев и способы их представления. Определение дерева и основных его компонент (корень, лист, уровень узла, бинарное дерево и его виды). Способы представления дерева. Примеры различного представления деревьев.
30.	Деревья двоичного поиска и операции с ними. Определение дерева двоичного поиска (ДДП). Пример построения ДДП. Алгоритмы поиска, поиска минимального элемента, вставки, удаления и их сложность.
31.	Идеально сбалансированные и сбалансированные деревья. Определение идеально сбалансированного и сбалансированного деревьев. Вставка в сбалансированное дерево. Алгоритм поддержания сбалансированности дерева.
32.	Определение графов и способы их представления. Определение обыкновенных неориентированных графов. Степень вершины, маршрут, цикл, гамильтонов и эйлеров циклы. Способы представления графов.
33.	Способы представления графов. Матрица смежностей. Матрица инцидентности. Матрица списка ребер. Список ребер. Список смежностей. Примеры различного представления графов.
34.	Постановка задачи поиска минимального остовного дерева. Алгоритм Краскала. Постановка задачи. Область использования задачи. Понятие жадного алгоритма. Алгоритм Краскала и его сложность. Пример работы алгоритма поиска.
35.	Постановка задачи поиска минимального остовного дерева. Алгоритм Прима. Постановка задачи. Область использования задачи. Понятие жадного алгоритма. Алгоритм Прима и его сложность. Пример работы алгоритма поиска.
36.	Постановка задачи поиска кратчайших путей. Области применения задачи. Критерии оптимальности пути. Постановка задачи о поиске кратчайшего пути. Варианты задач о поиске кратчайшего пути. Методы решения задачи.
37.	Алгоритм Дейкстры поиска кратчайших путей. Постановка задачи о поиске кратчайшего пути. Ограничение алгоритма. Алгоритм Дейкстры. Алгоритм определения номеров вершин. Выводы по работе алгоритма Дейкстры. Пример работы алгоритма. Сложность алгоритма.
38.	Матричный алгоритм определения кратчайших путей. Постановка задачи о поиске всех кратчайших путей. Методы решения задачи поиска всех кратчайших путей. Матричный алгоритм. Пример работы алгоритма. Сложность алгоритма. Алгоритм определения номеров вершин.

Перечень основных типов задач по курсу" Модели и структуры данных "

1.	С помощью алгоритма сортировки простым выбором (или простым обменом, простой вставкой, шейкер-сортировки, быстрой сортировки) выполнить пошаговую сортировку по возрастанию элементов (10, …, 7). Определить количество сравнений и обменов для реализации сортировки.
2.	С помощью алгоритма сортировки подсчетом (или поразрядной сортировки LSD, поразрядной сортировки MSD) выполнить пошаговую сортировку по возрастанию элементов (3, …, 9). Определить количество присваиваний для реализации сортировки.
3.	С помощью алгоритма бинарного поиска (или интерполяционного поиска, m–блочного поиска, линейного поиска, линейного поиска с барьером, поиска с использованием индексации по ключам) выполнить пошаговый поиск ключа a =… среди элементов (10, …, 7). Определить количество сравнений и обменов для реализации поиска.
4.	С помощью алгоритма РК-поиска в строке найти образец W ={2 … 7} в строке T ={3 … 0}, q =7, алфавит десятичный. Определить количество холостых срабатываний.
5.	Используя метод расстановки выполнить операции вставки и потом поиска элементов {5, …, 6}, N =13. Для разрешения коллизий использовать метод линейных проб (или квадратичных проб, двойного хеширования, двух аргументов, случайный метод). Определить среднее число обращений к таблице при вставке и поиске.
6.	С помощью матрицы смежностей (или матрицы инцидентности, массива (два вида), связанного списка) представить следующее дерево ….
7.	Определить для каждой вершины двоичного дерева поиска (6, …, 15) значения показателей идеальной сбалансированности и сбалансированности.
8.	С помощью матрицы смежностей (или матрицы инцидентности, матрицы списка ребер, списком ребер, списками смежностей) представить следующий граф.
9.	С помощью алгоритма Краскала (или Прима, или Борувки) построить остовное дерево наименьшей стоимости.
10.	С помощью алгоритма Дейкстры определить длины всех кратчайших путей от s -ой вершины и маршруты всех кратчайших путей от s -ой вершины до t -ой вершины.
11.	С помощью матричного алгоритма определить длины всех кратчайших путей и маршруты всех кратчайших путей от s -ой вершины до t -ой вершины.

Утверждено на заседании кафедры «Компьютерные системы и сети».Протокол № 4 от 1 ноября 2012 г.

Зав. кафедрою_____________В.С. Харченко Преподаватель_____________А.В.Шостак

Дата добавления: 2015-11-04