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

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

1. APush
2. BPeek
3. CPop
4. DEnqueue

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AОчередь
2. BХеш-множество
3. CГраф
4. DСтек

Что такое свойство max-кучи?

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(log n) из-за двоичного поиска
2. BO(n²), потому что каждый элемент сдвигается n раз
3. CO(1), потому что индекс известен
4. DO(n), потому что последующие элементы нужно сдвинуть

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A40
2. B20
3. C70
4. D50

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

1. AПравый поворот в левом потомке, затем левый поворот в узле
2. BЛевый поворот в левом потомке, затем правый поворот в узле
3. CОдиночный правый поворот в узле
4. DОдиночный левый поворот в узле

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

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