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

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

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

Глубина узла в дереве — это:

1. AЧисло рёбер от этого узла до самого глубокого листа
2. BЧисло узлов в его поддереве
3. CЧисло потомков этого узла
4. DЧисло рёбер от корня до этого узла

Какая структура данных используется для обхода дерева по уровням (level-order)?

1. AОчередь
2. BСтек
3. CХеш-таблица
4. DОчередь с приоритетом

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

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

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

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

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

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

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

1. AПоиск медианы за O(1)
2. BСортировку массива и двоичный поиск
3. CВставку элементов в любую позицию
4. DЗапросы префиксных сумм и обновления отдельного элемента

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

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