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

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AВставка в начало
2. BЧтение последнего элемента по индексу
3. CОпределение длины массива фиксированного размера
4. DДоступ к 5-му элементу

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

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

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

1. AEnqueue
2. BInsert
3. CDequeue
4. DPush

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

1. A20
2. B40
3. C70
4. D50

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

1. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 2 5 1 3
4. D4 5 2 3 1

Как найти минимальный ключ в двоичном дереве поиска?

1. AОбойти все листья и сравнить их
2. BИдти от корня по правым потомкам, пока правого потомка не окажется
3. CИдти от корня по левым потомкам, пока левого потомка не окажется
4. DПосмотреть только на корень

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

1. AЗапросы префиксных сумм и обновления отдельного элемента
2. BПоиск медианы за O(1)
3. CВставку элементов в любую позицию
4. DСортировку массива и двоичный поиск

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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