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

Что такое корень дерева?

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

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

1. APush
2. BDequeue
3. CEnqueue
4. DInsert

Сколько рёбер в дереве с n узлами?

1. An
2. B2n
3. Cn + 1
4. Dn − 1

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

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

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A24
2. B14
3. C11
4. D10

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

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

1. AНеобходимость хранить ключи в таблице
2. BНеобходимость в хеш-функции
3. CСтоимость O(n) чтения значения по ключу
4. DПервичную кластеризацию, при которой образуются длинные серии занятых ячеек