问题 单项选择题

设递增序列A为a1a2,…,an,递增序列B为b1,b2,…,bm,且m>n,则将这两个序列合并为一个长度为m+n的递增序列时,当()时,归并过程中元素的比较次数最少。

A.an>bm

B.an<b1

C.a1>b1

D.a1<bm

答案

参考答案:B

解析:

本题考查归并排序算法。

将两个有序序列归并为一个有序序列的过程是:从两个序列分别取一个元素进行比较,将较小的元素放入输出序列,并取其所在序列的下一个元素继续归并。因此,当一个序列的全部元素都小于另一个序列的全部元素时,归并过程中的比较次数最少。

对于递增序列a12,…,n和b1,b2,…,bm(m>n),其归并过程如下:

a1与b1比较,若a1小,则输出a1,接下来a2与b1比较,若a2小,则输出a2,下来a3与岛比较,以此类推,如果an<b1,则归并过程中共进行n次比较(b1与序列A的每个元素都比较1次)。

反之,若b1<a1,b2<a1,…,bm<a1,则归并过程中共进行m次比较(a1与序列B的每个元素都比较1次)。

由于m>n,因此在an<b1时,归并过程中元素的比较次数最少。

多项选择题
单项选择题