2019-gate-computer-science-and-it-practice.pdf/Q21-alg4

Вопрос: Q21-alg4-31d68c

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

I

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

II

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

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

Ответы

• I-TRUE, II-False
• I-TRUE, II-TRUE
• I-False, II-TRUE
• Правильный ответ: I-False, II-False

Объяснение

• Вычисление медианы из n элементов занимает времени в алгоритме Median of Medians.
• Минимальных остовных деревьев может быть несколько, и кратчайшие пути могут не совпадать.

Исходники — вопрос 21 на 239 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.