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

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

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

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

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

Хеш-таблица (hash table) хранит данные в виде:

1. AСтроки фиксированной длины
2. BДерева с упорядоченными ключами
3. CТолько отсортированного списка
4. DПар ключ–значение, расположение которых определяет хеш-функция

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(log n) из-за двоичного поиска
2. BO(1), потому что индекс известен
3. CO(n), потому что последующие элементы нужно сдвинуть
4. DO(n²), потому что каждый элемент сдвигается n раз

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. Alog₂ n
2. B1
3. Cn (дерево превращается в связный список)
4. D√n

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A11
2. B24
3. C10
4. D14

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

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

Почему B-деревья используются в базах данных и файловых системах?

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