第 10 题
初始有三个升序序列 (3, 5)、(7, 9)、(6)，若按从左至右的次序选择有序序列进行二路归并排序，则关键字之间的总比较次数是（）。
A. 3 B. 4 C. 5 D. 6
[tag_link]
正确答案：C
本题考察 多路归并 的原理，二路归并排序将相邻的有序子序列两两合并，得到合并后有序子序列。重复此过程，直到所有子序列合并为一个有序序列。第一轮归并：将升序序列两两分组，(3,5) 和 (7,9) 分为一组，(6) 分为一组。(3,5) 和 (7,9) 的归并过程如下：
| 输入序列 | 比较首个元素 | 输出元素 | 输出序列 | 剩余输入序列 |
|---|---|---|---|---|
| (3,5) 和 (7,9) | 3 < 7 | 3 | 3 | (5) 和 (7,9) |
| (5) 和 (7,9) | 5 < 7 | 5 | 3,5 | (7,9) |
| (7,9) | 7 | 3,5,7 | (9) | |
| (9) | 9 | 3,5,7,9 | ||
| 第二轮归并：将升序序列两两分组，(3,5,7,9) 和 (6) 分为一组。(3,5,7,9) 和 (6) 的归并过程如下： |
| 输入序列 | 比较首个元素 | 输出元素 | 输出序列 | 剩余输入序列 |
|---|---|---|---|---|
| (3,5,7,9) 和 (6) | 3 < 6 | 3 | 3 | (5,7,9) 和 (6) |
| (5,7,9) 和 (6) | 5 < 6 | 5 | 3,5 | (7,9) 和 (6) |
| (7,9) 和 (6) | 7 > 6 | 6 | 3,5,6 | (7,9) |
| (7,9) | 7 | 3,5,6,7 | (9) | |
| (9) | 9 | 3,5,6,7,9 | ||
| 到此，二路归并排序执行完毕。上述过程中第一轮归并关键字之间比较 2 次，第二轮归并关键字之间比较 3 次，因此，关键字之间的总比较次数为 2 + 3 = 5。本题选 C。 |