将两个长度为n的递增有序表归并成一个长度为2n的递增有序表,最少需要进行关键字比较()次。A.2B.n－

Question

将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较( )次。

A．2

B．n-1

C．n

D．2n

Answer 1

正确答案：C
解析：因为两个长度为n的有序表都递增，要归并为一个有序表，最好的情况是其中一个有序表A的最后一个元素比另一个有序表B第一个元素还小，这至少需要比较n次才能确定B的第一个元素的插入位置。