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

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

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

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

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

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

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

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

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

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

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

1. AO(m)
2. BO(log n)
3. CO(n)
4. DO(1 + α), где α = n / m

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AХранить front и rear в одной переменной
2. BХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
4. DДелать размер буфера степенью двойки