Методическое пособие по курсу Структуры данных и алгоритмы их обработки предназначено для студентов, обучающихся по направлениям Управление в технических системах
 Скачать 269 Kb.
|
Темы курсовых проектов1. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация динамической структуры данных типа стек; – создание стека, уничтожение стека, добавление элемента, исключение элемента, определение текущего числа элементов в стеке, очистка стека. Написать программу, иллюстрирующую работу с данной библиотекой. 2. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация динамической структуры данных типа очередь; – создание очереди, уничтожение очереди, добавление элемента, исключение элемента, определение текущего числа элементов в очереди, очистка очереди. Написать программу, иллюстрирующую работу с данной библиотекой. 3. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация динамической структуры данных типа дек – создание дека, уничтожение дека, добавление элемента, исключение элемента, определение текущего числа элементов в деке, очистка дека. Написать программу, иллюстрирующую работу с данной библиотекой. 4. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация динамической структуры данных типа кольцевая очередь; – создание кольцевой очереди, уничтожение очереди, добавление элемента, исключение элемента, определение текущего числа элементов в кольцевой очереди, очистка очереди. Написать программу, иллюстрирующую работу с данной библиотекой. 5. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организовать структуру данных типа строка (с представлением строки переменной длины со счётчиком) ; – функции создания строки, уничтожения строки, присваивания строки, определения длины строки, конкатенацию (слияние) строк, поиска вхождения подстроки в строке. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 6. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организовать структуру данных типа строка (с представлением строки переменной длины с признаком конца) ; – функции создания строки, уничтожения строки, присваивания строки, определения длины строки, конкатенацию (слияние) строк, поиска вхождения подстроки в строке. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 7. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация структуры данных типа двусвязный линейный список; – функции создания списка, уничтожения списка, доступа к элементу списка, обновления элемента списка, вставки элемента в список, удаления элемента из списка, сортировки элементов, поиска вхождения элемента. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 8. Сравнить эффективность алгоритмов сортировки – шейкерной и сортировки вставками. Для этого подсчитать среднее число сравнений (по 30 реализациям, со случайным расположением элементов), необходимое для сортировки n элементов тем и другим алгоритмом. Организовать библиотеку, содержащую подпрограммы для реализации функциональности поставленной задачи 9. Сравнить эффективность алгоритмов сортировки – пузырьковой и сортировки прямым выбором. Для этого подсчитать среднее число сравнений (по 100 реализациям, со случайным расположением элементов), необходимое для сортировки n элементов тем и другим алгоритмом. Организовать библиотеку, содержащую подпрограммы для реализации функциональности поставленной задачи 10. Сравнить эффективность алгоритмов сортировки – сортировки вставками и сортировки выбором. Для этого подсчитать среднее число сравнений (по 100 реализациям, со случайным расположением элементов), необходимое для сортировки n элементов тем и другим алгоритмом. Организовать библиотеку, содержащую подпрограммы для реализации функциональности поставленной задачи 11. Сравнить эффективность алгоритмов поиска – последовательного и бинарного. Для этого подсчитать среднее число сравнений (по 100 реализациям, с упорядоченным расположением элементов), необходимое для поиска вхождения случайного элемента тем и другим алгоритмом. Организовать библиотеку, содержащую подпрограммы для реализации функциональности поставленной задачи 12 Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация иерархической структуры данных : бинарное дерево поиска(БД); – создание БД: поиск и вставка элемента в БД, удаления элемента из БД; - обход дерева тремя стандартными способами. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 13. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация иерархической структуры данных :сбалансированное бинарное дерево (АВЛ); – создание АВЛ-дерева, поиск и вставка элемента в АВЛ-дерево с грамотной балансировкой, удаления элемента из АВЛ-дерева, обход дерева тремя стандартными способами. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 14. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация иерархической структуры данных :сильноветвящееся дерево (Б-дерево); – создание Б-дерева: а) поиск и вставка элемента в Б-дерево с возможностью расщепления страниц, б) удаления элемента из Б-дерева с возможным слиянием страниц. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 15. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация хеш-таблицы с разрешением коллизий методом внешних цепочек; – создание хеш-таблицы с использованием хеш-функции универсального хеширования, поиск и вставка элемента в хеш-таблицу, удаления элемента из хеш-таблицы. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 16. Создать программный модуль, содержащий описание динамической библиотеки, обладающей следующими подпрограммами: – организация хеш-таблицы методом двойного хеширования – создание хеш-таблицы с использованием хеш-функции универсального хеширования, поиск и вставка элемента в хеш-таблицу, удаления элемента из хеш-таблицы, Написать программу, иллюстрирующую работу с организованной динамической библиотекой. 17. Создать программный модуль, содержащий описание динамической библиотеки, со следующими подпрограммами: – организация структуры данных для представления ориентированного взвешенного графа – поиск каркаса минимального веса алгоритмом Прима, обход графа поиском в ширину, построение дерева поиска в ширину. Написать программу, иллюстрирующую работу с организованной динамической библиотекой 18. Создать программный модуль, содержащий описание динамической библиотеки, со следующими подпрограммами: – организация структуры данных для представления ориентированного взвешенного графа – поиск каркаса минимального веса алгоритмом Крускала, обход графа поиском в глубину, построение и сохранение каркаса поиском в глубину. Написать программу, иллюстрирующую работу с организованной динамической библиотекой 19. Создать программный модуль, содержащий описание динамической библиотеки, со следующими подпрограммами: – организация структуры данных для представления ориентированного взвешенного графа – поиск каркаса минимального веса, поиск кратчайшего пути в графе алгоритмом Дейкстры. Написать программу, иллюстрирующую работу с организованной динамической библиотекой. |