单选题
递增序列A(a
1
，a
2
，…，a
n
)和B(b
1
，b
2
，…，b
n
)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。
A、
a1，a2，…，an，b1，b2，…，bn
B、
b1，b2，…，bn，a1，a2，…，an
C、
a1，b1，a2，b2，…，ai，bi，…，an，bn
D、
a1，a2，…，ai/2，b1，b2，…，bi/2，ai/2+1，ai/2+2，…，an，bi/2+1，…，bn
【正确答案】
C
【答案解析】
要将两个有序序列归并为一个有序序列时，当一个序列的最大值小于另一个序列的最小值，这时需要比较的次数最少。当获得新序列后，两个序列的元素交替的情况(如选项C)下，需比较的次数最多。
提交答案
关闭