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

Какая структура данных используется для обхода дерева по уровням (level-order)?

1. AСтек
2. BОчередь
3. CХеш-таблица
4. DОчередь с приоритетом

Где находится наименьший элемент двоичной min-кучи?

1. AВ каком-то листе, который придётся искать
2. BВ корне
3. CВ самом левом листе
4. DВ последней позиции массива

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

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

Как вставляется новый элемент в двоичную кучу?

1. AЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
2. BВсю кучу перестраивают с нуля
3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
4. DЕго помещают в корень и опускают вниз

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ односвязном списке
2. BВ динамическом массиве
3. CВ двусвязном списке
4. DВ отсортированном массиве

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

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

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

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

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

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