中序序列：D KFIA EJC 后序序列： K FBHJ G A 八、（每小题2分，共8分）

设有序列：w={23,24,27,80,28}，试给出： （1）二叉排序树； （2）哈夫曼树； （3）平衡二叉树；

（4）对于增量d=2按降序执行一遍希尔排序的结果。 九、（本题9分）

有关键字序列{7,23,6,9,17,19,21,22,5}，Hash函数为H(key)=key % 5，采用链地址法处理冲突，试构造哈希表。

十、（本题15分）

假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。

模拟试题（一）参考答案

一、单项选择题

（1）B （2）D （3）A （4）B （6）C （7）A （8）C （9）B 二、（每小题4分，共8分）

（1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) （2）三元组线性表的顺序存储表示如下所示：

?6?1??3??4?5???65525125?1?? ?1???2?5??7??（5）B

（10）B

三、（本题8分）

求网的最小生成树可使用Prim算法，时间复杂度为O(n2)，此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。

四、（每小题4分，共8分）

（1）DFS：v1 v2 v3 v4 v5 （2）BFS：v2 v3 v4 v5 v1 五、（本题8分）

用栈存储入度为零的顶点得到的拓扑排序为： 4 3 6 5 7 2 1 用队列存储入度为零的顶点得到的拓扑排序为： 4 3 6 2 5 1 7 六、（本题8分）

所构造的堆如下图所示：

七、（本题8分）

在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 八、（每小题2分，共8分） （1）二叉排序树如下图所示：

（2）哈夫曼树如下图所示：

（3）平衡二叉树如下图所示：

（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23 九、（本题9分） 哈希表如下图所示：

十、（本题15分）

从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第

三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。

具体算法实现如下：

// 文件路径名:exam1\\alg.h template

void DisplayHelp(BinTreeNode *r, int level)

// 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1 { if(r != NULL) { // 空树不显式，只显式非空树 DisplayHelp(r->rightChild, level + 1); // 显示右子树 cout << endl; // 显示新行 for(int i = 0; i < level - 1; i++) cout << \ // 确保在第level列显示结点 cout << r->data; // 显示结点 DisplayHelp(r->leftChild, level + 1); // 显示左子树 } }

template

void Display(const BinaryTree &bt) // 操作结果：树状形式显示二叉树 { DisplayHelp(bt.GetRoot(), 1); // 树状显示以bt.GetRoot()为根的二叉树 cout << endl; // 换行 }

模拟试题（二）

一、单项选择题（每小题 2 分，共20分）

（1）设Huffman树的叶子结点数为m，则结点总数为（ ）。

A）2m B）2m-1 C）2m+1 D）m+1

（2）若元素a,b,c,d,e,f依次入栈，允许入栈、出栈操作交替进行。但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）

A）dcebfa B）cbdaef C）dbcaef D）afedcb

（3）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（ ）

A）41 B）82 C）113 D）122

（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分）

有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？

三、（每小题4分，共8分）

已知一个无向图的顶点集为{a, b, c, d, e}，其邻接矩阵如下所示：

?01001??? ?10010? ?00011???01101????10110??