Пусть P будет программой быстрой сортировки для сортировки чисел в порядке возрастания с использованием первого элемента в качестве точки разворота. Пусть t1 и t2 будут количеством сравнений, сделанных P для входов {1, 2, 3, 4, 5} и {4, 1, 5, 3, 2} соответственно. Что из следующего имеет место?
(А) t1 = 5
(B) t1 <t2
(С) t1> t2
(D) t1 = t2
Ответ: (с)
Объяснение: Когда первый или последний элемент выбран в качестве сводного, наихудший случай быстрой сортировки возникает для отсортированных массивов.
На каждом этапе быстрой сортировки числа делятся в соответствии со следующим повторением.
T (n) = T (n-1) + O (n)
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes