四川大学数据结构期终复习提纲模拟题答案.doc

四川大学“精品课程”
计算机科学与技术专业（本科）
《数据结构与算法分析》课程
考试说明与模拟试卷
第一部分 考试说明
数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或 C++ Builder或Borland C++）。
下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。
第一章 绪论
重点掌握的内容：
1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。
2. 集合结构、线性结构、树结构和图结构的特点。
3. 抽象数据类型的定义和表示方法。
4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。
5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。
6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。
7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。
8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。
对于本章的其余内容均作一般掌握。

第二章 线性表
重点掌握的内容：
1. 线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。
3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4. 链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。
5. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。
6. 带表头附加结点的链表、循环链表、双向链表的结构特点。
7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
9．Josephus问题的求解过程。
10．顺序表和线性链表的性能比较及各自使用背景。
对于本章的其余内容均作一般掌握。

第三章 数组和广义表
重点掌握的内容：
1. 多维数组的逻辑结构特征。
2. 多维数组的顺序存储结构及地址计算公式。
3．数组是一种随机存取结构的原因。
4．特殊矩阵和稀疏矩阵的概念。
5．特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。
6. 稀疏矩阵的定义和三元组线性表及三列二维数组表示。
7. 稀疏矩阵的顺序存储、带行指针向量的链接存储，在每一种存储中非零元素结点的结构。
8. 稀疏矩阵的转置运算。
9. 广义表的定义和表示，广义表长度和深度的计算。
10．广义表上的求表头、表尾运算。
5. 广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法，它们对应的时间复杂度。
一般掌握的内容：
稀疏矩阵转置的算法描述。
对于本章的其余内容均作一般了解。

第四章 栈和队列
重点掌握的内容：
1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。
3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。
5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。
6．给定n个栈元素, 出栈可能或不可能的序列数。
7. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
8. 队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。
9. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
10. 利用栈和队列解决简单问题的算法分析和设计。
11．双端队的概念及可能出队序列。
12．队和栈的应用背景，如cpu队、进程队、打印机队。
13．链队的各种存储表示。
一般掌握的内容：
1. 后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。
2. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。
对于本章的其余内容均作一般了解。

第五章 字符串
重点掌握的内容：
1. 串的有关概念及基本运算。
2. 串与线性表的关系。
3．串的各种存储结构。
4．一个串中真子串和子串个数的确定。
一般掌握的内容：
1. 串上各种运算的实现及其时间性能分析。
2. 使用C++提供的操作函数构造与串相关的算法解决简单的应用问题。

第六章 树和二叉树
重点掌握的内容：
1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。
2. 树和二叉树的概念，如结点的度、树的度、树叶、分枝结点、树的层数、树的深度等。
3．不同结点数的树和二叉树的形态。
4. 树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。
5. 二叉树中结点的编号规则和对应的顺序存储结构。
6. 二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。
7. 二叉树的先序、中序、后序、遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法，每种算法的时间复杂度。
8．二叉树的先序、中序、后序遍历序列，唯一确定一棵二叉树的原则。
9．算术表达式的二叉树表示及逆波兰表达式、中缀表示。
一般掌握的内容：
1. 普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用。
2．普通树的先根、后根和按层遍历的过程及算法。
3. 在链接存储的二叉树上实现指定功能的算法分析和设计。
对于本章的其余内容均作一般了解。

二叉树的应用
重点掌握的内容：
1. 二叉搜索树的定义和性质、建立。
2. 二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。
3. 二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度，根据一组数据生成一棵二叉搜索树的过程。
4. 堆的定义和顺序存储结构，小根堆和大根堆的异同及堆的判别、建立堆的过程。
5. 向堆中插入元素的过程、算法描述及时间复杂度。
6. 从堆中删除元素的过程、算法描述及时间复杂度。
7. 哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。
8．顺序二叉树及二叉链表表示二叉树。
9．已知关键字序列{22,16,38,89,56，16，79}，试构造平衡二叉树。
对本章的其余内容均作一般了解。

第七章 图
重点掌握的内容：
1. 图的顶点集和边集的表示。
2. 图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。
3. 图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构及相应的空间复杂度。
4. 存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用途。
5. 图的深度优先和广度优先搜索遍历的过程。
6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。
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分）
已知一个6´5稀疏矩阵如下所示，试：

（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 （5）B
（6）C （7）A （8）C （9）B （10）B
二、（每小题4分，共8分）
（1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))
（2）三元组线性表的顺序存储表示如下所示：

三、（本题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分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
具体算法实现如下：

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

template <class ElemType>
void Display(const BinaryTree<ElemType> &bt)
// 操作结果：树状形式显示二叉树
{
DisplayHelp<ElemType>(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)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）（　　　）。
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}，其邻接矩阵如下所示：

（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？
五、（本题8分）
将关键字序列（7、8、11、18、9、14, 30）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H(key)=（key * 3）% m（m为表长），处理冲突采用线性探测再散列法，要求装填（载）因子为0.7，请画出所构造的散列表；计算查找成功的平均查找长度。
六、（本题8分）
试列出如下图中全部可能的拓扑排序序列。

七、（本题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）D （3）B （4）D （5）A
（6）A （7）C （8）C （9）D （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分）
由装载因子0.7，由于有7个数据元素，可得7/m=0.7，从而m=10，所以，构造的散列表为：
下标
0
1
2
3
4
5
6
7
8
9
关键字
30
7
14
11
8
18
.
9
.

比较次数
1
1
1
1
1
2

1

H（7）=（7*3）% 10=1
H（8）=（8*3）% 10=4
H（11）=（11*3）% 10=3
H（18）=（18*3）% 10=4
H（9）=（9*3）% 10=7
H（14）=（14*3）% 10=2
H（30）=（30*3）% 10=2
（2）查找成功的ASL=(1+1+1+1+1+2+1)/7=8/7
六、（本题8分）
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
七、（本题8分）
哈希表及查找各关键字要比较的次数如下图所示：

ASL=(4×1+1×2+1×4+2×5)=2.5
八、（本题8分）

九、（本题9分）
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：

波兰式表示：*+a/bc-d*ef
中缀表示：a+b/c*d-e*f
逆波兰式表示：abc/+def*-*
十、（本题15分）
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。
具体算法实现如下：

// 文件路径名:exam2\alg.h
template <class ElemType>
long LeafCountHelp(BinTreeNode<ElemType> *r)
// 操作结果：按树状形式显示二叉树，level为层次数，可设根结点的层次数为1
{
if (r == NULL)
{ // 空二叉树
return 0; // 空树返回0
}
else if (r->leftChild == NULL && r->rightChild == NULL)
{ // 只有一个结点的树
return 1; // 只有一个结点的树返回1
}
else
{ // 其他情况, 叶子结点数为左右子树的叶子结点数之和
return LeafCountHelp(r->leftChild) + LeafCountHelp(r->rightChild);
}
}

template <class ElemType>
long LeafCount(const BinaryTree<ElemType> &bt)
// 操作结果：计算二叉树中叶子结点数目
{
return LeafCountHelp(bt.GetRoot()); // 调用辅助函数实现计算二叉树中叶子结点数目
}

模拟试题（三）
一、单项选择题（每小题 2 分，共20分）
（1）对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下
第一趟：2，12，16，5，10，88
第二趟：2，12，5，10，16，88
第三趟：2，5，10，12，16，88
则采用的排序方法可能是（ ）。
A）起泡排序 B）希尔排序 C）归并排序 D）基数排序
（2）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（　　　）。
A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p
C）p->next=HL; p=HL D）HL=p; p->next=HL
（3）对线性表，在下列哪种情况下应当采用链表表示？（　　　）
A）经常需要随机地存取元素 B）经常需要进行插入和删除操作
C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变
（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（　　　）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3
（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（　　　）。
A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序
（6）采用开放定址法处理散列表的冲突时，其平均查找长度（　　　）。
A）低于链接法处理冲突 B）高于链接法处理冲突
C）与链接法处理冲突相同 D）高于二分查找
（7）若需要利用形参直接访问实参时，应将形参变量说明为（　　　）参数。
A）值 B）函数 C）指针 D）引用
（8）为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A）栈 B）队列 C）树 D）图
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（　　　）。
A）行号 B）列号 C）元素值 D）非零元素个数
（9）快速排序在最坏情况下的时间复杂度为（　　　）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2)
（10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（　　　）。
A）O(n) B）O(1) C）O(log2n) D）O(n2)
二、（本题8分）
已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
三、（本题8分）
请画出如下图所示的邻接矩阵和邻接表。

四、（每小题4分，共8分）
设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，有向边上的权值表示活动的天数）。

（1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。
五、（本题8分）
一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。
六、（本题8分）
假设把n个元素的序列（a1,a2,…an）满足条件ak<max{at|1≤t≤k}的元素ak称为“逆序元素”。若在一个无序序列中有一对元素ai>aj(i<j)，试问，当ai与aj相互交换后，该序列中逆序元素的个数一定不会增加，这句话对不对？如果对，请说明为什么？如果不对，请举一例说明。
七、（本题8分）
带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；
②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；
③重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。
八、（本题8分）
已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。
九、（本题9分）
已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。
十、（本题15分）
编写一个算法求二又树的深度。
模拟试题（三）参考答案
一、单项选择题（每小题 2 分，共20分）
（1）A （2）A （3）B （4）C （5）B
（6）B （7）D （8）B （9）D （10）C
二、（本题8分）
用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
三、（本题8分）
邻接矩阵：

邻接表如下图所示：

四、（每小题4分，共8分）
（1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。
（2）v3事件的最早开始时间是13。
五、（本题8分）
如下图所示的有向图，只有一个顶点的入度为0外，其他每个顶点的入度都为1，因为非连通，所以此图却不是有向树。

六、（本题8分）
不对，例如序列｛3、3、4、2、l｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。
七、（每小题4分，共8分）
该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为 A→D→C。

八、（