Домашнее задание № 2 Нелинейные структуры данных

Цель работы – познакомиться с нелинейными структурами данных и некоторыми алгоритмами поиска, научиться решать задачи с использованием деревьев и графов, понять взаимосвязь алгоритма обработки структур данных с их внутренним представлением.

Постановка задачи

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

Задания могут быть выполнены на трех уровнях сложности.

1. Низкий. Структуры хранения для представления графа и дерева – по выбору студента.

2. Средний. Граф реализовать двумя способами (матрицей смежности или весов и списками смежности). Реализация дерева – по выбору студента (выбор обосновать!). Данные хотя бы для одной задачи считывать из файла.

3. Повышенный. Граф реализовать двумя способами (матрицей смежности или весов и списками смежности). Реализация дерева – по выбору студента (выбор обосновать!) Все структуры данных оформить в виде классов. Все данные считывать из файлов.

Варианты заданий

Вариант 1.

1. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города А в город В (который может проходить как по железным, так и по шоссейным дорогам), и места пересадок с одного вида транспорта на другой на этом пути.

2. Построить дерево бинарного поиска и реализовать рекурсивную функцию его копирования. Обойти полученное дерево в симметричном порядке.

Вариант 2.

1. В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной S+P, где S – сумма длин дорог пути, а P – сумма пошлин проезжаемых дорог.

2. Описать функцию, которая для заданного N строит почти полное строго бинарное дерево с количеством уровней N, где на каждом уровне i располагаются узлы, информационные части которых равны i. Обойти построенное дерево в симметричном и прямом порядках.

Вариант 3.

1. По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.

2. По данным, хранящимся в файле, построить дерево бинарного поиска и вычислить его высоту. Определить с помощью полученного дерева, есть ли в файле числа, вводимые с клавиатуры (количество чисел запрашивается перед их вводом), отсутствующие числа добавить в конец файла.

Вариант 4.

1. Определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.

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

Вариант 5.

1. Найти центр взвешенного орграфа.

2. Построить сбалансированное дерево бинарного поиска. Обойти полученное дерево в симметричном и прямом порядках.

Вариант 6.

1. Известно, что заданный граф – не дерево. Проверить, можно ли удалить из него одну вершину (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево.

2. Описать функцию, которая для заданного N строит полное двоичное дерево с количеством уровней N, где на каждом уровне i располагаются узлы, информационные части которых равны N-i. Вывести на экран списки значений узлов дерева, получаемые при его обходе в симметричном и обратном порядке. Изобразить полученное дерево на экране в виде иерархической структуры, используя поперечный обход дерева.

Вариант 7.

1. Из графа удалить все вершины, из которых недостижима заданная.

2. Построить дерево бинарного поиска. Определить, является ли это дерево сбалансированным. Обойти полученное дерево в симметричном, прямом и обратном порядках.

Вариант 8.

1. Найти диаметр графа, т.е. максимум расстояний между всеми парами его вершин.

2. Построить лес цифрового (символьного) поиска. Использовать реализацию общего дерева, в которой каждый узел представляет собой запись с информационным полем и заранее определенным количеством указателей на сыновей. Проверить с помощью этого леса, есть ли среди указанных чисел число N, введенное с клавиатуры.

Вариант 9.

1. Найти все вершины графа, недостижимые от заданной его вершины

2. Построить лес цифрового (символьного) поиска. Использовать реализацию леса в виде бинарного дерева. Проверить с помощью этого леса, есть ли среди указанных чисел число N, введенное с клавиатуры.

Вариант 10.

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

2. Построить дерево бинарного поиска и реализовать рекурсивную функцию его копирования. Обойти полученное дерево в симметричном порядке.

Вариант 11.

1. Задана система односторонних дорог. Найти путь, соединяющий города А и В, и не проходящий через заданное множество городов.

2. По числам, хранящимся в бинарном файле, построить дерево бинарного поиска. Сохранить неповторяющиеся данные из исходного файла в новом файле в убывающем порядке. Определить, на сколько в процентном отношении полученный файл меньше исходного.

Вариант 12.

1. Задан орграф с циклами. Проверить, можно ли удалить одну вершину так, чтобы в полученном орграфе не было циклов.

2. Описать функцию, которая для заданного N строит полное двоичное дерево с количеством уровней N, где на каждом уровне i располагаются узлы, информационные части которых равны i+1. Вывести на экран списки значений узлов дерева, получаемые при его обходе в прямом и симметричном порядке. Изобразить полученное дерево на экране в виде иерархической структуры, используя обход дерева по уровням.

Вариант 13.

1. Имеются n городов. Некоторые из них соединены дорогами известной длины. Определить, в каком из городов компании нужно построить склад, чтобы доставка товаров по городам осуществлялась с наименьшими транспортными расходами. Считать, что товары распределяются по городам равномерно и дорожные условия одинаковые.

2. Построить дерево бинарного поиска. Определить, является ли оно AVL-деревом. Обойти полученное дерево в симметричном и прямом порядках.

Вариант 14.

1. В орграфе найти все стоки, то есть вершины, в которые только входят дуги, и истоки, т. е. вершины, из которых дуги только выходят. Обойти орграф методом поиска в глубину и определить минимально возможное количество деревьев в глубинном остовном лесу этого графа.

2. Построить почти полное бинарное дерево. Обойти полученное дерево в симметричном и поперечном порядках.

Вариант 15.

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

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

Вариант 16.

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

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

Вариант 17.

1. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Определить N-периферию для заданного N.

2. Построить лес цифрового поиска. Использовать реализацию общего дерева в виде бинарного дерева. Проверить с помощью этого леса, есть ли среди указанных чисел число N, введенное с клавиатуры.

Вариант 18.

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

2. Вывести на экран бор, построенный по числам, хранящимся в бинарном файле. Определить с помощью этого бора, есть ли среди указанных чисел число N, введенное с клавиатуры.

Вариант 19.

1. Имеются n городов. Некоторые из них соединены дорогами известной длины. Хватит ли дальнобойщику, выезжающему из города А, топлива, чтобы доехать до города В, если в баке х л бензина, а расход у л на 100 км.

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

Вариант 20.

1. Имеются n городов. Некоторые из них соединены дорогами известной длины. Определить, из каждого ли города можно попасть в остальные.

2. Вывести на экран бор, построенный по числам, хранящимся в текстовом файле. Определить с помощью этого бора, есть ли среди указанных чисел число N, введенное с клавиатуры.