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

考查要点：本题主要考查归并两个有序表时的最少比较次数，需要理解归并过程中的比较逻辑及最优情况下的操作特点。

解题核心思路：
在归并两个有序表时，每次比较两个当前元素，选择较小者放入结果表。最少比较次数发生在两个表元素严格递增且完全相同的情况下。此时，每次比较后只需移动一个指针，无需反复比较后续元素。

破题关键点：

• 最优情况：两个有序表元素完全相同，归并时只需逐个比较一次，后续元素顺序已确定，无需额外比较。
• 比较次数公式：总共有n个元素需比较，但最后一个元素无需比较（因只剩一个表的元素），故总比较次数为n-1次。

最少比较次数的推导

1. 最优情况假设：两个有序表元素完全相同，例如表A和表B均为[a₁, a₂, ..., aₙ]。
2. 归并过程：
   • 第1次比较：比较A[0]和B[0]，选其中一个（如A[0]），放入结果表。
   • 指针移动：A的指针移至A[1]，B的指针仍指向B[0]。
   • 后续比较：由于元素完全相同，后续每次只需比较一次，即可确定下一个元素（如A[1]与B[0]比较后，选A[1]，B指针仍不动）。
3. 总比较次数：
   • 前n-1个元素各需比较一次，最后一个元素无需比较（因只剩一个表的元素）。
   • 总次数：n-1次。

选项分析

• A. n：错误，未考虑最后一个元素无需比较。
• B. 2n-1：错误，这是最坏情况下的比较次数。
• C. 2n：错误，明显超出实际可能。
• D. n-1：正确，符合最优情况下的推导。