的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。
3. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。
4. 递归排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。
5. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。
6．各种排序方法的不同数据序的比较、最好、最坏、平均情况。 7．哪些排序不受初始数据的影响。 一般掌握的内容：
1. 每一种排序方法的稳定性。
2. 直接插入排序和直接选择排序的算法。 一般了解的内容：
1. 二路归并排序过程中涉及的每个算法描述。 2. 冒泡排序算法。
第十章 文件
重点掌握的内容： 1. 文件的有关概念。
2. 文件的逻辑结构及其操作。 3. 索引文件的组织方式和特点。
4．索引文件的的查询和更新操作的基本思想。
5. 两种最常用的索引顺序文件(ISAM文件和VSAM文件) 的组织方式和特点。 6. 在ISAM文件和VSAM文件上查找和更新操作的基本思想。 7. 散列文件的组织方式和特点。
8. 散列文件的查询和更新操作的基本思想。 9. 多关键字文件和其它文件的差别。
10. 多重表文件和倒排文件组织方式和特点。
11. 多重表文件和倒排文件查询和更新操作的基本思想。 本章其它内容一般掌握
第二部分 模拟试卷
模拟试题（一）
一、单项选择题（每小题 2 分，共20分）
（1）以下数据结构中哪一个是线性结构？（ ）
A）有向图 B）队列 C）线索二叉树 D）B树 （2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ ）语句序列。
A）p=q; p->next=q; B）p->next=q; q->next=p; C）p->next=q->next; p=q; D）q->next=p->next; p->next=q; （3）（ ）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值
（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串。
A）14 B）5 C）6 D）8
（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。
A）11 B）35 C）19 D）53 以下6-8题基于下图：
（6）该二叉树结点的前序遍历的序列为（ ）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树结点的中序遍历的序列为（ ）。
A）A、B、C、D、E、G、F B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）该二叉树的按层遍历的序列为（ ）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面关于图的存储的叙述中正确的是（ ）。
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 （10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（ ）
A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z
二、（每小题4分，共8分）
已知一个6?5稀疏矩阵如下所示，试：
?00?00??0?1??00?50???000000000000701? 0??0???2?0??0??（1）写出它的三元组线性表；
（2）给出三元组线性表的顺序存储表示。 三、（本题8分）
求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？ 四、（每小题4分，共8分）
对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
（1）从顶点v1出发进行深度优先搜索所得到的深度优先生成树； （2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。
五、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。
六、（本题8分）
对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 七、（本题8分）
一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。
先序序列： B F ICEH G 中序序列：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??6?5525125?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 六、（本题8分）
所构造的堆如下图所示：
七、（本题8分）
在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 八、（每小题2分，共8分） （1）二叉排序树如下图所示：
（2）哈夫曼树如下图所示：
（3）平衡二叉树如下图所示：
（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23 九、（本题9分） 哈希表如下图所示：
十、（本题15分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
C++语言版测试程序见exam1\\10c++，具体算当如下：
template
void display_BT_with_tree_shape(const Binary_tree