Структуры данных: лист заданий с ответами

Что определяет двоичное дерево?

1. AВ дереве ровно два уровня
2. BУ каждого узла не более двух потомков
3. CУ каждого узла ровно два потомка
4. DКаждый узел хранит двоичное число

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

1. AОчередь
2. BХеш-таблица
3. CСвязный список
4. DСтек

Что такое свойство max-кучи?

1. AВсе листья содержат максимальный ключ
2. BКлючи отсортированы слева направо
3. CКлюч каждого левого потомка больше или равен ключу его правого соседа
4. DКлюч каждого родителя больше или равен ключам его потомков

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 5 2 3 1

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D1 2 3 4 5

Как найти минимальный ключ в двоичном дереве поиска?

1. AПосмотреть только на корень
2. BИдти от корня по левым потомкам, пока левого потомка не окажется
3. CИдти от корня по правым потомкам, пока правого потомка не окажется
4. DОбойти все листья и сравнить их

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

1. AO(n)
2. BO(log n)
3. CO(α(n))
4. DO(1)

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A60
2. B80
3. C40
4. D70