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

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

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

Что такое ориентированный граф?

1. AГраф без циклов
2. BГраф, в котором каждая пара различных вершин соединена ребром
3. CГраф, рёбра которого направлены от одной вершины к другой
4. DГраф, у всех рёбер которого есть веса

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

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

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

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

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

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

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

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

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

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

1. AЧтобы не нужно было увеличивать таблицу
2. BЧтобы хеш-таблица была отсортирована
3. CЧтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
4. DЧтобы гарантировать, что никакие два ключа никогда не столкнутся, какие бы ключи ни присылал атакующий