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

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

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

Как называется операция стека, добавляющая элемент на вершину?

1. APeek
2. BPop
3. CPush
4. DEnqueue

Что содержит указатель next последнего узла односвязного списка?

1. AАдрес предыдущего узла
2. BАдрес первого узла
3. CNull (узла нет)
4. DЧисло узлов в списке

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 4
2. BВ индексе 3
3. CВ индексе 6
4. DВ индексе 0

Что верно для матрицы смежности неориентированного графа?

1. AОна всегда верхнетреугольная
2. BНа её главной диагонали всегда стоят единицы
3. CВ каждой строке ровно одна 1
4. DОна симметрична относительно главной диагонали

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

1. AТолько двоичное дерево поиска
2. BТолько стек
3. CХеш-таблица в сочетании с двусвязным списком
4. DОдин отсортированный массив

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

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