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

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

1. APop
2. BPush
3. CPeek
4. DEnqueue

Как элементы массива хранятся в памяти?

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

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

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

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 3 4 5

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 4
2. BВ индексе 3
3. CВ индексе 6
4. DВ индексе 0

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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