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

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

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

Как элементы массива хранятся в памяти?

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

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

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

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

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

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

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

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

1. AO(V²)
2. BO(V)
3. CO(E log V)
4. DO(V + E)