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

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

1. AКратчайший путь до каждой другой вершины
2. BСтрока из V булевых значений
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Что ни у одного узла нет двух потомков
3. CВысоту O(log n) благодаря перебалансировке
4. DХранение ключей в порядке вставки

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AОчередь с приоритетом по минимуму
2. BСтек
3. CМножество без упорядочения
4. DОчередь FIFO

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

1. AЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
2. BОна работает за O(n) на любых входных данных
3. CОна устойчива и требует O(n) дополнительной памяти
4. DОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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