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

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

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

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

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Стек вызовов
4. DХеш-таблицу функций

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

1. A2i и 2i + 1
2. Bi/2 и i/2 + 1
3. Ci + 1 и i + 2
4. D2i + 1 и 2i + 2

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AОчередь FIFO последних k значений
2. BMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
3. CОтсортированный массив всех n значений
4. DMax-куча размера k, корень которой заменяется, когда приходит меньшее значение