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

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

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

Хеш-таблица (hash table) хранит данные в виде:

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

Что хранит отображение (map, словарь)?

1. AТолько значения в порядке вставки
2. BПары ключ–значение с уникальными ключами
3. CЗначения, отсортированные по размеру
4. DПары одинаковых ключей

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

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

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. AМаксимума нет
2. B0,5
3. C2
4. D1

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AХранить front и rear в одной переменной
2. BВсегда очищать буфер, когда front равен rear, так что состояние — пустой
3. CДелать размер буфера степенью двойки
4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной