将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )。A. nB. 2n-1C. 2nD. n-1

归并两个有序表的最少比较次数问题，考查对归并过程的理解及最优化分析能力。
核心思路：比较次数最少的情况发生在其中一个表的所有元素均小于另一个表的元素时。此时，每次只需比较一次即可确定下一个元素，无需反复比较。
关键点：

1. 有序表特性：两个表各自有序，归并时只需逐个比较当前元素。
2. 极端情况：当一个表的所有元素均小于另一个表时，只需进行n次比较即可完成归并，后续元素直接拼接无需比较。

最少比较次数的推导

1. 极端情况假设：假设表A的所有元素均小于表B的元素。
   • 例如：A = [1, 3, 5], B = [2, 4, 6]。
2. 归并过程：
   • 第1次比较：A[0]=1 < B[0]=2 → 取1，A指针后移。
   • 第2次比较：A[1]=3 < B[0]=2 → 取3，A指针后移。
   • 依此类推，每次从A取元素均需比较一次，共n次比较。
3. 剩余元素处理：当A取完后，B剩余元素直接拼接，无需比较。

结论：最少比较次数为n次，对应选项A。