四川大学数据结构期终复习

四川大学四川大学“精品课程精品课程”计算机科学与技术专业（本科）计算机科学与技术专业（本科）数据结构与算法分析数据结构与算法分析课程课程考试说明与模拟试卷考试说明与模拟试卷第一部分第一部分 考试说明考试说明数据结构与算法分析数据结构与算法分析是计算机科学与技术专业统设的一门重要的必修专业基础 课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的 插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具 体实现的算法。由于本课程的主教材采用 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. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。 9Josephus 问题的求解过程。 10顺序表和线性链表的性能比较及各自使用背景。 对于本章的其余内容均作一般掌握。对于本章的其余内容均作一般掌握。第三章第三章 数组和广义表数组和广义表 重点掌握的内容：重点掌握的内容： 1.1. 多维数组的逻辑结构特征。 2.2. 多维数组的顺序存储结构及地址计算公式。多维数组的顺序存储结构及地址计算公式。 3 3数组是一种随机存取结构的原因。 4特殊矩阵和稀疏矩阵的概念。 5特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。 6. 稀疏矩阵的定义和三元组线性表及三列二维数组表示。稀疏矩阵的定义和三元组线性表及三列二维数组表示。 7. 稀疏矩阵的顺序存储、带行指针向量的链接存储，在每一种存储中非零元素结 点的结构。 8. 稀疏矩阵的转置运算。 9. 广义表的定义和表示，广义表长度和深度的计算。 10广义表上的求表头、表尾运算。广义表上的求表头、表尾运算。 5. 广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算 法，它们对应的时间复杂度。 一般掌握的内容：一般掌握的内容： 稀疏矩阵转置的算法描述。对于本章的其余内容均作一般了解。第四章第四章 栈和队列栈和队列 重点掌握的内容：重点掌握的内容： 1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返 回值类型和参数表中每个参数的作用。 2. 栈的顺序存储结构的类型定义，即 Stack 类型的定义和每个域的定义及作用。 3栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。 5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的 方法。6给定给定 n n 个栈元素个栈元素, , 出栈可能或不可能的序列数。出栈可能或不可能的序列数。 7. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、 返回值类型和参数表中每个参数的作用。 8. 队列的顺序存储结构的类型定义，即 Queue 类型的定义和每个域的定义及作用。9. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。 10. 利用栈和队列解决简单问题的算法分析和设计。 11双端队的概念及可能出队序列。 12队和栈的应用背景，如队和栈的应用背景，如 cpucpu 队、进程队、打印机队。队、进程队、打印机队。 1313链队的各种存储表示。链队的各种存储表示。 一般掌握的内容：一般掌握的内容： 1. 后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。 2. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。 对于本章的其余内容均作一般了解。第五章第五章 字符串字符串 重点掌握的内容：重点掌握的内容： 1. 串的有关概念及基本运算。 2. 串与线性表的关系。 3串的各种存储结构。 4一个串中真子串和子串个数的确定。一个串中真子串和子串个数的确定。 一般掌握的内容：一般掌握的内容： 1. 串上各种运算的实现及其时间性能分析。 2. 使用 C+提供的操作函数构造与串相关的算法解决简单的应用问题。第六章第六章 树和二叉树树和二叉树 重点掌握的内容：重点掌握的内容： 1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。 2. 树和二叉树的概念，如结点的度、树的度、树叶、分枝结点、树的层数、树的 深度等。 3不同结点数的树和二叉树的形态。 4. 树和二叉树的性质，如已知树或二叉树的深度 h 可求出相应的最多结点数，已 知结点数 n 可求出对应树或二叉树的最大和最小高度。 5. 二叉树中结点的编号规则和对应的顺序存储结构。 6. 二叉树的链接存储结构及存储结点的类型定义，即 BTreeNode 类型的定义和每 个域的定义及作用。 7. 二叉树的先序、中序、后序、遍历的递归过程和递归算法，中序遍历的非递归二叉树的先序、中序、后序、遍历的递归过程和递归算法，中序遍历的非递归 算法，按层遍历的过程和算法，每种算法的时间复杂度。算法，按层遍历的过程和算法，每种算法的时间复杂度。 8二叉树的先序、中序、后序遍历序列，唯一确定一棵二叉树的原则。二叉树的先序、中序、后序遍历序列，唯一确定一棵二叉树的原则。9 9算术表达式的二叉树表示及逆波兰表达式、中缀表示。算术表达式的二叉树表示及逆波兰表达式、中缀表示。 一般掌握的内容：一般掌握的内容： 1. 普通树的链接存储结构，GTreeNode 类型的定义和每个域的定义及作用。 2普通树的先根、后根和按层遍历的过程普通树的先根、后根和按层遍历的过程及算法。 3. 在链接存储的二叉树上实现指定功能的算法分析和设计。 对于本章的其余内容均作一般了解。二叉树的应用二叉树的应用 重点掌握的内容：重点掌握的内容： 1. 二叉搜索树的定义和性质、建立。二叉搜索树的定义和性质、建立。 2. 二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素查找一个元素 的查找长度，即从树根结点到该结点的路径上的结点数。的查找长度，即从树根结点到该结点的路径上的结点数。 3. 二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度，根据一组数据 生成一棵二叉搜索树的过程。 4. 堆的定义和顺序存储结构，小根堆和大根堆的异同及堆的判别、建立堆的过程。堆的定义和顺序存储结构，小根堆和大根堆的异同及堆的判别、建立堆的过程。5. 向堆中插入元素的过程、算法描述及时间复杂度。 6. 从堆中删除元素的过程、算法描述及时间复杂度。 7. 哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈 夫曼树的过程。夫曼树的过程。 8顺序二叉树及二叉链表表示二叉树。顺序二叉树及二叉链表表示二叉树。 9已知关键字序列已知关键字序列22,16,38,89,5622,16,38,89,56，1616，7979，试构造平衡二叉树。，试构造平衡二叉树。 对本章的其余内容均作一般了解。第七章第七章 图图 重点掌握的内容：重点掌握的内容： 1. 图的顶点集和边集的表示。 2. 图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连 通图、权、网等。 3. 图的邻接矩阵、邻接表、图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构及相应的空间复 杂度。 4. 存储图使用的 vexlist, adjmatrix, adjlist, edgenode, edgeset, edge 等 类型的定义及用途。 5. 图的深度优先和广度优先搜索遍历的过程。 6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描 述以及相应的时间复杂度。 7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描 述以及相应的时间复杂度。8. 图的生成树（图的生成树（若一个具有若一个具有 n 个顶点，个顶点，e 条边的无向图是一个森林条边的无向图是一个森林（ne） ，则该森林中必有多少棵树。，则该森林中必有多少棵树。）、深度优先生成树和广度优先生成树、生）、深度优先生成树和广度优先生成树、生成树的权、最小生成树等的定义。成树的权、最小生成树等的定义。 9. 根据普里姆算法求图的最小生成树的过程。根据普里姆算法求图的最小生成树的过程。 1010根据克鲁斯卡尔算法求图的最小生成树的过程。根据克鲁斯卡尔算法求图的最小生成树的过程。 11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示 的图进行拓扑排序的过程。 12强连通图的最少边数。强连通图的最少边数。 一般掌握的内容：一般掌握的内容： 1根据普里姆算法求图的最小生成树的算法描述。 2根据克鲁斯卡尔算法求图的最小生成树的算法描述。 3. 对用邻接表表示的图进行拓扑排序的和算法描述。 对本章的其余内容均作一般了解。第八章第八章 查找查找 重点掌握的内容：重点掌握的内容： 1. 在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找 长度和时间复杂度。长度和时间复杂度。 2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间 复杂度，二