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

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

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

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

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

Граф состоит из:

1. AТолько ключей и хешей
2. BВершин (узлов), соединённых рёбрами
3. CТолько корня и листьев
4. DСтрок и столбцов

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

1. AМетод цепочек (separate chaining)
2. BДвойное хеширование
3. CЛинейное пробирование
4. DКвадратичное пробирование

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AХранение ключей в порядке вставки
2. BВысоту O(log n) благодаря перебалансировке
3. CЧто ни у одного узла нет двух потомков
4. DПоиск за константное время в любом случае

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

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

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[3, 1, 8, 5]