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

Что такое лист дерева?

1. AУзел с наибольшим значением
2. BУзел ровно с одним потомком
3. CУзел без родителя
4. DУзел без потомков

Какова определяющая особенность множества как абстрактного типа данных?

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

Что делает хеш-функция в хеш-таблице?

1. AПодсчитывает, сколько ключей хранится
2. BОтображает ключ в индекс таблицы
3. CСортирует ключи в таблице
4. DШифрует значения в таблице

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

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

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A2
2. BМаксимума нет
3. C0,5
4. D1

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

1. AОдин только прямой
2. BПрямой и обратный (preorder и postorder)
3. CПрямой и симметричный (preorder и inorder)
4. DОдин только обход по уровням

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

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