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

Сколько рёбер в дереве с n узлами?

1. A2n
2. Bn − 1
3. Cn + 1
4. Dn

Что делает хеш-функция в хеш-таблице?

1. AСортирует ключи в таблице
2. BШифрует значения в таблице
3. CОтображает ключ в индекс таблицы
4. DПодсчитывает, сколько ключей хранится

Что содержит каждый узел двусвязного списка?

1. AДанные, указатель на следующий узел и указатель на предыдущий узел
2. BДве копии данных и один указатель
3. CДанные и только указатель на следующий узел
4. DДанные и два указателя: один на следующий узел и один на узел после него

Что верно для матрицы смежности неориентированного графа?

1. AВ каждой строке ровно одна 1
2. BНа её главной диагонали всегда стоят единицы
3. CОна всегда верхнетреугольная
4. DОна симметрична относительно главной диагонали

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

1. AСтек
2. BТолько хеш-таблицу
3. CКучу
4. DОчередь

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

1. AB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
2. BB+ деревья не нужно балансировать
3. CB+ деревья хранят данные только в корне
4. DВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

1. AO(log n)
2. BO(m)
3. CO(n)
4. DO(1 + α), где α = n / m