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

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

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

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

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

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

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

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

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

Что верно для матрицы смежности неориентированного графа?

1. AОна всегда верхнетреугольная
2. BВ каждой строке ровно одна 1
3. CОна симметрична относительно главной диагонали
4. DНа её главной диагонали всегда стоят единицы

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

1. Ai + 1 и i + 2
2. B2i + 1 и 2i + 2
3. C2i и 2i + 1
4. Di/2 и i/2 + 1

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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