递增序列A（a1，a2，…，an）和B（b1，b2，…，bn）的元素互不相同，若需将它们合并为一个长度为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），这种情况下需比较的次数最多。
