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

В двоичном дереве поиска значения в левом поддереве узла:

1. AМеньше значения узла
2. BРасположены в случайном порядке
3. CРавны значению узла
4. DБольше значения узла

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AСтек
2. BХеш-множество
3. CГраф
4. DОчередь

Как называется операция очереди, удаляющая элемент из начала?

1. AEnqueue
2. BDequeue
3. CPush
4. DInsert

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AВсегда его правый потомок
2. BВсегда его родитель
3. CСамый левый узел его правого поддерева
4. DСамый правый узел его левого поддерева

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

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

1. A√n
2. B1
3. Cn (дерево превращается в связный список)
4. Dlog₂ n

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

1. AВысота равна ровно log₂ n
2. BВысота не превышает 2 log₂(n + 1)
3. CВысота не превышает n / 2
4. DВысота не превышает log₂ n + 1

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

1. AЧтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
2. BПотому что уменьшение вдвое при половинном заполнении привело бы к потере элементов
3. CЧтобы массив оставался отсортированным
4. DПотому что распределитель памяти может освобождать память только четвертями блока