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

Глубина узла в дереве — это:

1. AЧисло узлов в его поддереве
2. BЧисло рёбер от корня до этого узла
3. CЧисло рёбер от этого узла до самого глубокого листа
4. DЧисло потомков этого узла

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BПо уровням сверху вниз
3. CУзел, затем левое поддерево, затем правое поддерево
4. DЛевое поддерево, затем узел, затем правое поддерево

Сколько рёбер в дереве с n узлами?

1. An − 1
2. Bn
3. Cn + 1
4. D2n

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AМассивы требуют меньше инструкций для сравнения значений
2. BОбход массива занимает в сумме O(1), а связного списка — O(n)
3. CЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
4. DСвязные списки всегда хранят элементы на диске

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A2i + 1
2. B(i + 1) mod n
3. Ci + 1
4. D(i − 1) mod n

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. Ai/2 и i/2 + 1
2. Bi + 1 и i + 2
3. C2i + 1 и 2i + 2
4. D2i и 2i + 1

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

1. AСтоимость O(n) чтения значения по ключу
2. BНеобходимость хранить ключи в таблице
3. CНеобходимость в хеш-функции
4. DПервичную кластеризацию, при которой образуются длинные серии занятых ячеек

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AПрямой и обратный (preorder и postorder)
2. BПрямой и симметричный (preorder и inorder)
3. CОдин только обход по уровням
4. DОдин только прямой