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

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

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

Как называется операция очереди, удаляющая элемент из начала?

1. ADequeue
2. BEnqueue
3. CPush
4. DInsert

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

1. AАдрес предыдущего узла
2. BNull (узла нет)
3. CЧисло узлов в списке
4. DАдрес первого узла

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A0,5
2. B2
3. C1
4. DМаксимума нет

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Как определить, есть ли цикл в односвязном списке, используя O(1) дополнительной памяти?

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

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

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