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

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

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

Что такое цикл в графе?

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

Сколько рёбер в дереве с n узлами?

1. An + 1
2. Bn
3. C2n
4. Dn − 1

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AХранение ключей в порядке вставки
2. BВысоту O(log n) благодаря перебалансировке
3. CЧто ни у одного узла нет двух потомков
4. DПоиск за константное время в любом случае

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(log n) из-за двоичного поиска
2. BO(n), потому что последующие элементы нужно сдвинуть
3. CO(n²), потому что каждый элемент сдвигается n раз
4. DO(1), потому что индекс известен

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

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

1. AОтображение автоматически переносит ключ в новую корзину
2. BОтображение выбрасывает ошибку в момент изменения поля
3. CПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
4. DНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

1. AУдалённые ключи нужно хранить вечно из соображений безопасности, поэтому ячейки нельзя использовать повторно
2. BЭто делает таблицу отсортированной
3. CОсвобождение ячейки могло бы разорвать последовательность пробирования для других ключей
4. DНадгробия ускоряют хеширование