Лабораторные работы выполняются по вариантам. Выбор варианта осуществляется по следующей формуле:

V = (N × K) div 100,

где V — искомый номер варианта,

N — общее количество вариантов, div — целочисленное деление,

при V = 0 выбирается максимальный вариант, K — код варианта.

Каждая лабораторная работа предполагает написание программы на языке программирования C/C++, предназначенной для решения определенной задачи в соответствии с выбранным вариантом.

Программные среды, поддерживающие языки программирования C/C++, а также ссылки для бесплатного их скачивания, приведены ниже.

1. Microsoft Visual Studio Community 2015 [Ссылка для скачивания:]

https://www.microsoft.com/ru-ru/download/details.aspx?id=48146

2. Dev-C++

[Ссылка для скачивания:] http://sourceforge.net/projects/orwelldevcpp/

3. Code Blocks v 13.12 [Ссылка для скачивания:]

http://code-blocks.ru.uptodown.com/

Результатом выполнения лабораторной работы будет являться написанная на языке C/C++ программа, реализующая решение индивидуального задания, а также приложенный к ней отчет. Отчет по лабораторной работе должен включать в себя следующие компоненты:

1. Титульный лист.

2. Тема работы.

3. Цель работы.

4. Индивидуальное задание.

5. Алгоритм решения задачи.

6. Результаты работы программы.

7. Выводы.

Приложение А. Листинг программы.

Рекомендуемый порядок выполнения лабораторных работ:

1. Изучить теоретический материал по теме лабораторной работы, представленный в учебном пособии [1].

2. Составить алгоритм решения поставленной задачи.

3. Написать программу на языке C/C++.

4. Отладить и протестировать программу на различных наборах входных данных.

5. Написать отчет по лабораторной работе.

ЛАБОРАТОРНАЯ РАБОТА № 1 «БИНАРНЫЕ ДЕРЕВЬЯ»

Вариант № 1

Задать последовательность чисел. Построить бинарное дерево, содержащее эти числа. Произвести обход дерева сверху вниз и вывести результат обхода на экран. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 2

Дана последовательность чисел. Построить бинарное дерево, содержащее эти числа. Произвести обход дерева слева направо и вывести результаты на экран. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 3

Дана последовательность чисел. Построить бинарное дерево, содержащее эти числа. Произвести обход дерева справа налево и вывести результаты на экран. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 4

Даны две последовательности чисел. Построить бинарное дерево, содержащее числа первой последовательности. Для каждого числа второй последовательности узнать, входит ли оно в дерево. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 5

Дана последовательность чисел. Написать программу, которая формирует бинарное дерево, выводит построенное дерево на экран и подсчитывает число вершин на n-ом уровне сформированного дерева. Корень считать вершиной 0-ого уровня. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 6

Дана последовательность чисел. Построить бинарное дерево поиска, содержащее эти числа. Произвести обход дерева слева направо. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 7

Дана последовательность чисел, написать программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран и подсчитывает число вершин на n-ом уровне сформированного дерева. Корень считать вершиной 0-ого уровня. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 8

Дана последовательность чисел. Построить бинарное дерево поиска, содержащее эти числа. Для числа, введённого с клавиатуры, сказать, присутствует ли оно в дереве. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 9

Дана последовательность чисел. Построить бинарное дерево, содержащее эти числа. Удалить из дерева число, введённое с клавиатуры, и вывести оставшиеся числа в дереве. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 10

Дана последовательность чисел. Построить бинарное дерево поиска, содержащее эти числа. Для числа, введённого с клавиатуры, произвести удаление из дерева, вывести оставшиеся числа обходом слева направо. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 11

Дана последовательность чисел, написать программу, которая формирует АВЛ-дерево, выводит построенное дерево на экран и подсчитывает число вершин на n-ом уровне сформированного дерева. Корень считать вершиной 0-ого уровня. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 12

Дана последовательность чисел. Написать программу формирования и вывода бинарного дерева на экран. Найти в построенном бинарном дереве все вершины, для которых выполняется условие: количество потомков в левом поддереве отличается от количества потомков в правом поддереве на 1. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 13

Дана последовательность чисел. Написать программу формирования и вывода бинарного дерева на экран. Для построенного дерева вывести на экран только элементы, являющиеся листьями. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 14

Задать последовательность чисел. Написать программу, выполняющую построение и вывод бинарного дерева на экран. Для построенного дерева найти все вершины, имеющие поддеревья одинаковой высоты, и для каждой из этих вершин вывести список потомков. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 15

Задать последовательность чисел. Написать программу, выполняющую построение и вывод бинарного дерева поиска на экран. Для построенного дерева вывести на экран все элементы, находящиеся на k-ом уровне, где число k задается с клавиатуры. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 16

Дана последовательность чисел. Написать программу, выполняющую построение и вывод АВЛ-дерева на экран. Для построенного дерева вывести на экран только нечетные элементы, находящиеся на k-ом уровне, где число k задается с клавиатуры. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 17

Задать последовательность чисел. Написать программу, выполняющую построение и вывод АВЛ-дерева на экран. Для построенного дерева найти значения максимального, минимального, среднего арифметического значения элементов. Реализовать функцию добавления нового элемента в АВЛ-дерево. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 18

Дана последовательность чисел. Написать программу, выполняющую построение и вывод АВЛ-дерева на экран. Для построенного дерева реализовать функцию поиска элемента по указанному с клавиатуры значению. Реализовать функцию удаления найденного элемента из АВЛ-дерева. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 19

Задать последовательность чисел. Написать программу, выполняющую построение и вывод бинарного дерева на экран. Для построенного дерева реализовать функцию удаления поддерева, корнем которого является узел с номером, введенным с клавиатуры. После выполнения программы очистить память, занятую древовидной структурой.

Вариант № 20

Дана последовательность чисел. Написать программу, выполняющую построение и вывод АВЛ-дерева на экран. Для построенного дерева реализовать функцию нахождения пути от корня до вершины с номером k, где k вводится с клавиатуры. После выполнения программы очистить память, занятую древовидной структурой.

ЛАБОРАТОРНАЯ РАБОТА № 2 «ГРАФЫ»

Вариант № 1

Используя алгоритм Дейкстры, найти длины кратчайших путей во взвешенном неориентированном графе от заданной вершины до всех остальных. Граф задать в текстовом файле матрицей весов.

Вариант № 2

Для заданной с клавиатуры начальной вершины найти и вывести Эйлеров путь в неориентированном графе. Граф задать в текстовом файле списками смежности.

Вариант № 3

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

Вариант № 4

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

Вариант № 5

Используя алгоритм Дейкстры, найти длины кратчайших путей во взвешенном ориентированном графе от заданной вершины до всех остальных. Граф задать в текстовом файле матрицей весов.

Вариант № 6

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

Вариант № 7

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

Вариант № 8

Найти длины кратчайших путей в неориентированном графе, все рёбра которого имеют единичный вес, от заданной вершины до всех остальных. Начальную вершину ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций.

Вариант № 9

Найти и вывести кратчайший путь в ориентированном графе, все дуги которого имеют единичный вес, между двумя заданными вершинами. Начальную и конечную вершины ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций.

Вариант № 10

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

Вариант № 11

Используя алгоритм Дейкстры, найти кратчайший путь между двумя заданными вершинами во взвешенном неориентированном графе. Начальную и конечную вершины пути ввести с клавиатуры. Граф задать в текстовом файле матрицей весов.

Вариант № 12

Построить стягивающее дерево неориентированного графа методом поиска в глубину и вывести список рёбер дерева. Граф задать в текстовом файле списком рёбер.

Вариант № 13

Найти длины кратчайших путей в ориентированном графе, все дуги которого имеют единичный вес, от заданной вершины до всех остальных. Начальную вершину ввести с клавиатуры. Граф задать в текстовом файле матрицей смежности.

Вариант № 14

Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список рёбер дерева. Граф задать в текстовом файле матрицей инциденций.

Вариант № 15

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

Вариант № 16

Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список рёбер дерева. Граф задать в текстовом файле списками смежности.

Вариант № 17

Построить стягивающее дерево неориентированного графа методом поиска в глубину и вывести список рёбер дерева. Граф задать в текстовом файле матрицей смежности.

Вариант № 18

Найти и вывести кратчайший путь в неориентированном графе, все рёбра которого имеют единичный вес, между двумя заданными вершинами. Начальную и конечную вершины ввести с клавиатуры. Граф задать в текстовом файле матрицей смежности.

Вариант № 19

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

Вариант № 20

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