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

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

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

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

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

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

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

• I. Диграф — это граф, имеющий ровно 2 вершины.

• II. Остовное дерево в графе всегда должно содержать как минимум ребер.

• III. Алгоритм сортировки ребер для решения задачи коммивояжера всегда дает оптимальный результат.

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

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

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

• I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.

• II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

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

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

• I.

• II.

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

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

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

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