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

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

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

Что такое цикл в графе?

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

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

1. AУдаление головного элемента
2. BДоступ к элементу с индексом i
3. CЧтение первого элемента
4. DВставка в начало

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

1. A2^h+1 − 1
2. B2^h
3. C2h + 1
4. Dh²

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

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AОбхода графа
2. BОчереди фиксированного размера
3. CДвоичного дерева поиска
4. DХеш-функции

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
2. BМеняют его местами с корнем
3. CУдаляют всё поддерево
4. DЗаменяют его in-order преемником (или предшественником) и удаляют тот узел

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

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