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

В двоичном дереве поиска значения в левом поддереве узла:

1. AБольше значения узла
2. BРасположены в случайном порядке
3. CМеньше значения узла
4. DРавны значению узла

Как элементы массива хранятся в памяти?

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

Что такое узлы-братья (siblings) в дереве?

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе ⌊i / 2⌋ + 1
2. BВ индексе i − 1
3. CВ индексе ⌊(i − 1) / 2⌋
4. DВ индексе 2i + 1

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

1. Ah²
2. B2^h
3. C2^h+1 − 1
4. D2h + 1

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

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

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

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

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