7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

，8. 图的生成树（若一个具有n个顶点，e条边的无向图是一个森林（n＞e）则该森林中必有多少棵树。）、深度优先生成树和广度优先生成树、生成树的权、最

小生成树等的定义。

9. 根据普里姆算法求图的最小生成树的过程。

10．根据克鲁斯卡尔算法求图的最小生成树的过程。

11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。

12．强连通图的最少边数。 一般掌握的内容：

1．根据普里姆算法求图的最小生成树的算法描述。 2．根据克鲁斯卡尔算法求图的最小生成树的算法描述。 3. 对用邻接表表示的图进行拓扑排序的和算法描述。 对本章的其余内容均作一般了解。

第八章 查找

重点掌握的内容：

1. 在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找长度和时间复杂度。

2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。

3. 散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。 4. 利用除留余数法建立散列函数求元素散列地址的方法。

5. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。

6. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。

7. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。

一般掌握的内容： 1. B_树查找算法。

2. 向B_树中插入元素的过程。 对本章的其余内容均作一般了解。

第九章 排序

重点掌握的内容：

1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。

2. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。

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

已知一个65稀疏矩阵如下所示，试：

?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