发布时间 : 星期三 文章数据结构期终复习更新完毕开始阅读5f435cfcce84b9d528ea81c758f5f61fb6362842
中序序列：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为根的二叉树，level为层次数，可设根结点的层次数为1 { if(r != NULL) { // 空树不显式，只显式非空树 DisplayHelp
template
void Display(const BinaryTree
模拟试题（二）
一、单项选择题（每小题 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??