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

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

• I.

• II.

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

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

Сколько вершин имеет дерево с 57 ребрами?

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

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

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

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

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

Пусть имеется два отсортированных списка размера K и L соответственно. Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?

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