四川大学“精品课程” 计算机科学与技术专业（本科） 《数据结构与算法分析》课程
考试说明与模拟试卷 第一部分 考试说明
数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用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. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算