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

Существует несколько способов определить порядок умножения матриц A, B, C, D: (A(BC)D), A(B(CD)), (AB)(CD), ((AB)C)D), A((BC)D)

Эффективность умножения зависит от числа скалярных произведений, для (A(BC))D получится:

Для (A(B(CD))):

Какие размерности у матриц A, B, C, D соответственно?

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

Рассмотрим следующие утверждения (h(k) — хэш-функция):

• I. если даже .

• II. для любых .

• III. для любых .

Рассмотрим следующее AVL-дерево:

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

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

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

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

Рассмотрим следующие выражения:

• I.

• II.

Какие утверждения верные, а какие нет?

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

Рассмотрим следующие утверждения:

• Пусть n — это число элементов в массиве
• В процессе сортировки массива происходит порядка уровней
• На каждом уровне происходит порядка действий

Для какого алгоритма сортировки все утверждения являются верными?