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

Что такое ориентированный граф?

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AВставка в начало
2. BУдаление головного элемента
3. CЧтение первого элемента
4. DДоступ к элементу с индексом i

В двоичном дереве поиска значения в левом поддереве узла:

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

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

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

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