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

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

1. An − 1
2. B2n
3. Cn + 1
4. Dn

В односвязном списке каждый узел содержит:

1. AДанные и индекс
2. BДанные и ссылки на все остальные узлы
3. CДанные и ссылку на следующий узел
4. DТолько данные

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

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

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AМножество без упорядочения
2. BСтек
3. CОчередь FIFO
4. DОчередь с приоритетом по минимуму

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

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

1. A2i + 1 и 2i + 2
2. Bi/2 и i/2 + 1
3. C2i и 2i + 1
4. Di + 1 и i + 2

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

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

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[1, 5, 8, 3]
2. B[1, 3, 8, 5]
3. C[3, 1, 8, 5]
4. D[1, 3, 5, 8]