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

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

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

Что такое дек (deque, двусторонняя очередь)?

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

В чём главное отличие статического массива от динамического?

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AОчереди фиксированного размера
2. BДвоичного дерева поиска
3. CОбхода графа
4. DХеш-функции

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

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

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

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

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

1. AВысота не превышает log₂ n + 1
2. BВысота не превышает 2 log₂(n + 1)
3. CВысота равна ровно log₂ n
4. DВысота не превышает n / 2

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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