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

Что такое корень дерева?

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

Что хранится для каждой вершины в представлении графа списками смежности?

1. AСписок соседних вершин
2. BКратчайший путь до каждой другой вершины
3. CСтрока из V булевых значений
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Хеш-таблицу функций

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AОбхода графа
2. BДвоичного дерева поиска
3. CХеш-функции
4. DОчереди фиксированного размера

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

1. AO(n log n)
2. BO(n)
3. CO(log n)
4. DO(1)