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

Где находится наименьший элемент двоичной min-кучи?

1. AВ корне
2. BВ самом левом листе
3. CВ каком-то листе, который придётся искать
4. DВ последней позиции массива

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

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

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

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

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

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(1)

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AВсегда его родитель
2. BВсегда его правый потомок
3. CСамый правый узел его левого поддерева
4. DСамый левый узел его правого поддерева

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

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

Вставка ключа в АВЛ-дерево делает левое поддерево узла слишком высоким, причём новый ключ попал в левое поддерево его левого потомка (случай левый–левый). Какое исправление применяется?

1. AОдиночный левый поворот в несбалансированном узле
2. BОдиночный правый поворот в несбалансированном узле
3. CПерекрашивание узла и его потомка
4. DЛевый поворот в потомке, затем правый поворот в узле