Структуры и алгоритмы обработки данных (часть 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)
Вид работы: Лабораторная работа 1
Оценка: Зачет
Дата оценки: 23.02.2018
Рецензия: Уважаемый
Мачикина Елена Павловна

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

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

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

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