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

Что такое узлы-братья (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Число рёбер от этого узла до самого глубокого листа

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

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

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AДвоичная куча рёбер
2. BОдин отсортированный массив вершин
3. CСписки смежности
4. DМатрица смежности

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A60
2. B70
3. C40
4. D80

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

1. AОтсортировать список и искать повторы
2. BДвигать один указатель на один шаг, а другой на два и проверять, встретятся ли они
3. CСчитать узлы, пока счёт не превысит поле длины списка
4. DХранить каждый посещённый узел в хеш-множестве