aux_display_BT_with_tree_shape
template
void aux_display_BT_with_tree_shape(Binary_node
C语言版测试程序见exam1\\10c，具体算当如下：
void DisplayBTWithTreeShape(BiTree T,int level=1) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(T) { //空树不显式，只显式非空树 DisplayBTWithTreeShape(T->rchild,level+1); //显示右子树 cout<
模拟试题（二）
一、单项选择题（每小题 2 分，共20分）
（1）设Huffman树的叶子结点数为m，则结点总数为（ ）。
A）2m B）2m-1 C）2m+1 D）m+1
（2）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（ ）个元素。
A）n B）n-1 C）n+1 D）不确定 （3）下述哪一条是顺序存储方式的优点？（ ）
A）存储密度大 B）插入和删除运算方便
C）获取符合某种条件的元素方便 D）查找运算速度快
（4）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，
m>3） 每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，（ ）。
A）658 B）648 C）633 D）653 （5）下列关于二叉树遍历的叙述中，正确的是（ ）。
A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
（6）k层二叉树的结点总数最多为（ ）。
A）2k-1 B）2k+1 C）2K-1 D）2k-1 （7）对线性表进行二分法查找，其前提条件是（ ）。
A）线性表以链接方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以顺序方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序 （8）对n个记录进行堆排序，所需要的辅助存储空间为（ ）。
A）O(1og2n) B）O(n) C）O(1) D）O(n2)
（9）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（ ）个。
A）1 B）2 C）3 D）4 （10）下列关于数据结构的叙述中，正确的是（ ）。
A）数组是不同类型值的集合
B）递归算法的程序结构比迭代算法的程序结构更为精炼 C）树是一种线性结构
D）用一维数组存储一棵完全二叉树是有效的存储方法 二、（本题8分）
假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。
三、（每小题4分，共8分）
已知一个无向图的顶点集为{a, b, c, d, e}，其邻接矩阵如下所示：
?01001??? ?10010? ?00011????01101???10110??（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？ 五、（本题8分）
设有数组A[-1:3,0:6,-2:3]，按行为主序存放在2000开始的连续空间中，如元素的长度是5，试计算出A[1,1,1]的存储位置。
六、（本题8分）
试列出如下图中全部可能的拓扑排序序列。
123456 七、（本题8分）
已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。
八、（本题8分） 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个
数据而生成的二叉搜索树。 九、（本题9分）
试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。
十、（本题15分）
以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。
模拟试题（二）参考答案
一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）A （4）D （6）A （7）C （8）C （9）D
（5）A
（10）D
二、（本题8分） 先序： a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按层： a,b,d,c,e,f 三、（每小题4分，共8分） 【解答】
（1）该图的图形如下图所示：
（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。 四、（本题8分）
树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。
五、（本题8分）
A[1,1,1]的存储位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。 六、（本题8分）
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
七、（本题8分）
哈希表及查找各关键字要比较的次数如下所示：
ASL=1(4×1+1×2+1×4+2×5)=2.5
8八、（本题8分）
九、（本题9分）
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序
遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：
波兰式表示：*+a/bc-d*ef 中缀表示：a+b/c*d-e*f 逆波兰式表示：abc/+def*-* 十、（本题15分）
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 C++语言版测试程序见exam2\\10c++，具体算当如下：
template
long leaf_count(const Binary_tree
template
long aux_leaf_count(Binary_node
C语言版测试程序见exam2\\10c，具体算当如下：
long LeafCount(BiTree T) // 计算二叉树中叶子结点数目 { if(T==NULL) return 0; //空树返回0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //只有一个结点的树返回1 else //叶子结点数为左右子树的叶子结点数之和