尧图网站建设 
简介这份《西安电子科技大学-数据结构与算法-期末知识点总结》面向高校计算机及相关专业学生尤其适合备考数据结构期末、梳理课程框架或准备考研复习的读者使用。内容围绕基本概念、线性表、栈与队列、树与二叉树、图、查找与排序算法展开对顺序表与单链表的存储结构对比、循环队列判空判满条件、二叉树性质与遍历方式等高频考点均有归纳可作为课堂笔记之外的补充提纲。资源包共1个PDF文件约2.09MB篇幅紧凑便于打印或移动端随时翻阅。目前已有1230人学习下载说明其在同类复习资料中具有一定参考价值。读者可借助它快速定位薄弱章节对照教材补齐概念细节并在考前集中回顾算法特性、时间复杂度与典型结构操作等易错点提升复习效率。1. 西电数据结构期末知识点总结一份能直接对着复习的 PDF 该怎么用期末周翻遍整本严蔚敏教材却抓不住重点这大概是每个计算机专业学生都经历过的场景。这份西安电子科技大学的数据结构与算法期末知识点总结 PDF把基本概念、线性表、栈与队列、树与二叉树、图、查找、排序七大模块压缩成了一份可以直接对着刷的提纲。它不是教材的替代品而是一份考点地图——告诉你哪些定义必须背、哪些代码必须手写、哪些复杂度必须会推。适合正在准备数据结构期末考、考研 408 复习初期需要快速梳理框架、或者面试前想系统过一遍基础的人。我拿到这份资料的第一反应是如果当年期末有这个东西至少能省下三天翻书的时间。这份总结的覆盖面相当完整从数据元素、数据项这些基本单位到哈夫曼编码、拓扑排序、关键路径这些容易出大题的知识点都有明确的条目。尤其值得一提的是它把算法分析部分单独拎出来做了总结包括递归方程求解、贪心算法和动态规划的基本要素这在一般的期末提纲里不常见。接下来我会按这份 PDF 的知识模块逐块拆解怎么用它复习、哪些地方需要额外补代码、哪些概念容易在考试里翻车。2. 线性表与栈队列顺序表和链表的代码手写要点2.1 顺序表的结构体定义与插入删除边界这份总结里给出了顺序表的结构体定义但考试时经常要求手写插入和删除的完整代码。先看结构体#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; // 存储元素的数组 int length; // 当前表长 } SqList;MAXSIZE是预定义的最大容量elem从下标 0 开始存数据length记录当前实际元素个数。考试里常见的坑是插入位置的范围判断——合法插入位置是 1 到length1不是 0 到length。因为教材里的位置是 1-based 的但数组是 0-based 的这个转换错了后面全错。插入操作的核心逻辑int ListInsert(SqList *L, int i, DataType e) { if (i 1 || i L-length 1) return 0; // 位置非法 if (L-length MAXSIZE) return 0; // 表满 for (int j L-length; j i; j--) { L-elem[j] L-elem[j - 1]; // 从后往前挪腾出位置 } L-elem[i - 1] e; // 注意下标转换第i个位置对应elem[i-1] L-length; return 1; }循环从L-length开始递减到i每次把elem[j-1]搬到elem[j]。为什么从后往前因为从前往后会覆盖掉还没搬走的元素。平均移动次数是 n/2所以时间复杂度 O(n)。删除操作类似循环方向相反从i到length-1每次把后面的元素往前覆盖平均移动 (n-1)/2 次。2.2 单链表的头结点与空表判定总结里明确区分了带头结点和不带头结点的空表判定这是考试选择题的高频考点。带头结点的空表是L-next NULL不带头结点的是L NULL。循环单链表为空的判定是L-next L这个容易和单链表搞混。单链表的结构体typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList;头结点的data域不存有效数据next指向第一个实际元素。插入操作如果带头结点就不用特殊处理在表头插入的情况代码更统一。考试里如果题目没明确说带头结点默认按带头结点写除非题目给了不带头结点的结构。按值查找和按序号查找的代码要能默写。按序号查找GetElem(L, i)需要从第一个结点开始走i次时间复杂度 O(n)。按值查找LocateElem(L, e)最坏也是 O(n)。插入和删除如果已经定位到位置只需要改指针时间复杂度 O(1)但定位本身要 O(n)所以整体还是 O(n)。2.3 循环队列的队空队满判定与元素个数计算循环队列的判定条件是必考内容。总结里写了队空front rear队满(rear1) % m front。注意队满用的是“牺牲一个存储单元”的方案实际最多存 m-1 个元素。元素个数公式是(rear - front m) % m这个公式在选择题里经常出现。#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; int front, rear; // 队头、队尾指针 } SqQueue; // 入队 int EnQueue(SqQueue *Q, DataType e) { if ((Q-rear 1) % MAXSIZE Q-front) return 0; // 队满 Q-elem[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return 1; } // 出队 int DeQueue(SqQueue *Q, DataType *e) { if (Q-front Q-rear) return 0; // 队空 *e Q-elem[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }入队时先存元素再移动rear出队时先取元素再移动front。取模操作% MAXSIZE是实现循环的关键。如果不用取模rear一直加会越界。考试里如果要求不牺牲存储单元的方案需要额外加一个tag标志或者用size计数但这份总结采用的是最经典的牺牲单元法期末考基本够用。栈的顺序存储和链式存储也要能写。顺序栈的top指针初始化为 -1入栈时top再存出栈时先取再top--。链栈用不带头结点的单链表入栈就是头插法出栈就是删头结点。这些代码在总结里没有完整给出但考试大概率要手写建议对着教材补全。3. 树与二叉树从性质推导到遍历代码的完整链路3.1 二叉树五条性质的推导与考试用法总结里列了二叉树的五条核心性质每一条都可能出计算题。第一条第 i 层至多有 2^(i-1) 个结点。第二条深度为 k 的二叉树至多有 2^k - 1 个结点。第三条叶子结点数 n0 n2 1这条最重要推导过程是 n n0 n1 n2 和 n - 1 2n2 n1 联立消去 n 和 n1。第四条n 个结点的完全二叉树深度为 floor(log2 n) 1。第五条完全二叉树中结点 i 的双亲是 floor(i/2)左孩子是 2i右孩子是 2i1。考试里最常见的题型是给出一组条件求叶子结点数。比如“一棵二叉树有 10 个度为 2 的结点5 个度为 1 的结点求叶子结点数”直接用 n0 n2 1 11。如果题目给的是总结点数 n 和某种结点的度数先列方程再解。完全二叉树的编号关系在堆排序和顺序存储里反复用到必须记牢。3.2 二叉链表遍历的递归实现与非递归思路二叉链表的结构体typedef struct BTNode { DataType data; struct BTNode *lchild, *rchild; } BTNode, *BinTree;先序、中序、后序的递归代码必须能默写。以中序为例void InOrder(BinTree T) { if (T ! NULL) { InOrder(T-lchild); // 递归遍历左子树 visit(T); // 访问根结点 InOrder(T-rchild); // 递归遍历右子树 } }先序就是把visit(T)放到最前面后序放到最后面。递归代码简洁但考试有时要求非递归版本中序非递归用栈实现一路向左压栈弹出时访问然后转向右子树。先序非递归也是用栈但访问时机在入栈前。后序非递归最难需要记录上一个访问的结点来判断是从左子树返回还是右子树返回。遍历序列还原二叉树是必考大题。已知先序和中序可以唯一确定一棵二叉树已知后序和中序也可以。但已知先序和后序不行因为无法区分只有一个孩子的情况。还原的步骤先序的第一个是根在中序里找到根的位置左边是左子树的中序右边是右子树的中序然后递归处理。考试时建议先画图再写代码避免下标算错。3.3 哈夫曼树构造与编码生成的手算流程哈夫曼树的构造是每次取两个权值最小的结点合并新结点的权值是两者之和放回集合继续选。这个过程在纸上手算比写代码更常考。构造完成后左分支标 0右分支标 1从根到叶子的路径就是该叶子的哈夫曼编码。带权路径长度 WPL 的计算是所有叶子结点的权值乘以路径长度之和。考试里经常要求先构造哈夫曼树再算 WPL。注意哈夫曼树不唯一因为左右子树可以交换但 WPL 是唯一的。哈夫曼编码是前缀码任何一个编码都不是另一个编码的前缀这保证了译码无歧义。总结里还提到了线索二叉树ltag和rtag为 0 时表示指向子树为 1 时表示指向前驱或后继。n 个结点的二叉链表有 n1 个空链域这些空链域可以用来存线索。线索化的过程就是遍历过程中把空指针改成指向前驱或后继。考试里如果考线索二叉树通常要求画出线索化后的图或者写出中序线索化的代码重点理解pre指针的维护。4. 图与查找排序算法手算流程和复杂度对比4.1 邻接矩阵与邻接表的选型与 DFS/BFS 遍历图的存储结构选择取决于图的稠密程度。邻接矩阵用二维数组存边空间 O(n^2)适合稠密图。邻接表用链表存每个顶点的邻接点空间 O(ne)适合稀疏图。总结里给出了邻接表的弧结点和顶点结点定义typedef struct ArcNode { int adjvex; // 邻接点在顶点数组中的下标 struct ArcNode *nextarc; // 指向下一个邻接点 } ArcNode; typedef struct VexNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一个邻接点 } VexNode;DFS 用递归或栈实现BFS 用队列实现。DFS 的时间复杂度邻接矩阵 O(n^2)邻接表 O(ne)。BFS 同理。考试里常考给定一个图写出从某个顶点出发的 DFS 和 BFS 序列。注意邻接表中邻接点的顺序会影响遍历序列如果题目没指定顺序一般按编号从小到大。最小生成树的两个算法要能区分。Prim 算法从一个顶点开始每次选连接已选集合和未选集合的最小边时间复杂度 O(n^2)适合稠密图。Kruskal 算法把所有边排序每次选最小且不构成环的边时间复杂度 O(e log e)适合稀疏图。考试里如果给出一个带权图要求分别用两种算法求最小生成树注意 Prim 从指定顶点开始Kruskal 从全局最小边开始。4.2 折半查找的判定树与哈希冲突处理折半查找的前提是表有序且顺序存储。查找过程用low、high、mid三个指针每次比较mid位置的元素然后缩小范围。判定树的构造是考试重点把mid作为根左半部分递归构造左子树右半部分递归构造右子树。查找成功的平均查找长度 ASL 等于每个结点所在层数之和除以结点总数。哈希表的冲突解决方法总结里列了开放定址法和拉链法。开放定址法又分线性探测、二次探测和再哈希。线性探测容易产生堆积二次探测可以缓解但可能探测不到所有空位。拉链法把冲突的元素挂在同一个链表中适合冲突较多的情况。装填因子 α 表中元素个数 / 表长α 越大冲突越多。考试里常考给定关键字序列和哈希函数要求画出哈希表并计算 ASL。4.3 排序算法的稳定性与时间复杂度速查总结末尾的排序算法对比表是复习的核心。直接插入排序稳定平均和最坏都是 O(n^2)辅助空间 O(1)。快速排序不稳定平均 O(n log n)最坏 O(n^2)辅助空间 O(log n)。归并排序稳定平均和最坏都是 O(n log n)辅助空间 O(n)。堆排序不稳定平均和最坏都是 O(n log n)辅助空间 O(1)。简单选择排序稳定O(n^2)O(1)。基数排序稳定O(d(nr))O(r)。选择排序方法的依据n 较小用直接插入或简单选择初始基本有序用直接插入或冒泡n 较大用快排、堆排或归并。快排被认为是基于比较的内部排序中最好的方法但最坏情况会退化。考试里经常给一个序列要求写出每一趟排序后的结果注意不同算法的“一趟”定义不同冒泡一趟是把最大的沉到底快排一趟是完成一次划分归并一趟是合并相邻的两个子序列。堆排序的建堆过程是从最后一个非叶子结点开始向下调整最后一个非叶子结点的下标是 floor(n/2)。调整时比较父结点和左右孩子把最大的换上去然后继续向下调整被换下来的结点。建堆的时间复杂度是 O(n)不是 O(n log n)这个容易搞错。排序阶段每次把堆顶和最后一个元素交换然后调整堆共 n-1 次每次 O(log n)所以总时间是 O(n log n)。5. 算法设计大题避坑递归方程、贪心选择和动态规划边界5.1 递归方程求解的三种情况与主定理总结里给出了递归方程 T(n) aT(n/b) D(n) 的三种情况。当 D(n) 为常数 c 时T(n) O(n^(log_b a))。当 D(n) 为线性函数 cn 时比较 a 和 b 的大小a b 则 T(n) O(n^(log_b a))a b 则 T(n) O(n log n)a b 则 T(n) O(n)。当 D(n) 为幂函数 n^x 时比较 a 和 b^x 的大小规则类似。考试里常见的递归方程是 T(n) 2T(n/2) n这里 a2b2D(n)n 是线性的ab所以 T(n) O(n log n)。归并排序和快排的平均情况都是这个方程。T(n) 4T(n/2) na4b2a b所以 T(n) O(n^2)。T(n) 4T(n/2) n^3a4b2b^38a 8所以 T(n) O(n^3)。这些推导在考试里通常要求写出过程不能只写结果。汉诺塔问题的递归方程是 T(n) 2T(n-1) 1这是减法形式的递减展开后 T(n) 2^n - 1时间复杂度 O(2^n)。二分查找的递归方程是 T(n) T(n/2) 1a1b2D(n)1 是常数T(n) O(log n)。这些经典问题的方程要能快速写出并求解。5.2 贪心算法适用性判断与反例构造贪心算法的核心是每一步都选当前最优但局部最优不一定导致全局最优。总结里明确指出最小生成树问题、单源最短路径问题、旅行商问题、0-1 背包问题贪心算法不能找到最优解。活动安排问题、最优装载问题贪心算法可以找到最优解。考试里如果要求判断一个问题能否用贪心算法通常需要构造反例。比如 0-1 背包问题贪心策略是按单位价值排序但可能存在一个单位价值稍低但重量刚好填满背包的组合更优。构造反例的方法是找两个物品一个单位价值高但重量大另一个单位价值低但重量小背包容量刚好只能装其中一个或两个的组合。活动安排问题的贪心策略是按结束时间排序每次选最早结束且不与已选活动冲突的。这个策略的正确性可以用交换论证证明假设最优解的第一个活动不是最早结束的把它换成最早结束的不会减少后续可选活动。考试里如果要求证明贪心选择性质通常用这种交换论证。5.3 动态规划填表顺序与回溯路径动态规划的两个基本要素是最优子结构和重叠子问题。最优子结构指问题的最优解包含子问题的最优解重叠子问题指递归求解时会重复计算相同的子问题。动态规划的步骤找出最优解性质并刻画结构特征递归定义最优解自底向上计算并保存根据信息构造最优解。最短路径的动态规划填表是从源点开始逐阶段往后推。总结里给出了一个具体的计算例子阶段 1 初始化直接相连的边阶段 2 到阶段 4 逐步取最小值。填表时注意每个阶段只依赖前一个阶段的结果所以可以按阶段顺序计算。考试里如果要求写出填表过程和最终路径建议画一个表格行是阶段列是顶点每格填当前最短距离和前驱顶点。回溯法求最优解时需要记录路径。以 0-1 背包为例用bestv记录当前最优价值用bestx记录最优解向量。搜索过程中如果当前价值加上剩余物品的上界不超过bestv就剪枝。分支限界法用优先队列代替回溯法的栈每次扩展上界最大的结点适合求最优解而不是所有解。考试里如果考分支限界法通常要求写出评价函数和搜索过程重点理解“限界”就是剪掉不可能产生最优解的分支。5.4 常见翻车点排查现象折半查找的判定树画错ASL 算出来和答案对不上。原因通常是mid的取法不一致。教材里mid floor((lowhigh)/2)有些题解用ceil导致判定树结构不同。解决方法是先确认题目用的哪种取法然后统一按这个规则画树。如果题目没指定默认用floor。现象哈夫曼编码的 WPL 算错。原因可能是把非叶子结点的权值也加进去了。WPL 只计算叶子结点的权值乘以路径长度非叶子结点的权值是合并产生的不参与 WPL 计算。解决方法是构造完哈夫曼树后只标记叶子结点逐个算路径长度。现象快速排序一趟划分后序列写错。原因通常是基准元素的选择和交换顺序搞混。教材里通常选第一个元素作为基准然后用low和high双指针从两端向中间扫描high先动找到比基准小的就换到low位置然后low动找到比基准大的换到high位置。解决方法是严格按“high 先动”的顺序模拟不要凭感觉。现象Prim 算法和 Kruskal 算法求出的最小生成树不一样以为算错了。原因是最小生成树可能不唯一当图中存在相同权值的边时不同算法可能选出不同的边集但总权值相同。解决方法是检查总权值是否一致如果一致就没问题。现象拓扑排序的序列不唯一和答案对不上。原因是当有多个入度为 0 的顶点时选择顺序不同会导致不同序列。解决方法是按题目要求的顺序选如果题目没要求通常按编号从小到大。考试里如果只要求写出一个合法序列任意合法序列都算对。5.5 复杂度分析的常见误区时间复杂度 O 记号表示上界Ω 表示下界Θ 表示同阶。考试里如果问“算法的时间复杂度”通常指最坏情况下的上界用 O 表示。如果问“至少需要”用 Ω。如果问“精确阶”用 Θ。常见误区是把 O 和 Θ 混用比如快排的平均时间复杂度是 Θ(n log n)最坏是 O(n^2)不能笼统说快排是 O(n log n)。空间复杂度的计算要注意递归调用的栈空间。快排的递归深度平均是 O(log n)最坏是 O(n)所以辅助空间平均 O(log n)最坏 O(n)。归并排序需要额外的数组存合并结果辅助空间 O(n)。堆排序是原地排序辅助空间 O(1)。这些在选择题里经常考要能快速判断。多项式时间算法的排序O(1) O(log n) O(n) O(n log n) O(n^2) O(n^3)。指数时间算法的排序O(2^n) O(n!) O(n^n)。约定 log n 表示以 2 为底的对数。考试里如果要求按增长速度排序先判断是多项式还是指数再在同类里比较。5.6 从知识点到答题的转化技巧这份 PDF 的定位是知识点提纲不是题库。复习时建议先过一遍提纲确认每个概念都能用自己的话解释然后找历年真题练习。选择题重点看基本概念和复杂度对比填空题重点看结构体定义和算法步骤大题重点看遍历序列还原、最小生成树、最短路径、排序过程模拟。手写代码题通常考线性表的插入删除、二叉树的遍历、图的 DFS/BFS。写代码时先写结构体定义再写函数框架最后填核心逻辑。注意边界条件的判断比如空表、表满、位置非法。注释不需要写太多但关键步骤要标出来方便检查。算法设计题通常考贪心或动态规划。先判断问题类型如果满足贪心选择性质就用贪心否则用动态规划。动态规划先定义状态和转移方程再确定填表顺序最后回溯构造解。考试时如果时间不够至少把状态定义和转移方程写出来能拿步骤分。从那以后我每次复习数据结构都会先把这份提纲过一遍把不熟悉的知识点标记出来然后针对性地翻教材补代码。提纲负责告诉我“考什么”教材负责告诉我“为什么”两者配合才能既快又稳。希望帮到你。本文还有配套的精品资源点击获取 西电数据结构期末知识点总结PDF：考点地图与复习指南
简介这份《西安电子科技大学-数据结构与算法-期末知识点总结》面向高校计算机及相关专业学生尤其适合备考数据结构期末、梳理课程框架或准备考研复习的读者使用。内容围绕基本概念、线性表、栈与队列、树与二叉树、图、查找与排序算法展开对顺序表与单链表的存储结构对比、循环队列判空判满条件、二叉树性质与遍历方式等高频考点均有归纳可作为课堂笔记之外的补充提纲。资源包共1个PDF文件约2.09MB篇幅紧凑便于打印或移动端随时翻阅。目前已有1230人学习下载说明其在同类复习资料中具有一定参考价值。读者可借助它快速定位薄弱章节对照教材补齐概念细节并在考前集中回顾算法特性、时间复杂度与典型结构操作等易错点提升复习效率。1. 西电数据结构期末知识点总结一份能直接对着复习的 PDF 该怎么用期末周翻遍整本严蔚敏教材却抓不住重点这大概是每个计算机专业学生都经历过的场景。这份西安电子科技大学的数据结构与算法期末知识点总结 PDF把基本概念、线性表、栈与队列、树与二叉树、图、查找、排序七大模块压缩成了一份可以直接对着刷的提纲。它不是教材的替代品而是一份考点地图——告诉你哪些定义必须背、哪些代码必须手写、哪些复杂度必须会推。适合正在准备数据结构期末考、考研 408 复习初期需要快速梳理框架、或者面试前想系统过一遍基础的人。我拿到这份资料的第一反应是如果当年期末有这个东西至少能省下三天翻书的时间。这份总结的覆盖面相当完整从数据元素、数据项这些基本单位到哈夫曼编码、拓扑排序、关键路径这些容易出大题的知识点都有明确的条目。尤其值得一提的是它把算法分析部分单独拎出来做了总结包括递归方程求解、贪心算法和动态规划的基本要素这在一般的期末提纲里不常见。接下来我会按这份 PDF 的知识模块逐块拆解怎么用它复习、哪些地方需要额外补代码、哪些概念容易在考试里翻车。2. 线性表与栈队列顺序表和链表的代码手写要点2.1 顺序表的结构体定义与插入删除边界这份总结里给出了顺序表的结构体定义但考试时经常要求手写插入和删除的完整代码。先看结构体#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; // 存储元素的数组 int length; // 当前表长 } SqList;MAXSIZE是预定义的最大容量elem从下标 0 开始存数据length记录当前实际元素个数。考试里常见的坑是插入位置的范围判断——合法插入位置是 1 到length1不是 0 到length。因为教材里的位置是 1-based 的但数组是 0-based 的这个转换错了后面全错。插入操作的核心逻辑int ListInsert(SqList *L, int i, DataType e) { if (i 1 || i L-length 1) return 0; // 位置非法 if (L-length MAXSIZE) return 0; // 表满 for (int j L-length; j i; j--) { L-elem[j] L-elem[j - 1]; // 从后往前挪腾出位置 } L-elem[i - 1] e; // 注意下标转换第i个位置对应elem[i-1] L-length; return 1; }循环从L-length开始递减到i每次把elem[j-1]搬到elem[j]。为什么从后往前因为从前往后会覆盖掉还没搬走的元素。平均移动次数是 n/2所以时间复杂度 O(n)。删除操作类似循环方向相反从i到length-1每次把后面的元素往前覆盖平均移动 (n-1)/2 次。2.2 单链表的头结点与空表判定总结里明确区分了带头结点和不带头结点的空表判定这是考试选择题的高频考点。带头结点的空表是L-next NULL不带头结点的是L NULL。循环单链表为空的判定是L-next L这个容易和单链表搞混。单链表的结构体typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList;头结点的data域不存有效数据next指向第一个实际元素。插入操作如果带头结点就不用特殊处理在表头插入的情况代码更统一。考试里如果题目没明确说带头结点默认按带头结点写除非题目给了不带头结点的结构。按值查找和按序号查找的代码要能默写。按序号查找GetElem(L, i)需要从第一个结点开始走i次时间复杂度 O(n)。按值查找LocateElem(L, e)最坏也是 O(n)。插入和删除如果已经定位到位置只需要改指针时间复杂度 O(1)但定位本身要 O(n)所以整体还是 O(n)。2.3 循环队列的队空队满判定与元素个数计算循环队列的判定条件是必考内容。总结里写了队空front rear队满(rear1) % m front。注意队满用的是“牺牲一个存储单元”的方案实际最多存 m-1 个元素。元素个数公式是(rear - front m) % m这个公式在选择题里经常出现。#define MAXSIZE 100 typedef struct { DataType elem[MAXSIZE]; int front, rear; // 队头、队尾指针 } SqQueue; // 入队 int EnQueue(SqQueue *Q, DataType e) { if ((Q-rear 1) % MAXSIZE Q-front) return 0; // 队满 Q-elem[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return 1; } // 出队 int DeQueue(SqQueue *Q, DataType *e) { if (Q-front Q-rear) return 0; // 队空 *e Q-elem[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }入队时先存元素再移动rear出队时先取元素再移动front。取模操作% MAXSIZE是实现循环的关键。如果不用取模rear一直加会越界。考试里如果要求不牺牲存储单元的方案需要额外加一个tag标志或者用size计数但这份总结采用的是最经典的牺牲单元法期末考基本够用。栈的顺序存储和链式存储也要能写。顺序栈的top指针初始化为 -1入栈时top再存出栈时先取再top--。链栈用不带头结点的单链表入栈就是头插法出栈就是删头结点。这些代码在总结里没有完整给出但考试大概率要手写建议对着教材补全。3. 树与二叉树从性质推导到遍历代码的完整链路3.1 二叉树五条性质的推导与考试用法总结里列了二叉树的五条核心性质每一条都可能出计算题。第一条第 i 层至多有 2^(i-1) 个结点。第二条深度为 k 的二叉树至多有 2^k - 1 个结点。第三条叶子结点数 n0 n2 1这条最重要推导过程是 n n0 n1 n2 和 n - 1 2n2 n1 联立消去 n 和 n1。第四条n 个结点的完全二叉树深度为 floor(log2 n) 1。第五条完全二叉树中结点 i 的双亲是 floor(i/2)左孩子是 2i右孩子是 2i1。考试里最常见的题型是给出一组条件求叶子结点数。比如“一棵二叉树有 10 个度为 2 的结点5 个度为 1 的结点求叶子结点数”直接用 n0 n2 1 11。如果题目给的是总结点数 n 和某种结点的度数先列方程再解。完全二叉树的编号关系在堆排序和顺序存储里反复用到必须记牢。3.2 二叉链表遍历的递归实现与非递归思路二叉链表的结构体typedef struct BTNode { DataType data; struct BTNode *lchild, *rchild; } BTNode, *BinTree;先序、中序、后序的递归代码必须能默写。以中序为例void InOrder(BinTree T) { if (T ! NULL) { InOrder(T-lchild); // 递归遍历左子树 visit(T); // 访问根结点 InOrder(T-rchild); // 递归遍历右子树 } }先序就是把visit(T)放到最前面后序放到最后面。递归代码简洁但考试有时要求非递归版本中序非递归用栈实现一路向左压栈弹出时访问然后转向右子树。先序非递归也是用栈但访问时机在入栈前。后序非递归最难需要记录上一个访问的结点来判断是从左子树返回还是右子树返回。遍历序列还原二叉树是必考大题。已知先序和中序可以唯一确定一棵二叉树已知后序和中序也可以。但已知先序和后序不行因为无法区分只有一个孩子的情况。还原的步骤先序的第一个是根在中序里找到根的位置左边是左子树的中序右边是右子树的中序然后递归处理。考试时建议先画图再写代码避免下标算错。3.3 哈夫曼树构造与编码生成的手算流程哈夫曼树的构造是每次取两个权值最小的结点合并新结点的权值是两者之和放回集合继续选。这个过程在纸上手算比写代码更常考。构造完成后左分支标 0右分支标 1从根到叶子的路径就是该叶子的哈夫曼编码。带权路径长度 WPL 的计算是所有叶子结点的权值乘以路径长度之和。考试里经常要求先构造哈夫曼树再算 WPL。注意哈夫曼树不唯一因为左右子树可以交换但 WPL 是唯一的。哈夫曼编码是前缀码任何一个编码都不是另一个编码的前缀这保证了译码无歧义。总结里还提到了线索二叉树ltag和rtag为 0 时表示指向子树为 1 时表示指向前驱或后继。n 个结点的二叉链表有 n1 个空链域这些空链域可以用来存线索。线索化的过程就是遍历过程中把空指针改成指向前驱或后继。考试里如果考线索二叉树通常要求画出线索化后的图或者写出中序线索化的代码重点理解pre指针的维护。4. 图与查找排序算法手算流程和复杂度对比4.1 邻接矩阵与邻接表的选型与 DFS/BFS 遍历图的存储结构选择取决于图的稠密程度。邻接矩阵用二维数组存边空间 O(n^2)适合稠密图。邻接表用链表存每个顶点的邻接点空间 O(ne)适合稀疏图。总结里给出了邻接表的弧结点和顶点结点定义typedef struct ArcNode { int adjvex; // 邻接点在顶点数组中的下标 struct ArcNode *nextarc; // 指向下一个邻接点 } ArcNode; typedef struct VexNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一个邻接点 } VexNode;DFS 用递归或栈实现BFS 用队列实现。DFS 的时间复杂度邻接矩阵 O(n^2)邻接表 O(ne)。BFS 同理。考试里常考给定一个图写出从某个顶点出发的 DFS 和 BFS 序列。注意邻接表中邻接点的顺序会影响遍历序列如果题目没指定顺序一般按编号从小到大。最小生成树的两个算法要能区分。Prim 算法从一个顶点开始每次选连接已选集合和未选集合的最小边时间复杂度 O(n^2)适合稠密图。Kruskal 算法把所有边排序每次选最小且不构成环的边时间复杂度 O(e log e)适合稀疏图。考试里如果给出一个带权图要求分别用两种算法求最小生成树注意 Prim 从指定顶点开始Kruskal 从全局最小边开始。4.2 折半查找的判定树与哈希冲突处理折半查找的前提是表有序且顺序存储。查找过程用low、high、mid三个指针每次比较mid位置的元素然后缩小范围。判定树的构造是考试重点把mid作为根左半部分递归构造左子树右半部分递归构造右子树。查找成功的平均查找长度 ASL 等于每个结点所在层数之和除以结点总数。哈希表的冲突解决方法总结里列了开放定址法和拉链法。开放定址法又分线性探测、二次探测和再哈希。线性探测容易产生堆积二次探测可以缓解但可能探测不到所有空位。拉链法把冲突的元素挂在同一个链表中适合冲突较多的情况。装填因子 α 表中元素个数 / 表长α 越大冲突越多。考试里常考给定关键字序列和哈希函数要求画出哈希表并计算 ASL。4.3 排序算法的稳定性与时间复杂度速查总结末尾的排序算法对比表是复习的核心。直接插入排序稳定平均和最坏都是 O(n^2)辅助空间 O(1)。快速排序不稳定平均 O(n log n)最坏 O(n^2)辅助空间 O(log n)。归并排序稳定平均和最坏都是 O(n log n)辅助空间 O(n)。堆排序不稳定平均和最坏都是 O(n log n)辅助空间 O(1)。简单选择排序稳定O(n^2)O(1)。基数排序稳定O(d(nr))O(r)。选择排序方法的依据n 较小用直接插入或简单选择初始基本有序用直接插入或冒泡n 较大用快排、堆排或归并。快排被认为是基于比较的内部排序中最好的方法但最坏情况会退化。考试里经常给一个序列要求写出每一趟排序后的结果注意不同算法的“一趟”定义不同冒泡一趟是把最大的沉到底快排一趟是完成一次划分归并一趟是合并相邻的两个子序列。堆排序的建堆过程是从最后一个非叶子结点开始向下调整最后一个非叶子结点的下标是 floor(n/2)。调整时比较父结点和左右孩子把最大的换上去然后继续向下调整被换下来的结点。建堆的时间复杂度是 O(n)不是 O(n log n)这个容易搞错。排序阶段每次把堆顶和最后一个元素交换然后调整堆共 n-1 次每次 O(log n)所以总时间是 O(n log n)。5. 算法设计大题避坑递归方程、贪心选择和动态规划边界5.1 递归方程求解的三种情况与主定理总结里给出了递归方程 T(n) aT(n/b) D(n) 的三种情况。当 D(n) 为常数 c 时T(n) O(n^(log_b a))。当 D(n) 为线性函数 cn 时比较 a 和 b 的大小a b 则 T(n) O(n^(log_b a))a b 则 T(n) O(n log n)a b 则 T(n) O(n)。当 D(n) 为幂函数 n^x 时比较 a 和 b^x 的大小规则类似。考试里常见的递归方程是 T(n) 2T(n/2) n这里 a2b2D(n)n 是线性的ab所以 T(n) O(n log n)。归并排序和快排的平均情况都是这个方程。T(n) 4T(n/2) na4b2a b所以 T(n) O(n^2)。T(n) 4T(n/2) n^3a4b2b^38a 8所以 T(n) O(n^3)。这些推导在考试里通常要求写出过程不能只写结果。汉诺塔问题的递归方程是 T(n) 2T(n-1) 1这是减法形式的递减展开后 T(n) 2^n - 1时间复杂度 O(2^n)。二分查找的递归方程是 T(n) T(n/2) 1a1b2D(n)1 是常数T(n) O(log n)。这些经典问题的方程要能快速写出并求解。5.2 贪心算法适用性判断与反例构造贪心算法的核心是每一步都选当前最优但局部最优不一定导致全局最优。总结里明确指出最小生成树问题、单源最短路径问题、旅行商问题、0-1 背包问题贪心算法不能找到最优解。活动安排问题、最优装载问题贪心算法可以找到最优解。考试里如果要求判断一个问题能否用贪心算法通常需要构造反例。比如 0-1 背包问题贪心策略是按单位价值排序但可能存在一个单位价值稍低但重量刚好填满背包的组合更优。构造反例的方法是找两个物品一个单位价值高但重量大另一个单位价值低但重量小背包容量刚好只能装其中一个或两个的组合。活动安排问题的贪心策略是按结束时间排序每次选最早结束且不与已选活动冲突的。这个策略的正确性可以用交换论证证明假设最优解的第一个活动不是最早结束的把它换成最早结束的不会减少后续可选活动。考试里如果要求证明贪心选择性质通常用这种交换论证。5.3 动态规划填表顺序与回溯路径动态规划的两个基本要素是最优子结构和重叠子问题。最优子结构指问题的最优解包含子问题的最优解重叠子问题指递归求解时会重复计算相同的子问题。动态规划的步骤找出最优解性质并刻画结构特征递归定义最优解自底向上计算并保存根据信息构造最优解。最短路径的动态规划填表是从源点开始逐阶段往后推。总结里给出了一个具体的计算例子阶段 1 初始化直接相连的边阶段 2 到阶段 4 逐步取最小值。填表时注意每个阶段只依赖前一个阶段的结果所以可以按阶段顺序计算。考试里如果要求写出填表过程和最终路径建议画一个表格行是阶段列是顶点每格填当前最短距离和前驱顶点。回溯法求最优解时需要记录路径。以 0-1 背包为例用bestv记录当前最优价值用bestx记录最优解向量。搜索过程中如果当前价值加上剩余物品的上界不超过bestv就剪枝。分支限界法用优先队列代替回溯法的栈每次扩展上界最大的结点适合求最优解而不是所有解。考试里如果考分支限界法通常要求写出评价函数和搜索过程重点理解“限界”就是剪掉不可能产生最优解的分支。5.4 常见翻车点排查现象折半查找的判定树画错ASL 算出来和答案对不上。原因通常是mid的取法不一致。教材里mid floor((lowhigh)/2)有些题解用ceil导致判定树结构不同。解决方法是先确认题目用的哪种取法然后统一按这个规则画树。如果题目没指定默认用floor。现象哈夫曼编码的 WPL 算错。原因可能是把非叶子结点的权值也加进去了。WPL 只计算叶子结点的权值乘以路径长度非叶子结点的权值是合并产生的不参与 WPL 计算。解决方法是构造完哈夫曼树后只标记叶子结点逐个算路径长度。现象快速排序一趟划分后序列写错。原因通常是基准元素的选择和交换顺序搞混。教材里通常选第一个元素作为基准然后用low和high双指针从两端向中间扫描high先动找到比基准小的就换到low位置然后low动找到比基准大的换到high位置。解决方法是严格按“high 先动”的顺序模拟不要凭感觉。现象Prim 算法和 Kruskal 算法求出的最小生成树不一样以为算错了。原因是最小生成树可能不唯一当图中存在相同权值的边时不同算法可能选出不同的边集但总权值相同。解决方法是检查总权值是否一致如果一致就没问题。现象拓扑排序的序列不唯一和答案对不上。原因是当有多个入度为 0 的顶点时选择顺序不同会导致不同序列。解决方法是按题目要求的顺序选如果题目没要求通常按编号从小到大。考试里如果只要求写出一个合法序列任意合法序列都算对。5.5 复杂度分析的常见误区时间复杂度 O 记号表示上界Ω 表示下界Θ 表示同阶。考试里如果问“算法的时间复杂度”通常指最坏情况下的上界用 O 表示。如果问“至少需要”用 Ω。如果问“精确阶”用 Θ。常见误区是把 O 和 Θ 混用比如快排的平均时间复杂度是 Θ(n log n)最坏是 O(n^2)不能笼统说快排是 O(n log n)。空间复杂度的计算要注意递归调用的栈空间。快排的递归深度平均是 O(log n)最坏是 O(n)所以辅助空间平均 O(log n)最坏 O(n)。归并排序需要额外的数组存合并结果辅助空间 O(n)。堆排序是原地排序辅助空间 O(1)。这些在选择题里经常考要能快速判断。多项式时间算法的排序O(1) O(log n) O(n) O(n log n) O(n^2) O(n^3)。指数时间算法的排序O(2^n) O(n!) O(n^n)。约定 log n 表示以 2 为底的对数。考试里如果要求按增长速度排序先判断是多项式还是指数再在同类里比较。5.6 从知识点到答题的转化技巧这份 PDF 的定位是知识点提纲不是题库。复习时建议先过一遍提纲确认每个概念都能用自己的话解释然后找历年真题练习。选择题重点看基本概念和复杂度对比填空题重点看结构体定义和算法步骤大题重点看遍历序列还原、最小生成树、最短路径、排序过程模拟。手写代码题通常考线性表的插入删除、二叉树的遍历、图的 DFS/BFS。写代码时先写结构体定义再写函数框架最后填核心逻辑。注意边界条件的判断比如空表、表满、位置非法。注释不需要写太多但关键步骤要标出来方便检查。算法设计题通常考贪心或动态规划。先判断问题类型如果满足贪心选择性质就用贪心否则用动态规划。动态规划先定义状态和转移方程再确定填表顺序最后回溯构造解。考试时如果时间不够至少把状态定义和转移方程写出来能拿步骤分。从那以后我每次复习数据结构都会先把这份提纲过一遍把不熟悉的知识点标记出来然后针对性地翻教材补代码。提纲负责告诉我“考什么”教材负责告诉我“为什么”两者配合才能既快又稳。希望帮到你。本文还有配套的精品资源点击获取