Файл: 15 Графы и деревья.pdf

Информатика

Преподаватель: Молчанова И.А.

№

Задача

Баллы

1

Описать

рекурсивную функцию

или

процедуру, которая

определяет, входит ли

2

элемент Е в дерево Т.

2

Используя

очередь

или стек описать процедуру и функции, необходимые для

2

присваивания параметру Е элемента из самого левого листа непустого дерева Т.

3

Используя очередь или стек описать процедуру и функции, необходимые для замены

2

в дереве Т всех отрицательных элементов на их абсолютные величины.

4

Описать процедуру copy(T, T1), которая строит Т1 - копию дерева Т.

3

5

Рекурсивно

и

нерекурсивно

описать

логическую

функциюequal(T1,

T2),

3

проверяющую на равенство деревья Т1 и Т2.

6

Используя

очередь

или стек описать процедуру и функции, необходимые для

3

нахождения в непустом дереве Т длины пути от корня дерева до ближайшей вершины

с элементом Е; если Е не входит в Т, за ответ принять -1.

7

Используя очередь или стек описать процедуру и функции, необходимые, чтобы

3

распечатать все элементы дерева Т по уровням.

8

N колец

сцеплены

между собой(задана

матрица A(n*n),

A(i,

j)=1 в случае,

если

5

кольца i и j сцеплены друг с другом и A(i, j)=0 иначе).

Удалить минимальное

количество колец так, чтобы получилась цепочка.

9

Имеется

N

городов.

Для каждой пары городов(I,J) можно построить дорогу,

5

соединяющую эти два города и не заходящие в другие города. Стоимость такой

дороги

A(I,J). Вне

городов дороги не пересекаются. Написать алгоритм для

нахождения самой дешевой системы дорог, позволяющей попасть из любого города в

любой другой. Результаты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только

тогда, когда дорогу, соединяющую города I и J, следует строить.

10

Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до

5

N. Каждая дорога определяется тройкой чиселдвумя номерами домовконцов

дороги и длиной дороги. В каждом доме живет по одному человеку. Найти точку -

место встречи всех людей, от которой суммарное расстояние до всех домов будет

минимальным. Если точка лежит на дороге, то указать номера домовконцов этой

дороги и расстояние от первого из этих домов. Если точка совпадает с домом, то

указать номер этого дома. Примечание: длины дорог - положительные целые числа.