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

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

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AУдаление головного элемента
2. BДоступ к элементу с индексом i
3. CЧтение первого элемента
4. DВставка в начало

Какая структура данных используется для обхода дерева по уровням (level-order)?

1. AХеш-таблица
2. BСтек
3. CОчередь с приоритетом
4. DОчередь

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A4 2 5 1 3
2. B1 2 3 4 5
3. C1 2 4 5 3
4. D4 5 2 3 1

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

1. A(i + 1) mod n
2. Bi + 1
3. C(i − 1) mod n
4. D2i + 1

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

1. AСтек вызовов
2. BДвоичное дерево поиска кадров
3. CОчередь памяти кучи
4. DХеш-таблицу функций

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(α(n)), обратная функция Аккермана, практически константа
2. BРовно O(log n)
3. CO(n)
4. DO(n²)

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

1. AВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
2. BB+ деревья хранят данные только в корне
3. CB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
4. DB+ деревья не нужно балансировать