Задание к контрольной работе по дисциплине «Структуры и алгоритмы обработки данных»

Задание к контрольной работе

по дисциплине «Структуры и алгоритмы обработки данных»

Номер задания выбирается по зачётной книжке. Если у Вас номер больше 25, то необходимо отнять от номера 25 – получится номер варианта.

Правильность выбора варианта будет контролироваться!!!

Целью изучения дисциплины «Структуры и алгоритмы обработки данных» является:

·  изучение различных форм организации данных в программах и методов их обработки и применения в различных классах задач,

·  освоение технологии программирования структур данных и алгоритмов их обработки

В контрольной работе необходимо описать логическую структуру данных, алгоритм и программу обработки базовой структуры.

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

№	задание	Исходные данные
1.	Бинарное упорядоченное сбалансированное дерево	Базовая структура данных - Дерево Функции - создание дерева, уничтожение дерева, добавление элемента, исключение элемента, определение текущего числа элементов в дереве, очистка дерева, функция балансировки дерева. Примечание: написать программу, иллюстрирующую работу с данной структурой.
2.	Информационно-поисковая система автосалона.	Базовая структура данных - Мультисписок Для каждого клиента формируется список оказываемых услуг. Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
3.	Информационно-поисковая система аптеки.	Базовая структура данных - Слоёный список Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
4.	Информационно-поисковая система бухгалтерии фирмы.	Базовая структура данных - Однонаправленный список Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
5.	Информационно-поисковая система справочной аэропорта.	Базовая структура данных - Мультисписок. Каждому маршруту выделяется отдельный список. Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
6.	Информационно-поисковая система инспектора отдела кадров.	Базовая структура данных - Дерево Функции - создание дерева, уничтожение дерева, добавление элемента, исключение элемента, определение текущего числа элементов в дереве, очистка дерева. Примечание: написать программу, иллюстрирующую работу с данной структурой. В виде дерева представить иерархию должностей в организации.
7.	Информационно-поисковая система музыкального магазина.	Базовая структура данных - двунаправленный список. Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
8.	Информационно-поисковая система склада.	Базовая структура данных - Слоёный список Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
9.	Информационно-поисковая система научной библиотеки.	Базовая структура данных - Мультисписок. Каждому автору создаётся отдельный список. Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, поиск вхождения элемента. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
10.	Информационно-поисковая система справочной железнодорожной станции.	Базовая структура данных - Граф Функции - создание графа, уничтожение графа, поиск элемента графа, обновление элемента графа, добавление элемента в граф, удаление элемента из графа, поиск вхождения элемента, поиск кратчайшего пути. Примечание: написать программу, иллюстрирующую работу с данной структурой. Набор данных определяется самостоятельно.
11.	Сжатие данных	Алгоритм - кодирование Хаффмана Функции – компрессия и декомпрессия данных. Примечание: написать программу, иллюстрирующую работу алгоритма Хаффмана. Реализовать возможность просмотра оптимальных префиксных кодов.
12.	Моделирование работы стека	Базовая структура данных - стек Функции - создание стека, уничтожение стека, добавление элемента, исключение элемента, определение текущего числа элементов в стеке, очистка стека, определение количества элементов между минимальным и максимальным элементами стека Примечание: написать программу, иллюстрирующую работу с данной структурой. Стек содержит числовые данные.
13.	Поиск кратчайшего пути	Базовая структура данных - Граф Функции - создание графа, уничтожение графа, добавление элементов графа удаление элементов из графа, поиск и вывод кратчайшего пути. Примечание: Реализовать алгоритм Флойда
14.	Поиск кратчайшего пути	Базовая структура данных - Граф Функции - создание графа, уничтожение графа, добавление элементов графа удаление элементов из графа, поиск и вывод кратчайшего пути. Примечание: Сравнить эффективности метода поиска в ширину и алгоритма Дейкстры.
15.	Система поддержки принятия решения «Кулинарная книга»	Базовая структура данных - Дерево Функции - создание дерева, уничтожение дерева, добавление элементов дерева, исключение элементов, определение текущего числа элементов в дереве, очистка дерева. Примечание: реализовать программу, осуществляющую поиск блюд, которые можно приготовить при наличии определённых продуктов. Определить не менее 15 видов продуктов.
16.	Сравнение эффективности методов поиска	Осуществить поиск слова в тексе. Методы - алгоритм Боуера-Мура, алгоритм Кнута–Мориса –Пратта (КМП) Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений от объёма данных.
17.	Нахождение минимального остовного дерева.	Базовая структура данных - Граф Функции - создание графа, уничтожение графа, добавление элементов графа удаление элементов из графа, вывод минимального остовного дерева. Примечание: Реализовать алгоритм Крускала.
18.	Сравнительное исследование эффективности методов сортировки	Базовая структура данных - Вектор Методы сортировки - Подсчётом, простым извлечением Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений и  числа перестановок элементов  от объёма данных.
19.	Сравнительное исследование эффективности методов сортировки	Базовая структура данных - Вектор Методы сортировки - Подсчётом, Слиянием Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений и  числа перестановок элементов  от объёма данных.
20.	Сравнительное исследование эффективности методов сортировки	Базовая структура данных - Вектор Методы сортировки - простым включением, метод пузырька Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений и  числа перестановок элементов  от объёма данных.
21.	Информационно-поисковая система администратора гостиницы	Базовая структура данных - Разреженная матрица. Функции - создание матрицы, уничтожение матрицы, добавление элемента, исключение элемента, определение текущего числа элементов в матрице, очистка матрицы, поиск номеров с определённым количеством свободных мест. Примечание: написать программу, иллюстрирующую работу с данной структурой. В виде элементов матрицы представить номера гостиницы.
22.	Сравнительное исследование эффективности методов сортировки	Базовая структура данных - Вектор Методы сортировки - Шелла, Древесная сортировка Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений и  числа перестановок элементов  от объёма данных.
23.	Сравнительное исследование эффективности методов сортировки	Базовая структура данных - Вектор Методы сортировки - Метод пузырька, Хоара Примечание: Сравнение приводится в виде графиков зависимостей количества сравнений и  числа перестановок элементов  от объёма данных.
24.	Хэш-поиск	Базовая структура данных - Список Функции - создание списка, уничтожение списка, доступ к элементу списка, обновление элемента списка, вставке элемента в список, удаление элемента из списка, сортировка элементов, хэш-поиск вхождения элемента, отображение хэш-таблицы; Примечание: Открытое хеширование
25.	Раскраска графа	Базовая структура данных - Граф Функции - создание графа, уничтожение графа, добавление элементов графа удаление элементов из графа, вывод раскрашенного графа Примечание: Реализовать алгоритм раскраски графа. Граф содержит не менее 50 вершин.