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

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

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

Что такое лист дерева?

1. AУзел без родителя
2. BУзел ровно с одним потомком
3. CУзел с наибольшим значением
4. DУзел без потомков

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

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

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

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

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

1. A(i + 1) mod n
2. B(i − 1) mod n
3. Ci + 1
4. D2i + 1

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

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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