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

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

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

Хеш-таблица (hash table) хранит данные в виде:

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

Какую структуру обычно используют для реализации очереди с приоритетом?

1. AСтек
2. BСтроку
3. CКучу
4. DНеупорядоченный односвязный список

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

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

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. Alog₂ n
2. B1
3. Cn (дерево превращается в связный список)
4. D√n

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

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

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

1. AЭти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты
2. BБиты фильтра Блума нельзя менять после создания
3. CФильтры Блума хранят элементы целиком, и их невозможно снова найти после хеширования
4. DУдаление повысило бы долю ложноположительных результатов до 100%

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AОчередь (или любая коллекция) вершин с полустепенью захода 0
2. BMax-куча, упорядоченная по полустепени исхода
3. CСтек всех посещённых рёбер
4. DМатрица смежности, фиксирующая, какие вершины уже удалены