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

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

1. AОно хранит элементы без повторений
2. BОно хранит пары ключ–значение
3. CОно хранит элементы в отсортированном порядке
4. DОно допускает доступ только с одного конца

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

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

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

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

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

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

Как вставляется новый элемент в двоичную кучу?

1. AЕго помещают в корень и опускают вниз
2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
4. DВсю кучу перестраивают с нуля

Сколько памяти занимает матрица смежности графа с V вершинами?

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

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

1. A60
2. B40
3. C80
4. D70

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

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