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

Что делает операция peek (или top) стека?

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

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

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

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

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(n), где n — число слов
2. BO(log n), где n — число слов
3. CO(L), независимо от числа хранимых слов
4. DO(L × n)

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

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

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

1. AO(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), где α = n / m

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

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