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

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

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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AБинарное дерево
2. BСтек
3. CКуча
4. DОчередь

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

1. ADequeue
2. BEnqueue
3. CPush
4. DInsert

Как вставляется новый элемент в двоичную кучу?

1. AВсю кучу перестраивают с нуля
2. BЕго помещают в корень и опускают вниз
3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
4. DЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи

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

1. A2i + 1 и 2i + 2
2. Bi + 1 и i + 2
3. C2i и 2i + 1
4. Di/2 и i/2 + 1

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

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

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AСтек всех посещённых рёбер
2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
3. CMax-куча, упорядоченная по полустепени исхода
4. DМатрица смежности, фиксирующая, какие вершины уже удалены