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

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

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

Что такое узлы-братья (siblings) в дереве?

1. AУзел и его родитель
2. BУзлы с общим родителем
3. CУзлы на одной глубине в разных поддеревьях
4. DУзлы без потомков

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

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

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

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

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

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. Ai/2 и i/2 + 1
2. Bi + 1 и i + 2
3. C2i + 1 и 2i + 2
4. D2i и 2i + 1

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A70
2. B60
3. C80
4. D40

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

1. AДек, хранящий индексы в порядке убывания значений
2. BОтсортированный массив, обновляемый сдвигами
3. CMin-куча, перестраиваемая для каждого окна
4. DОдносвязный список элементов окна