将两个分别含有m、n个节点的有序单链表归并成一个有序单链表，要求不破坏原有的单链表，对应算法的空间复杂度是（）（MIN表示取最小值）。A．O(n)B．O(m)C．O(m+n)D．O(MIN(m,n))

正确答案：B

参考答案：
　　合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。
　　[算法描述]
　　void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
　　{//合并链表La和Lb，合并后的新表使用头指针Lc指向
　　pa=La->next; pb=Lb->next;
　　//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
　　Lc=pc=La; //用La的头结点作为Lc的头结点
　　while(pa && pb)
　　{if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}
　　//取较小者La中的元素，将pa链接在pc的后面，pa指针后移
　　else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}
　　//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
　　else //相等时取La中的元素，删除Lb中的元素
　　{pc->next=pa;pc=pa;pa=pa->next;
　　q=pb->next;delete pb ;pb =q;
　　}
　　}
　　pc->next=pa?pa:pb; //插入剩余段
　　delete Lb; //释放Lb的头结点
　　}

参考答案：A

参考答案：C

正确答案：B
解析：本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即则在有序单链表上查找插入位置的平均比较次数为：

正确答案：

 

Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}

答案：C

解析：

答案：C

解析：

正确答案：B

【解析】本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。
插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；…；在第，n个结点之后插入需查找次。如果在每一个位置上作插入的概率相等，即 ，则在有序单链表上查找插入位置的平均比较次数为：

 

参考答案：C
解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。

参考答案：B

参考答案：C

正确答案：C
解析：设A表和B表的长度分别为m和n，则该算法的时间复杂度为O(m+n)。

正确答案： B

答案：C

解析：