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

Что определяет двоичное дерево?

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

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

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

Что такое лист дерева?

1. AУзел ровно с одним потомком
2. BУзел с наибольшим значением
3. CУзел без потомков
4. DУзел без родителя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Как найти минимальный ключ в двоичном дереве поиска?

1. AОбойти все листья и сравнить их
2. BИдти от корня по правым потомкам, пока правого потомка не окажется
3. CПосмотреть только на корень
4. DИдти от корня по левым потомкам, пока левого потомка не окажется

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

1. AСтек
2. BКучу
3. CТолько хеш-таблицу
4. DОчередь

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

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

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

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