A）n B）d C）r D）n - d
（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。
A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 （4）限定在一端加入和删除元素的线性表称为（ ）。
A）双向链表 B）单向链表 C）栈 D）队列 （5）快速排序执行一遍之后，已经到位的元素个数是（ ）。
A）1 B）3 C）n D）n
42（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
A）m-n-1 B）n+1 C）m-n+1 D）m-n
（7）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（ ）。
A）12 B）13 C）14 D）15 （8）下面关于广义表的叙述中，不正确的是（ ）。
A）广义表可以是一个多层次的结构 B）广义表至少有一个元素 C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表
（9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（ ）。
A）f>=c B）c>f C）f=2k+1-a D）c>sk-1
（10）从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为（ ）。
A）head(tail(L)) B）head(head(tail(L))) C）tail(head(tail(L))) D）head(tail(head(tail(L)))) 二、（每小题4分，共8分）
写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 三、（每小题4分，共8分） 试对如下图中的二叉树画出其：
（1）顺序存储表示；
（2）二叉链表存储表示的示意图。
四、（每小题4分，共8分）
判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 五、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
六、（每小题2分，共8分）
设有12个数据25,40,33,47,12,66,72,87,94,22,5,58，它们存储在散列表中，利用线性探测再散列处理冲突，取散列函数为H(key)=key % 13。
（1）顺次将各个数据散列到表中，并同时列出各元素的比较次数。 （2）计算查找成功的平均查找次数。 七、（第1小题2分，第2、3小题每小题3分，本题8分） 对于如下图所示的图G，邻接点按从小到大的次序。
（1）图G有几个连通分量？
（2）按深度优先搜索所得的树是什么？
（3）按深度优先搜索所得的顶点序列是什么？ 八、（本题8分）
已知一棵树边的结点为：
{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)} 试画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）树的深度是多少？ 九、（本题9分）
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。
（1）希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢轴） 十、（本题15分）
编写复制一棵二叉树的非递归算法。
模拟试题（五）参考答案
一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）B （4）C （6）D （7）C （8）B （9）B 二、（每小题4分，共8分）
（1）3 X * Y 2 - / 1 + （2）2 X Y 3 + * + 三、（每小题4分，共8分）
（1）二叉树的顺序存储表示如下所示：
0 1 1 2 2 3 3 4 4 5 6 5 7 6 8 9 7 10 11 12 （5）A （10）D
13 8 14 15 16 17 18 9 （2）二叉树的二叉链表存储表示的示意图如下图所示：
四、（每小题4分，共8分）
（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70} （2）是小根堆。 五、（本题8分）
普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 六、（每小题2分，共8分）
（1）取散列函数为H(key)=key % 13。
（2）顺次将各个数据散列到表中，并同时列出各元素的比较次数如下表所示。
各元素的比较次数
地址 关键字 比较 0 1 40 1 2 66 2 3 94 1 4 5 5 1 6 58 1 7 33 1 8 47 1 9 72 3 10 87 2 11 22 3 12 25 1 13 12 2 14
（4）计算查找成功的平均查找次数=（1×7+2×3+3×2）/12=19/12。 七、（第1小题2分，第2、3小题每小题3分，本题8分） （1）图G有2个连通分量。
（2）按深度优先搜索所得的树如下图所示：
（3）按深度优先搜索所得的顶点序列：ABHFGCDE 八、（本题8分）
【解答】树，如下图所示：
（1）C是根结点。
（2）F，K，L，H，D，M，N是叶子结点。 （3）深度是5。 九、（本题9分）
（1）（12,2,10,20,6,18,4,16,30,8,28） （2）（6,2,10,4,8,12,28,30,20,16,18） 十、（本题15分）
可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。 C++语言版测试程序见exam5\\10c++，具体算当如下：
template
void copy_bitree(Binary_tree
}
to_root=new Binary_node
T_to=new Binary_tree
C语言版测试程序见exam5\\10c，具体算当如下：
void CopyBiTree(BiTree T_from,BiTree &T_to) // 复制二叉树T_from到T_to的非递归算法 { if(T_from==NULL) { //空二叉树的处理 T_to=NULL; return; } LinkQueue Q_from,Q_to; BiTNode *e_from,*e_to; InitQueue(Q_from);InitQueue(Q_to); T_to=new BiTNode; T_to->data=T_from->data; //复制根结点 EnQueue(Q_from,T_from);EnQueue(Q_to,T_to); //入队 while(QueueEmpty(Q_from)==FALSE) { DeQueue(Q_from,e_from);DeQueue(Q_to,e_to); //出队 if(e_from->lchild!=NULL) { //复制e_from左孩子 e_to->lchild=new BiTNode; e_to->lchild->data=e_from->lchild->data; EnQueue(Q_from,e_from->lchild);EnQueue(Q_to,e_to->lchild);//入队 } else