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

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

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

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

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

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

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

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

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

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

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

Какие из представленных ниже утверждений являются верными?

• 1)

• 2)

• 3),  — константа

• 4)

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

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

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

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

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?