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

Что такое лист дерева?

1. AУзел без потомков
2. BУзел без родителя
3. CУзел ровно с одним потомком
4. DУзел с наибольшим значением

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

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

Что хранит отображение (map, словарь)?

1. AЗначения, отсортированные по размеру
2. BПары ключ–значение с уникальными ключами
3. CТолько значения в порядке вставки
4. DПары одинаковых ключей

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

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

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

1. Ai + 1 и i + 2
2. B2i + 1 и 2i + 2
3. C2i и 2i + 1
4. Di/2 и i/2 + 1

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

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

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

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

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

1. AMin-куча, перестраиваемая для каждого окна
2. BДек, хранящий индексы в порядке убывания значений
3. CОтсортированный массив, обновляемый сдвигами
4. DОдносвязный список элементов окна