Алгоритмы и сложность: лист заданий с ответами

Какой алгоритм сортировки выбирает опорный элемент и разбивает массив на меньшие и бо́льшие элементы?

1. AБыстрая сортировка
2. BСортировка вставками
3. CСортировка пузырьком
4. DСортировка слиянием

Цикл начинается с i = 1 и удваивает i на каждой итерации, пока i > n не станет истинным. Сколько итераций он выполнит?

1. AОколо n
2. BОколо n²
3. CОколо log₂ n
4. DОколо n / 2

Доступ к элементу массива по индексу занимает:

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

Каково решение рекуррентного соотношения T(n) = 2T(n − 1) + O(1)?

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

Вы один раз сортируете массив из n элементов, а затем отвечаете на k запросов о принадлежности бинарным поиском. Какова общая стоимость?

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

Какова амортизированная временная сложность добавления элемента в конец динамического массива, который удваивает свою ёмкость при заполнении?

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

Сортировка вставками работает за O(n) на отсортированном входе. Противоречит ли это нижней оценке Ω(n log n) для сортировки сравнениями?

1. AНет, потому что сортировка вставками не является сортировкой сравнениями
2. BДа, значит, нижняя оценка неверна
3. CНет, нижняя оценка относится к худшему случаю по всем входам, а не к каждому входу
4. DДа, но только для массивов короче 100

Почему алгоритм Дейкстры может давать неверные результаты, если некоторые веса рёбер отрицательны?

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