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

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

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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AКуча
2. BСтек
3. CОчередь
4. DБинарное дерево

Что делает хеш-функция в хеш-таблице?

1. AОтображает ключ в индекс таблицы
2. BПодсчитывает, сколько ключей хранится
3. CШифрует значения в таблице
4. DСортирует ключи в таблице

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
2. BМассивы требуют меньше инструкций для сравнения значений
3. CОбход массива занимает в сумме O(1), а связного списка — O(n)
4. DСвязные списки всегда хранят элементы на диске

Префиксное дерево (trie) особенно эффективно для:

1. AПоиска кратчайших путей
2. BСортировки чисел
3. CПоиска по префиксу, например автодополнения
4. DХранения матриц

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A2
2. B1
3. C0,5
4. DМаксимума нет

Что делает косое дерево (splay tree) после каждого обращения?

1. AПерестраивает всё дерево в сбалансированном виде
2. BПерекрашивает узлы на пути поиска
3. CПоворотами поднимает узел, к которому обращались, в корень
4. DПеремещает узел, к которому обращались, в лист

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
2. BОтсортированный массив всех n значений
3. CОчередь FIFO последних k значений
4. DMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших