Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

Предположим, что P, Q, R, S, T являются отсортированными последовательностями, имеющими длины 20, 24, 30, 35, 50 соответственно. Они должны быть объединены в одну последовательность, объединяя две последовательности одновременно. Число сравнений, которые потребуются в худшем случае оптимальным алгоритмом для этого, составляет ____.
(А) 358
(Б) 438
(С) 568
(D) 664

Ответ: (А)
Объяснение: Чтобы объединить два списка размером m и n, нам нужно выполнить сравнение m + n-1 в худшем случае. Поскольку нам нужно объединять 2 за раз, оптимальной стратегией было бы сначала брать списки наименьшего размера. Причина выбора двух самых маленьких предметов заключается в том, чтобы при объединении иметь минимальные предметы для повторения.
Сначала мы объединяем 20 и 24 и получаем список из 44, используя 43 сравнения в худшем случае. Затем мы объединяем 30 и 35 в список из 65, используя 64 сравнения наихудших случаев. Затем мы объединяем 50 и 44 в список из 94, используя 93 сравнения. Наконец, мы объединяем 94 и 65, используя 158 сравнений. Таким образом, общее количество сравнений составляет 43 + 64 + 93 + 158, что составляет 358.

Источник: http://espressocode.top/data-structures-algorithms-set-34-2/
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

0.00 (0%) 0 votes