15 - Деревья

1. Отметьте все правильные утверждения.
дерево - это рекурсивная структура данных
в дереве могут быть циклы (замкнутые пути)
каждый узел дерева может иметь не более двух сыновей
только один узел дерева не имеет предков
2. Перечислите листья этого дерева.
А, В, Д
Б, Г, Д
В, Г, Д
А, Б, Г
это некорректный вопрос
3. Сколько потомков имеет узел А?
Ответ: 
4. Как называется дерево, в котором каждый узел может иметь не более двух сыновей? В ответе введите прилагательное.
Ответ: 
5. Запишите арифметическое выражение, соответствующее этому дереву, в префиксной форме (без пробелов).
Ответ: 
6. Запишите арифметическое выражение, соответствующее этому дереву, в постфиксной форме (без пробелов).
Ответ: 
7. Выполните обход этого дерева в порядке «корень-левое-правое». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).
Ответ: 
8. Выполните обход этого дерева в порядке «левое-корень-правое». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).
Ответ: 
9. Выполните обход этого дерева в порядке «левое-правое-корень». В ответе введите последовательность меток узлов без пробелов (например, АБВГД).
Ответ: 
10. Какие деревья, изображённые на рисунке, могут служть деревьями поиска?
а
б
в
г
11. Сколько сравнений надо сделать в худшем случае, чтобы определить, есть ли в этом дереве поиска заданный элемент?
Ответ: 
12. Какой порядок обхода надо использовать для дерева поиска, чтобы отсортировать данные в порядке убывания?
левое - корень - правое
левое - правое - корень
корень - левое - правое
правое - корень - левое
правое - левое - корень
13. Дерево поиска строится из массива, содержащего 15 различных чисел. Какова высота полученного дерева?
Ответ: 
14. Какую асимптотическую сложность имеет операция поиска в дереве поиска минимальной высоты?
O(log N)
O(N)
O(N2)
O(N3)
O(2N)