（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？ 五、（本题8分）
将关键字序列（7、8、11、18、9、14, 30）散列存储到散列列表中，散列表的存储空
H(key)=% m间是一个下标从0开始的一个一维数组，散列函数为：（key * 3）（m为表长），
处理冲突采用线性探测再散列法，要求装填（载）因子为0.7，请画出所构造的散列表；计算查找成功的平均查找长度。
六、（本题8分）
试列出如下图中全部可能的拓扑排序序列。
123456 七、（本题8分）
请说明对一棵二叉树进行按照先遍左子树，后右子树的方式进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？
八、（本题8分）
设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。
九、（本题9分）
试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。
十、（本题15分）
以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。
模拟试题（二）参考答案
一、单项选择题（每小题 2 分，共20分） （1）B （2）C.D （3）B （4）D （5）A （6）A （7）C （8）C （9）D （10）D 二、（本题8分）
D第二个出栈的次序有CDEBA 、CDBAE 和按照栈的特点可知以元素C第一个出栈，
CDBEA 3种。
三、（每小题4分，共8分）
【解答】
（1）该图的图形如下图所示：
（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。 四、（本题8分）
树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。
五、（本题8分）
由装载因子0.7，由于有7个数据元素，可得7/m=0.7，从而m=10，所以，构造的散列表为：
下标 关键字 比较次数
0 30 1
1 7 1
2 14 1
3 11 1
4 8 1
5 18 2
6 .
7 9 1
8 .
9
H（7）=（7*3）% 10=1 H（8）=（8*3）% 10=4 H（11）=（11*3）% 10=3 H（18）=（18*3）% 10=4 H（9）=（9*3）% 10=7 H（14）=（14*3）% 10=2 H（30）=（30*3）% 10=2
（2）查找成功的ASL=(1+1+1+1+1+2+1)/7=8/7 六、（本题8分）
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
七、（本题8分）
二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。
八、（本题8分）
九、（本题9分）
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：
波兰式表示：*+a/bc-d*ef 中缀表示：a+b/c*d-e*f 逆波兰式表示：abc/+def*-* 十、（本题15分）
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 具体算法实现如下：
// 文件路径名:exam2\\alg.h template
long LeafCountHelp(BinTreeNode
// 操作结果：按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if (r == NULL) { // 空二叉树 return 0; // 空树返回0 } else if (r->leftChild == NULL && r->rightChild == NULL) { // 只有一个结点的树 return 1; // 只有一个结点的树返回1 } else { // 其他情况, 叶子结点数为左右子树的叶子结点数之和 return LeafCountHelp(r->leftChild) + LeafCountHelp(r->rightChild); } }
template
long LeafCount(const BinaryTree
模拟试题（三）
一、单项选择题（每小题 2 分，共20分）
（1）对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下
第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是（ ）。
A）起泡排序 B）希尔排序 C）归并排序 D）基数排序
（2）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ ）。
A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p C）p->next=HL; p=HL D）HL=p; p->next=HL （3）对线性表，在下列哪种情况下应当采用链表表示？（ ）
A）经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变
（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3
（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。
A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序 （6）采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A）低于链接法处理冲突 B）高于链接法处理冲突 C）与链接法处理冲突相同 D）高于二分查找
（7）若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。
A）值 B）函数 C）指针 D）引用
（8）为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A）栈 B）队列 C）树 D）图
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。
A）行号 B）列号 C）元素值 D）非零元素个数