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

Что такое коллизия в хеш-таблице?

1. AКлюч вообще невозможно хешировать
2. BДва разных ключа отображаются в один и тот же индекс
3. CВ таблице заканчивается память
4. DДва одинаковых ключа хранятся дважды

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

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

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AДоступ к 5-му элементу
2. BЧтение последнего элемента по индексу
3. CОпределение длины массива фиксированного размера
4. DВставка в начало

Сколько памяти занимает матрица смежности графа с V вершинами?

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. Ah²
2. B2^h+1 − 1
3. C2^h
4. D2h + 1

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. Ai/2 и i/2 + 1
2. B2i и 2i + 1
3. Ci + 1 и i + 2
4. D2i + 1 и 2i + 2

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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