设递增序列A为a1 a2 ？ an 递增序列 B为b1 b2 ？ bm 且mgt;n 则将这两 个序列合并为一个长度为m＋
序列,元素
已帮助 人
设递增序列A为a1，a2，？，an，递增序列 B为b1，b2，？，bm，且m>n，则将这两
个序列合并为一个长度为m+n的递增序列时，当 (38) 时，归并过程中元素的比较次
数最少。
(38)
A. an >bm
B.an <b1
C.a1>b1
D.a1<bm
-
参考答案：B试题(38)分析本题考查归并排序算法。将两个有序序列归并为一个有序序列的过程是：从两个序列分别取一个元素进行比较，将较小的元素放入输出序列，并取其所在序列的下一个元素继续归并。因此，当一个序列的全部元素都小于另一个序列的全部元素时，归并过程中的比较次数最少。对于递增序列a1,a2,…,an，和b1,b2,…,bm ，(m>n)，其归并过程如下：a1与b1比较，若a1小，则输出a1，接下来a2与b1比较，若a2小，则输出a2，下来a3与b1比较，以此类推，如果an<b1，则归并过程中共进行n次比较（b1与序列A的每个元素都比较1次）。反之，若b1<a1，b2<a1，…，bm<a1，则归并过程中共进行m次比较（a1与序列B的每个元素都比较1次）。由于m>n，因此在an<b1时，归并过程中元素的比较次数最少。参考答案(38)B