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

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

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

Высота дерева обычно определяется как:

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

Что такое дек (deque, двусторонняя очередь)?

1. AДве отдельные очереди в одном массиве
2. BОчередь, отсортированная по приоритету
3. CСтруктура, допускающая вставку и удаление с обоих концов
4. DОчередь, допускающая удаление только с конца

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

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

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

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

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

1. AСтек
2. BДвоичное дерево поиска
3. CХеш-таблица
4. DОчередь

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

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AДелать размер буфера степенью двойки
2. BВсегда очищать буфер, когда front равен rear, так что состояние — пустой
3. CХранить front и rear в одной переменной
4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной