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

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

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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BЛевое поддерево, затем узел, затем правое поддерево
3. CУзел, затем левое поддерево, затем правое поддерево
4. DПо уровням сверху вниз

Где находится наименьший элемент двоичной min-кучи?

1. AВ самом левом листе
2. BВ каком-то листе, который придётся искать
3. CВ корне
4. DВ последней позиции массива

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

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

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

Как вставляется новый элемент в двоичную кучу?

1. AЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
2. BЕго помещают в корень и опускают вниз
3. CЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
4. DВсю кучу перестраивают с нуля

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AMax-куча, упорядоченная по полустепени исхода
2. BМатрица смежности, фиксирующая, какие вершины уже удалены
3. CСтек всех посещённых рёбер
4. DОчередь (или любая коллекция) вершин с полустепенью захода 0