将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最

问题单项选择题

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

A.I

B.n-1

C.n

D.2n

答案

参考答案：C

解析：

由于两个表有序，最少比较是一个表的最大节点，比另一个表的所有节点小。如{1，2，3}和{4，5，6}。我们只要将表中第一个节点（最小节点），和另个表中所有节点比较，比较次数为另个表的表长。