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

Где находится наименьший элемент двоичной 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Подсчитывает, сколько ключей хранится

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

1. AO(E)
2. BO(V)
3. CO(log V)
4. DO(1)

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AВысоту O(log n) благодаря перебалансировке
2. BЧто ни у одного узла нет двух потомков
3. CХранение ключей в порядке вставки
4. DПоиск за константное время в любом случае

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 6
2. BВ индексе 0
3. CВ индексе 4
4. DВ индексе 3

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

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

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

1. AОдин только обход по уровням
2. BПрямой и симметричный (preorder и inorder)
3. CПрямой и обратный (preorder и postorder)
4. DОдин только прямой