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

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

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

Как называется операция очереди, удаляющая элемент из начала?

1. AInsert
2. BEnqueue
3. CPush
4. DDequeue

Как элементы массива хранятся в памяти?

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

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. Alog₂ n
2. Bn (дерево превращается в связный список)
3. C1
4. D√n

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AСамый правый узел его левого поддерева
2. BВсегда его правый потомок
3. CВсегда его родитель
4. DСамый левый узел его правого поддерева

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

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
2. BМеняют его местами с корнем
3. CУдаляют всё поддерево
4. DПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ