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

Высота дерева обычно определяется как:

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Сбалансированное двоичное дерево поиска
4. DНеотсортированный связный список

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

1. AO(V + E)
2. BO(V × E)
3. CO(E²)
4. DO(V²)

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A70
2. B40
3. C80
4. D60

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

1. AO(α(n))
2. BO(log n)
3. CO(1)
4. DO(n)