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

Question

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

A．1

B．n-1

C．→n

D．2n

Answer 1

正确答案：C
解析：考生首先要明白两个前提：一是要归并的两个表都是递增有序的，且长度都为n，二是题目问的是最少的关键字比较次数，即最好的情况下的比较次数。而最好的情况应该是：一个表的所有关键字都大于(或小于)另一个表的所有关键字，如：(1234)与(5678)。比较的时候有两个指针分别指向两个表的第一个元素，由于一个表的关键字要都大于另一个表的关键字，所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后，先被并入到新表中，这时关键字大的表的指针还是指向第一个元素没变，此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长，也就是n。