Лабораторная «5 лаб. работ на С/С++, среда программирования по выбору »,
Структуры и алгоритмы обработки данных в Казани

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