Лабораторная №7. Деревья. Сортировка на двоичном дереве.

Используя двоичное дерево сортировать массив

Вариант	Массив
1	5, 9, 13, 14, 2, 7, 1, 15, 18, 8, 4, 3, 50
2	4, 5, 13, 8, 41, 52, 41, 64, 52, 17, 8, 9, 30
3	5, 1, 91, 4, 7, 51, 40, 61, 57, 71, 9, 8, 3
4	15, 3, 46, 54, 17, 81, 56, 72, 61, 59, 8, 3, 21
5	54, 31, 72, 62, 5, 95, 7, 64, 59, 87, 63, 64
6	57, 91, 64, 52, 73, 61, 5, 91, 11, 13, 15, 105, 7
7	17, 54, 64, 2, 17, 52, 1, 19, 17, 64, 52, 17, 24
8	54, 101, 27, 14, 17, 18, 54, 91, 72, 76, 75, 102
9	31, 102, 127, 114, 19, 54, 17, 88, 77, 11, 4, 7
10	5, 102, 7, 64, 8, 92, 54, 17, 25, 29, 44, 71

1) Реализуйте дерево в виде двусвязного списка

2) Обход слева, обход справа, симметрический обход.

3) Реализуйте программу сортировки массива на дереве методом симметрического обхода.

Лабораторная №8. Деревья. Сортировка на двоичном дереве.

Сортировать массив из задания 6 методом “Турнир с выбыванием”

Лабораторная №9. Графы. Обход графов.

Представить граф в виде

1)матрицы смежности и матрицы инцидентности. Реализовать операторы: добавить вершину, вывод смежных вершин. На основе представления графа матрицей инцидентности определите цикличность графа ( транзитивное замыкание).

Напишите процедуру рекурсивного обхода графа

2) списков узлов, причем список содержит метку(номер) вершины, номер смежной вершины и указатель

1 вариант 2 вариант

3 вариант 4 вариант

200

5 вариант

6 вариант

7 вариант 8 вариант

Вариант 9 Вариант 10

Лабораторная №10. Графы. Алгоритмы на графах

1. Напишите программу построения остовного дерева минимальной стоимости 2 методами: а) алгоритм Прима

б) алгоритм Крускаля

(граф из лаб №9.)

Лабораторная №11 Множества. Отображения. Сильноветвящиеся деревья.

Вариант 1.

Реализовать множество целых чисел на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству.
Реализовать сильноветвящееся дерево, в узлах которого хранятся целые числа методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством названий городов ХМАО и множеством населения в этих городах. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, график отображения.

Вариант 2.

1. Реализовать множество вещественных чисел на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.

2. Реализовать сильноветвящееся дерево методом списков смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.

3. Реализовать отображение между множеством школ города Нижневартовска и множеством количества учащихся в них. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 3.

1. Реализовать множество строк на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.

3. Реализовать отображение между множеством предприятий города Нижневартовска и множеством количества сотрудников в них. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 4.

Реализовать множество строк на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать сильноветвящееся дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством больниц города Нижневартовска и множеством количества сотрудников в них. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 5.

Реализовать множество битовых строк на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать сильноветвящееся дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством больниц города Нижневартовска и множеством количества сотрудников в них. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 6.

Реализовать множество профессий на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать 2-3 дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством детских садов города Нижневартовска и множеством количества детей в них. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 7.

Реализовать множество специальностей в вузах Нижневартовска на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать 3-4 дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством наименований компаний производящих легковые автомобили и марками легковых автомобилей. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 8.

1. Реализовать множество наименований продтоваров на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.

2. Реализовать 4-5 дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.

3. Реализовать отображение между множеством порядковых номеров букв русского алфавита и множеством букв. Реализуйте операторы отображения. Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 9.

Реализовать множество наименований промтоваров на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать 2-3 дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством порядковых номеров букв латинского алфавита и множеством букв. Реализуйте операторы отображения: инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Вариант 10.

Реализовать множество фамилий студентов на основе двусвязного списка. Реализовать операторы: добавить элемент, удалить элемент, принадлежность элемента множеству и операторы над двумя множествами: объединение, пересечение, разность.
Реализовать 3-4 дерево методом матрицы смежности. Создать методы: добавить узел, удалить узел, предок узла, сыновья узла.
Реализовать отображение между множеством предметов на курсе и множеством преподавателей. Реализуйте операторы отображения: инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, определение соответственных элементов, график отображения.

Лабораторная работа № 12

Рекурсии

Разработайте рекурсивный алгоритм, рисующий:

Оценить время выполнения алгоритма.

Вариант 1

к - концентрических окружностей