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

Как элементы массива хранятся в памяти?

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

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

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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

1. A1
2. Bn (дерево превращается в связный список)
3. Clog₂ n
4. D√n

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A2i + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. Di + 1

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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