Алгоритмы и структуры данных

Лабораторная работа №1
Тема: "Поиск ключа в массиве. Анализ эффективности алгорит-мов поиска"
I. Разработать программу, обеспечивающую выполнение следующих функций:
1. Формирование и вывод на экран массива случайных чисел, со-стоящего из n целочисленных элементов (n – заданное число).
2. Поиск заданного ключа в исходном неотсортированном массиве.
Значение ключа вводиться в режиме диалога или формируется дат-чиком случайных чисел.
Используется следующий метод поиска ключа:
• для студентов с четными номерами – метод последовательного поиска с барьером
Лабораторная работа №2
Тема: "Сортировка массивов. Анализ эффективности алгорит-мов сортировки"
I. Разработать программу, обеспечивающую выполнение следующих функций:
1. Формирование и вывод на экран массива случайных чисел, со-стоящего из n целочисленных элементов (n – заданное число).
2. Сортировка исходных массивов двумя методами, заданными в табл. П.1.
Примечание: сортировка элементов в массиве каждым из методов должна сопровождаться определением времени сортировки или подсче-том количества операций сравнения, выполненных программой (данная характеристика выбирается разработчиком).
II. Выполнить разработанную программу для различных значений n в диапазоне от 100 до 1000.
III. Оценить эффективность работы алгоритмов сортировки и произ-вести их сравнение. Построить графики характеризующие зависимость времени (или количества операций сравнения) от n для заданных методов сортировки.
Методы сортировок, выбираемые по вариантам:
11. Быстрая сортировка выбором (турнир с выбыванием или пира-мидальная – по выбору).
12. Сортировка подсчетом
Лабораторная работа №3
Тема: "Работа с линейными списками"
1. Выбрать из табл. П.2 вид списка, способ его реализации и функ-ции, которые надо выполнить. Написать программу, которая создает список из десяти элементов и выполняет заданную в табл. П.2 последо-вательность функций.
2. Список функций, номера которых содержатся в последней ко-лонке таблицы:
1) обход списка;
2) сортировка элементов списка;
3) поиск элемента списка, совпадающего с заданным ключом x, причем данный элемент может отсутствовать в списке;
4) удаление шестого по порядку элемента списка;
5) добавление в список нового элемента после элемента, совпада-ющего с ключом x; если такого элемента нет, добавить новый элемент в начало списка;
6) добавление в список после второго элемента трех новых элемен-тов;
7) удаление из списка всех элементов, которые меньше среднего значения элементов списка;
8) обход списка с вычислением среднего значения элементов списка.
Варианты индивидуального задания.
Номер послед. цифры ст. кода Вид списка Способ реализации списка Выполняемые функции
0, 8 Линейный однонаправленный Двумя массивами 1, 2, 5, 6, 1
Лабораторная работа №4
Тема: "Методы обхода графов"
1. Нарисовать на бумаге граф, состоящий из 10 вершин. В вершины графа записать буквы, которые образуют вашу фамилию и часть имени.
2. В соответствии с табл. П.3 реализовать граф в ЭВМ. Обойти граф, используя заданный в табл. П.3 алгоритм, и прочитать текст в вершинах графа.
3. Проанализировать прочитанный текст и переставить буквы в вершинах так, чтобы фамилия и имя читались правильно. Снова обойти граф, прочитав новый текст.
Примечание: Способ построения графа и его обход реализовать в про-грамме. Анализ прочитанного текста и перестановка букв в вершинах графа может выполняться как программным путем, так и вручную.
Варианты индивидуального задания.
Способ реализации графа
Список инцидентности
Метод обхода графа
Обход в глубину
Лабораторная работа №5
Тема: " Бинарные деревья"
Вариант I
1. Построить упорядоченное сбалансированное бинарное дерево.
2. Найти узел, содержащий элемент, который совпадает с заданным ключом.
3. Удалить найденный узел.
4. Проверить условие сбалансированности дерева, если оно наруше- но, перес