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

Что такое взвешенный граф?

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

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

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

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

1. An + 1
2. Bn
3. Cn − 1
4. D2n

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ отсортированном массиве
2. BВ двусвязном списке
3. CВ односвязном списке
4. DВ динамическом массиве

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы хранить число элементов
2. BЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
3. CЧтобы упростить код, убрав особые случаи в голове или хвосте
4. DЧтобы список был отсортирован

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AСамый правый узел его левого поддерева
2. BСамый левый узел его правого поддерева
3. CВсегда его родитель
4. DВсегда его правый потомок

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

1. AОн не использует дополнительной памяти
2. BОжидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд
3. CГарантированный поиск за O(1), потому что каждый узел хранит указатель на каждый другой узел
4. DОн хранит ключи без упорядочения