（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 九、（本题9分）
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。 十、（本题15分）
已知两个带头结点的单链表A和B分别表示两个集合，元素值递增有序，设计算法求出A，B的交集C，并同样以递增的形式存储。
模拟试题（六）参考答案
一、单项选择题（每小题 2 分，共20分） （1）D （2）C （3）D （4）C （6）B （7）C （8）C （9）B 二、（本题8分）
线性表为：(90,40,78,50,34,60) 三、（本题8分）
（5）B
（10）A
四、（本题8分）
用克鲁斯卡尔算法得到的最小生成树为：
(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 五、（本题8分） 如下图所示：
六、（本题8分）
根据后序序列知根结点为C，所以左子树：中序序列为AB，后序序列为AB；右子树：中序序列为EFGHD，后序序列为FHGED，以此类推得该二叉树结构如下图所示。
七、（每小题4分，共8分）
（1）由邻接矩阵所画的有向图如下图所示：
2212523145358635957
（2）关键路径如下图所示：
123145597
八、（本题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分）
解答：由于单链表A和B是递增有序的，可设置两个整型变量分别表示两个单链表的当前元素的位置，依次取出A与B的元素进行比较，当A的数据元素小于B的值时，将指向A的当前位置都后移；当A的数据元素大于B的值时，将指向B的当前位置都后移，否
则复将A（或B）的当前元素制到C中，并同时将A与B的当前位置后移。具体算法如下：
用单链表la表示集合 la，用单链表lb表示集合 lb，用单链表lc表示集合 lc，具体算法如下：
// 文件路径名:exam6\\alg.h template
void Interaction(const LinkList