⚙️ Алгоритмы  ·  20 вопросов  ·  ~40 мин  ·  ⏱ Таймер 40:00  ·  Средний  · 

Деревья и двоичные деревья поиска

Дерево не гарантирует быстрый поиск само по себе: важны порядок ключей и высота. Тест предлагает считать глубину и листья, восстанавливать обходы, искать глобальное нарушение BST, прослеживать вставку и понимать, как поворот меняет ссылки при балансировке.

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Сколько листьев в дереве?
Python
class Node:
    def __init__(self, v, left=None, right=None):
        self.v, self.left, self.right = v, left, right

root = Node(1,
    Node(2, Node(4), Node(5)),
    Node(3, None, Node(6)))
Вопрос 2 из 20
Какую высоту вернёт функция, если высота пустого дерева равна 0?
Python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = Node(1, right=Node(2, right=Node(3, right=Node(4))))
print(height(root))
Вопрос 3 из 20
Если глубина корня равна 0, какова глубина его внука?
Вопрос 4 из 20
Сколько узлов посетит функция size?
Python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

root = Node(1,
    Node(2, Node(4), Node(5)),
    Node(3, Node(6), Node(7)))
print(size(root))
Вопрос 5 из 20
Какое максимальное число узлов может быть на уровне d бинарного дерева, если корень на уровне 0?
N_d\le 2^d
Вопрос 6 из 20
Какую последовательность напечатает прямой обход этого дерева?
Python
class Node:
    def __init__(self, value, left=None, right=None):
        self.v = value
        self.left = left
        self.right = right

root = Node(1,
    Node(2, None, Node(4)),
    Node(3, Node(5), None)
)

def walk(node):
    if node is None:
        return
    print(node.v, end=' ')
    walk(node.left)
    walk(node.right)

walk(root)
Вопрос 7 из 20
Какую последовательность напечатает симметричный обход?
Python
tree = {
    1: (2, 3),
    2: (None, 4),
    3: (5, None),
    4: (None, None),
    5: (None, None),
}

def inorder(v):
    if v is None:
        return
    left, right = tree[v]
    inorder(left)
    print(v, end=' ')
    inorder(right)

inorder(1)
Вопрос 8 из 20
Какой обход естественно использовать для удаления всего дерева снизу вверх?
Вопрос 9 из 20
Какой список получится после обхода дерева по уровням?
Python
from collections import deque

children = {
    1: (2, 3),
    2: (None, 4),
    3: (5, None),
    4: (None, None),
    5: (None, None),
}

q = deque([1])
out = []
while q:
    v = q.popleft()
    out.append(v)
    for child in children[v]:
        if child is not None:
            q.append(child)
print(out)
Вопрос 10 из 20
Можно ли однозначно восстановить произвольное бинарное дерево только по симметричному обходу с уникальными значениями?
Вопрос 11 из 20
Какой путь пройдёт поиск числа 6?
Python
tree = {
    8: (3, 10),
    3: (None, 6),
    6: (None, None),
    10: (9, None),
    9: (None, None),
}

node = 8
path = []
x = 6
while node is not None and node != x:
    path.append(node)
    left, right = tree[node]
    node = left if x < node else right
if node is not None:
    path.append(node)
print(path)
Вопрос 12 из 20
Куда вставится 7?
Python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Node(8,
    Node(3, None, Node(6)),
    Node(10)
)
value = 7
node = root
while True:
    if value < node.value:
        if node.left is None:
            break
        node = node.left
    else:
        if node.right is None:
            break
        node = node.right
# Вопрос: какая свободная ссылка будет использована?
Вопрос 13 из 20
Почему проверка «каждый левый ребёнок меньше родителя, каждый правый больше» недостаточна для BST?
Вопрос 14 из 20
Корректно ли это дерево как двоичное дерево поиска, и почему?
Python
# Узел записан как (значение, левое поддерево, правое поддерево).
root = (
    10,
    (5, None, None),
    (15, (6, None, None), (20, None, None)),
)
Вопрос 15 из 20
Что даёт симметричный обход корректного дерева поиска с различными ключами?
Вопрос 16 из 20
Какова высота BST после вставки 1,2,3,4,5 в таком порядке без балансировки, если высота считается в узлах?
Python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))

root = None
for value in [1, 2, 3, 4, 5]:
    root = insert(root, value)
print(height(root))
Вопрос 17 из 20
Что станет новым корнем поддерева после левого поворота вокруг x?
Python
# До поворота:
# x.right = y
# y.left = B
# y.right = C
#
# Выполняется левый поворот вокруг x.
Вопрос 18 из 20
Какова сложность поиска в вырожденном BST из n узлов?
O(n)
Вопрос 19 из 20
Какой фактор баланса у узла, если высота левого поддерева 4, правого 2?
Python
left_height = 4
right_height = 2
balance = left_height - right_height
print(balance)
Вопрос 20 из 20
Что гарантирует AVL-дерево?
h=O(\log n)

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу