}
}
e_to->lchild=NULL; //左孩子为空 if(e_from->rchild!=NULL) { //复制e_from右孩子 e_to->rchild=new BiTNode; e_to->rchild->data=e_from->rchild->data; EnQueue(Q_from,e_from->rchild);EnQueue(Q_to,e_to->rchild);//入队 } else e_to->rchild=NULL; //右孩子为空
模拟试题（六）
一、单项选择题（每小题 2 分，共20分）
（1）下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是（ ）。
A）顺序结构 B）链接结构 C）索引结构 D）Hash结构 （2）在数据结构中，数据元素可由（ ）。
A）实体 B）域 C）数据项 D）字段
（3）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ ）。
A）O(1) B）O(n) C）O(n) D）O(n3)
（4）对n个记录的文件进行快速排序，所需要的辅助存储空间为（ ）。
A）O（1） B）O（log2n） C）O（n） D）O（n2） （5）哈夫曼树中一定不存在（ ）。
A）度为0的结点 B）度为1的结点 C）度为2的结点 D）带权的结点 （6）设D={A,B,C,D}，R={
A）树 B）图 B）线性表 D）前面都正确 （7）（ ）关键码序列不符合堆的定义。
A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X、G、Q、R C）A、D、P、R、C、Q、X、M、H、G D）A、D、C、M、P、G、H、X、R、Q （8）假定关键字K=442205883，允许存储地址为四位十进制数，并且Hash地址为6111，则所采用的构造Hash函数的方法是（ ）。
A）直接定址法 B）平方取中法 C）除留余数法，模为97 D）折叠法 （9）在算法的时间复杂度中，n表示问题规模，f(n)表示基本操作重复执行的次数，则随问题的规模n的增大，算法执行时间的增长率同（ ）相同。
A）f(n) B）n C）O(n) D）前面都不正确 （10）对线性表进行二分法查找，其前提条件是（ ）。
A）线性表以顺序方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以链接方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序 二、（本题8分）
在如下表所示的数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。
线性表
A Data next 0 4 1 60 0 2 50 5 3 78 2 4 90 7 5 34 1 6 7 40 3 三、（本题8分）
已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出这棵二叉树。
四、（本题8分）
已知一个图的顶点集V为： V={1,2,3,4,5,6,7}，弧如下表所示。
图的弧集
起点 终点 权 1 6 1 2 4 1 2 5 2 5 4 2 5 7 2 2 6 3 2 7 3 6 7 4 1 7 5 3 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 五、（本题8分）
向最小根堆中依次插入数据4, 2, 5, 8, 3, 6, 10, 1时，画出每插入一个数据后堆的变化。
六、（本题8分）
已知广义表L=(((b,c),d),((a),((b,c),d)),())，试画出它的存储结构。 七、（每小题4分，共8分）
对给定的有7个顶点的有向图的邻接矩阵如下： （l）画出该有向图；
（2）若将图看成是AOE-网，画出关键路径。
??????????????????
2?522?1???????????????????8???35???
5????39????5??????八、（本题8分）
给出一组关键字29、18、25、47、58、12、51、10，分别写出按下列各种排序方法进行排序时的变化过程：
（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 （2）C （3）D （4）B （6）B （7）C （8）D （9）A 二、（本题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分）
本题广义表存储结构如下图所示：
七、（每小题4分，共8分）
（1）由邻接矩阵所画的有向图如下图所示：
2212523145358635957 （2）关键路径如下图所示：
22123145597 八、（本题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++，具体算当如下：
template
void interaction(List