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

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

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

Что такое ориентированный граф?

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

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

1. ADequeue
2. BPush
3. CInsert
4. DEnqueue

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

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

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

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

1. AДвойное хеширование
2. BЛинейное пробирование
3. CМетод цепочек (separate chaining)
4. DКвадратичное пробирование

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

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

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