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

Что делает операция peek (или top) стека?

1. AУдаляет верхний элемент и возвращает его
2. BУдаляет все элементы из стека
3. CВозвращает верхний элемент, не удаляя его
4. DВозвращает нижний элемент стека

В односвязном списке каждый узел содержит:

1. AДанные и ссылку на следующий узел
2. BДанные и ссылки на все остальные узлы
3. CТолько данные
4. DДанные и индекс

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем узел, затем правое поддерево
2. BПо уровням сверху вниз
3. CЛевое поддерево, затем правое поддерево, затем узел
4. DУзел, затем левое поддерево, затем правое поддерево

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(L), независимо от числа хранимых слов
2. BO(log n), где n — число слов
3. CO(L × n)
4. DO(n), где n — число слов

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

1. A4 2 5 1 3
2. B1 2 3 4 5
3. C1 2 4 5 3
4. D4 5 2 3 1

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

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

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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