（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
// 初始条件: la和lb中数据元素递增有序
// 操作结果: lc返回la与lb表示的集合的交集，并使lc中数据元素仍递增有序 { ElemType aItem, bItem; // la和lb中当前数据元素 int aLength = la.Length(), bLength = lb.Length(); // la和lb的长度 int aPosition = 1, bPosition = 1; // la和lb的当前元素序号 lc.Clear(); // 清空lc while (aPosition <= aLength && bPosition <= bLength ) { // 取出la和lb中数据元素进行归并 la.GetElem(aPosition, aItem); // 取出la中数据元素 lb.GetElem(bPosition, bItem); // 取出lb中数据元素 if (aItem < bItem) { // aItem插入到lc aPosition++; // 指向la下一数据元素 } else if (aItem > bItem) { // lb后移 bPosition++; // 指向lb下一数据元素 } else
}
}
{ }
// aItem == bItem，la和lb同时后移 lc.Insert(lc.Length() + 1, aItem); aPosition++; bPosition++;
// 插入aItem到lc
// 指向la下一数据元素 // 指向lb下一数据元素
*模拟试题（七）
注：本套试题选作
一、单项选择题（每小题 2 分，共20分）
（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ ）。
A）1234 B）4132 C）4231 D）4213 （2）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[298]中，A中元素a66,65在B数组中的位置k为（ ）（假设B[0]的位置是1）。 A）198 B）195 C）197 D）198
（3）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A）n-1
B）??n??1 ?m??C）??n?1? ?m?1??D）??n??1 ?m?1??（4）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻
接矩阵必定为（ ）。
A）对称矩阵 B）稀疏矩阵 C）三角矩阵 D）一般矩阵
（5）设森林 F对应的二叉树为有 m个结点，此二叉树根的左子树的结点个数为k，则另一棵子树的结点个数为（ ）。
A）m-k+1 B）k+1 C）m-k-1 D）m-k （6）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A）K-1次 B）K次 C）K＋l次 D）K(K+1)/2次 （7）一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。
A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1
（8）如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
A）直接插入排序 B）快速排序 C）归并排序 D）选择排序 （9）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有（ ）