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

Что такое коллизия в хеш-таблице?

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

Что определяет двоичное дерево?

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

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

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

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе ⌊(i − 1) / 2⌋
3. CВ индексе 2i + 1
4. DВ индексе ⌊i / 2⌋ + 1

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

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

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

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

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