问题
单项选择题
两个递增序列A和B的长度分别为m和n(m<n),将二者归并为一个长度为m+n的递增序列时,(),归并过程中元素的比较次数最少。
A.当A的最大元素大于B的最大元素时
B.当A的最大元素小于B的最小元素时
C.当A的最小元素大于B的最小元素时
D.当A的最小元素小于B的最大元素时
答案
参考答案:B
解析:
[分析]: 本题考查归并排序基本过程。
两个递增序列A、B进行归并时,从序列的第一个元素开始,分别从这两个序列中取一个元素并进行比较,将较小者输出,然后从较小者所在序列取下一个元素再进行比较,循环往复,直到某个序列的全部元素已经输出,再将另一个序列的剩余元素依次输出即可。
序列A表示为a1,a2,…,am,序列B表示为b1,b2,…,bn(m<n)。
若a1<b1<a2<b2<a3<b3<…<am-1<bm-1<am<bm,则需要2m+1次比较。
若am<b1,则需要依次比较a1与b1、a2与b1、a3与b1、…、am-1与b1、am与b1,共需要m次比较,这是归并时比较次数最少的情况。