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

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

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

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

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

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

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

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

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

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

Существует несколько способов определить порядок умножения матриц 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 соответственно?

Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?

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