Тест по Computer Science — вопросы

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

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?

Рассмотрим следующий код:

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

Какая сложность по времени для данного кода является правильной?

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

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

Пусть дана последовательность случайных чисел. Какая будет временная сложность для вычисления медианы данного массива? (Разве с помощью алгоритма k-ой порядковой статистики нельзя найти медиану быстрее???)

Рассмотрим следующее рекуррентное соотношение: Какое из следующих утверждений является верным?

Пусть является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

Пусть и что из ниже перечисленного является верным?

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?