（1）归并排序，每归并一次书写一个次序。

（2）快速排序，每划分一次书写一个次序以及最后排好序后的序列。 （2）快速排序： (10,18,25,12)29(58,51,47) (10(18,25,12)29((47,51)58) (10((12)18(25))29((47(51))58)

(10,12,18,25,29,47,51,58)

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

九、（本题9分）

试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。

十、（本题15分）

设计以单链表存储的两个集合求交集的算法。

【答案】==================================

一、单项选择题（每小题 2 分，共20分） （1）A （6）B

（2）C （7）C

（3）D （8）D

（4）B （9）A

（5）B （10）A

二、（本题8分）

线性表为：(90,40,78,50,34,60) 三、（本题8分）

五、（本题8分） 如下图所示：

八、（本题8分） 变化过程如下：

（1）归并排序： (l8,29)(25,47)(12,58)(l0,51) (l8,25,29,47)(10,12,51,58)

(l0,12,18,25,29,47,51,58)

（2）快速排序： (10,18,25,12)29(58,51,47) (10(18,25,12)29((47,51)58) (10((12)18(25))29((47(51))58)

(10,12,18,25,29,47,51,58)

（3）堆排序： 初始堆（大顶推）：(58,47,51,29,18,12,25,10) 第一次调整：(51,47,25,29,18,12,10)(58) 第二次调整：(47,29,25,10,18,12)(51,58) 第三次调整：(29,18,25,10,12)(47,51,58) 第四次调整：(25,18,12,10)(29,47,51,58) 第五次调整：(l8,10,12)(25,29,47,51,58) 第六次调整：(l2,10)(18,25,29,47,51,58) 第七次调整：(l0,12,18,25,29,47,51,58) 九、（本题9分）

具有3个结点的树的不同形态如下图所示。

具有3个结点的二叉树的不同形态如下图所示。

十、（本题15分）

用单链表lc表示集合 C。分别将la中元素取出，再在lb中进行查找，如在lb中出现，则将其插入到lc中。

C语言版测试程序见exam6\\10c，具体算当如下：

void interaction(LinkList la,LinkList lb,LinkList &lc) // { }

LinkList pa,pb,pc;

lc=new LNode;

//生成lc的头结点

将链表la与lb中共同出现的元素插入到链表lc中

pc=lc;

//pc永远指向lc的尾结点

//pa指向la的第一个元素

pa=la->next;

while(pa)

{

pb=lb->next;

while(pb&&pb->data!=pa->data) { }

//pc为尾结点，其后继为空

pc->next=new LNode; pc=pc->next;

//生成lc新的尾结点

pb=pb->next;

//在pb中定位pa->data

//定位成功

if(pb)

//pc指向新的尾结点

pc->data=pa->data; }

pa=pa->next;

//将pa->data复制到pc中

pc->next=NULL;