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

Что хранится для каждой вершины в представлении графа списками смежности?

1. AСписок соседних вершин
2. BСтрока из V булевых значений
3. CКратчайший путь до каждой другой вершины
4. DОбщее число рёбер графа

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

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

Что определяет двоичное дерево?

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

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

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D4 2 5 1 3

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

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

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

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

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

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

1. AO(V²)
2. BO(E log V)
3. CO(V + E)
4. DO(V)