12 - Деревья

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

2. Перечислите листья этого дерева.

	А, В, Д
	Б, Г, Д
	В, Г, Д
	А, Б, Г
	это некорректный вопрос

4. Как называется дерево, в котором каждый узел может иметь не более двух сыновей? В ответе введите прилагательное.

Ответ:

5. Запишите арифметическое выражение, соответствующее этому дереву, в префиксной форме (без пробелов).

Ответ:

6. Запишите арифметическое выражение, соответствующее этому дереву, в постфиксной форме (без пробелов).

Ответ:

7. Выполните обход этого дерева в порядке «корень-левое-правое». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).

Ответ:

8. Выполните обход этого дерева в порядке «левое-корень-правое». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).

Ответ:

9. Выполните обход этого дерева в порядке «левое-правое-корень». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).

Ответ:

10. Какие деревья, изображённые на рисунке, могут служть деревьями поиска?

	а
	б
	в
	г

11. Сколько сравнений надо сделать в худшем случае, чтобы определить, есть ли в этом дереве поиска заданный элемент?

Ответ:

12. Какой порядок обхода надо использовать для дерева поиска, чтобы отсортировать данные в порядке убывания?

	левое - корень - правое
	левое - правое - корень
	корень - левое - правое
	правое - корень - левое
	правое - левое - корень

13. Дерево поиска строится из массива, содержащего 15 различных чисел. Какова высота полученного дерева?

Ответ:

14. Какую асимптотическую сложность имеет операция поиска в дереве поиска минимальной высоты?
	`O(log N)`
	`O(N)`
	`O(N²)`
	`O(N³)`
	`O(2^N)`