Тест по 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) в процессе работы алгоритма поиска в глубину?

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

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

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

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

• I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

• II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

Предположим, что G — это связный неориентированный граф, ребра которого имеют положительные веса. Пусть M — минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно?

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

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

• I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.

• II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

Какие из данных утверждений верны?

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