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

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

1. APush
2. BPop
3. CPeek
4. DEnqueue

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

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

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

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AХеш-функции
2. BДвоичного дерева поиска
3. CОбхода графа
4. DОчереди фиксированного размера

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе 2i + 1
3. CВ индексе ⌊(i − 1) / 2⌋
4. DВ индексе ⌊i / 2⌋ + 1

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

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

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

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

Дерево отрезков (segment tree) обычно используют для:

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