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

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

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

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

1. AEnqueue
2. BInsert
3. CDequeue
4. DPush

Сколько рёбер в дереве с n узлами?

1. A2n
2. Bn + 1
3. Cn
4. Dn − 1

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

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

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

Почему B-деревья используются в базах данных и файловых системах?

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

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

1. AЗначения хеша должны быть простыми числами
2. BРавные ключи должны иметь равные значения хеша
3. CРазные ключи должны иметь разные значения хеша
4. DИз равенства хешей следует равенство ключей