Структуры и алгоритмы обработки данных. Часть 2. Лабораторные работы №1-5 на языке С++ (для всех вариантов)

ПРАВИЛА ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ
Перед выполнением заданий лабораторной работы рекомендуется изучить теоретический материал по теме лабораторной работы и описание методов обработки данных на псевдокоде, используя конспекты лекционных занятий и литературу из списка.
Задания лабораторных работ выполняются на языке программирования С/С++, среда программирования по выбору студента.
Изучаемые методы обработки данных рекомендуется программно реализовывать в виде отдельных функций (подпрограмм), массивы (последовательности) данных должны передаваться в подпрограммы в качестве параметров. Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо также оформлять в виде отдельных подпрограмм.
При выполнении заданий следует обеспечить вывод на экран данных на всех шагах алгоритма. Программа должна иметь дружественный, интуитивно понятный интерфейс (меню пользователя, вывод подсказок, комментарии при вводе/выводе данных и т.д.).
Тестирование разработанной программы необходимо проводить для различных типов входных данных (случайный массив, упорядоченный массив в прямом и обратном порядке). После тестирования необходимо проанализировать полученные результаты, т.е. проверить соответствие полученных экспериментальным путем величин теоретическим оценкам.
Для зачета по лабораторной работе студенту необходимо представить
• Исходные тексты программ с подробными комментариями;
• Исполняемые файлы;
• Отчет по лабораторной работе.
Отчет должен включать в себя следующие разделы
• Формулировку задания
• Очень краткое описание алгоритмов, используемых в лабораторной работе;
• Результаты работы программы (в виде файла или в виде скриншота);
• Анализ и сравнение полученных результатов с теоретическими оценками.

ЛАБОРАТОРНАЯ РАБОТА 1
Тема: Идеально сбалансированное дерево поиска (ИСДП)
Цель работы: Изучение процесса программного построения ИСДП.

1. Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют
• размер дерева;
• высоту дерева;
• среднюю высоту дерева;
• контрольную сумму данных в вершинах дерева;
и проверить их работу на конкретном примере.
2. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
3. Разработать подпрограмму поиска вершины с заданным ключом в двоичном дереве поиска.
4. Разработать подпрограмму построения идеально сбалансированного дерева поиска (ИСДП) для массива случайных чисел, а также логическую функцию для определения является ли данное двоичное дерево деревом поиска.
5. Построить ИСДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенных деревьев вычислить размер, контрольную сумму, высоту и среднюю высоту, используя разработанные функции. Заполнить таблицу и проанализировать полученные результаты:
 
Размер дерева ИСДП
 Контр.
сумма Высота Теор. оценка для средней высоты Средняя
высота
100    
200    
300    
400    
500    

ЛАБОРАТОРНАЯ РАБОТА 2
Тема: Случайное дерево поиска (СДП)
Цель работы: Изучение процесса программного построения СДП.

1. Разработать подпрограмму построения случайного дерева поиска (СДП).
2. Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
3. Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП. Заполнить таблицу и проанализировать полученные результаты:

Размер дерева СДП ИСДП
 Контр.
сумма Высота Средняя
высота Контр.
сумма Высота Средняя
высота
100      
200      
300      
400      
500      

ЛАБОРАТОРНАЯ РАБОТА 3
Тема: Сбалансированные по высоте деревья поиска (АВЛ)
Цель работы: Изучение процесса программного построения АВЛ-дерева.

1. Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.
2. Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
3. Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

Размер дерева АВЛ-дерево ИСДП
 Контр.
сумма Теор. оценки для сред. высоты Средняя
высота Контр.
сумма Теор. оценки для сред. высоты Средняя
высота
100      
200      
300      
400      
500      

ЛАБОРАТОРНАЯ РАБОТА 4
Тема: Двоичное Б-дерево поиска (ДБД)
Цель работы: Изучение процесса программного построения ДБД.

1. Разработать подпрограмму построения ДБ-дерева для массива целых чисел
2. Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
3. Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

Размер дерева АВЛ-дерево ДБД
 Контр.
сумма Сред.
высота Контр.
сумма Кол-во уровней Теор. оценки для высоты ДБД Сред.
высота для дв. дерева.
100      
200      
300      
400      
500 

ЛАБОРАТОРНАЯ РАБОТА 5
Тема: Дерево оптимального поиска (приближенные алгоритмы)
Цель работы: Изучение процесса программного построения почти оптимальных деревьев поиска.
1. Реализовать программно алгоритмы А1 и А2 для построения почти оптимальных деревьев поиска.
2. Построить почти оптимальные деревья поиска из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные) с помощью алгоритмов А1 и А2, распечатать их обход слева направо.
3. Для построенных деревьев вычислить размер, контрольную сумму и средневзвешенную высоту, сравнить их с аналогичными характеристиками дерева оптимального поиска. Заполнить таблицу и проанализировать полученные результаты:
Размер дерева А1 А2
 Контр.
сумма Средне-
взвешенная высота Контр.
сумма Средне-
взвешенная высота
100    
200    
300    
400    
500

Все работы зачтены без замечаний.

Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Структуры и алгоритмы обработки данных (часть 2-я)
Вид работы: Лабораторная работа
Оценка:Зачет
Дата оценки: .01.2016
Рецензия:Уважаемый
Мачикина Елена Павловна