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

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

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

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

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

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

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

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

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

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

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

Как работает extract-min в двоичной min-куче?

1. AПоследний элемент перемещают в корень и опускают вниз (sift down)
2. BИщут новый минимум среди всех листьев
3. CУдаляют последний элемент массива
4. DУдаляют корень и сдвигают все элементы на одну позицию влево

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

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