简介《西安电子科技大学-数据结构与算法-期末知识点总结.pdf》是一份面向西电学生与数据结构学习者的期末复习资料紧扣课程大纲适合考前突击与重点速记。文档按专题模块梳理涵盖基本概念、线性表、栈与队列、树与二叉树、图、查找与排序等章节具体包含数据元素与数据项、逻辑结构与物理结构、算法特性顺序表与单链表的存储差异与操作复杂度栈的后进先出、队列的先进先出以及循环队列判满判空条件二叉树性质、存储结构、先序/中序/后序遍历折半查找、快速排序等常用算法。这份PDF为单文件文档大小约2.09MB内容精炼便于打印或在手机/平板上阅读。目前已有1230人学习下载可作为期末复习、考前速记、查漏补缺与核心要点复盘的实用参考。1. 西电《数据结构与算法》期末复习为什么这份知识点总结值得你过三遍西电《数据结构与算法》期末复习最容易翻车的地方不是题目难而是你不知道这门课的考点在卷子上怎么分布。这份期末知识点总结就是把整门课按章节压缩成一份冲刺地图线性表、栈队列、树、图、查找、排序每一章哪些概念必背、哪些代码必写、哪些推导步骤阅卷老师只看结果基本都覆盖到了。适合三类人平时上课听了个大概、考前需要快速建立知识框架的刷题不少但遇到手写代码题就卡壳的以及考研408打算拿数据结构当保底项、想把基础概念一次理清的。我的建议是别把它当通读书当作考前一星期的排查清单用。你不需要从头看到尾按下面的章节优先级哪里薄弱打哪里。2. 从考试结构倒推考点分布先把“背多分”的数据结构章节吃透期末卷子再灵活题型结构大概率是这么拆的选择或填空考概念辨析简答考性质推导应用题考手算过程最后两道大题留给手写算法。这意味着有些知识点是“背了就有分”有些是“理解了才有分”复习策略完全不同。2.1 线性表、栈与队列代码题落笔就错的三个细节线性表这章看着简单但它是全卷失分的重灾区。链表相关代码题阅卷时最常揪的三个细节头结点的使用、指针修改顺序、边界条件判断。很多同学背了“尾插法建表”的代码考试时把p-next s; s-next NULL;的顺序写反或者忘了处理第一个结点时头指针为空的情况——空表插入和尾插是两种不同的写法必须分开记忆。栈和队列的考点集中在两个地方一个是出栈序列的合法性判断另一个是循环队列的队空队满判定。循环队列这里有一个高频选择题陷阱就是front rear到底是空还是满取决于你牺牲了一个存储单元还是加了计数器。西电的期末考试题里循环队列的判空判满条件几乎每年都会出现用牺牲一个单元的做法最经典(rear1) % maxsize front就是满front rear就是空。提示写线性表代码题时先判断“操作的位置在表头、表中还是表尾”三种情况的分支条件不一样。很多代码题丢分不是因为不会写而是因为只写了中间情况。2.2 树与二叉树遍历序列反推结构是必考大题树这章是期末复习的重点章节原因很简单可考的点足够多从性质推导到手写遍历再到哈夫曼编码每一处都能出题。最基础的得分点——二叉树第 i 层最多结点数、深度为 k 的二叉树最多结点总数、n0 n2 1 这类性质属于送分题但你要能做对的是它们的推导过程比如 n0 n2 1 的证明思路是通过边数和度数的关系推导选择题里经常换着说法考你。遍历这一块的难点不是递归写法而是给你一棵树的先序和中序序列让你反推后序序列或还原树的结构。这类题的核心规律只有一句话先序序列的第一个结点是根中序序列里根的左边是左子树、右边是右子树。用这个规律递归切序列几轮就能得到整棵树的结构。注意如果题目只给先序和后序树的形态不唯一这是题目常见的陷阱不要硬画。手写遍历代码时我一般会推荐掌握非递归写法。递归写法大家都会但非递归中序遍历用栈模拟的过程能同时考察你对“入栈时机”的理解是期末和考研共同的高频出题点。下面是完整的非递归中序代码void InOrderTraverse(BiTree T) { if (T NULL) return; // 空树直接返回 Stack S; InitStack(S); // 初始化一个栈 BiTree p T; while (p || !StackEmpty(S)) { // p 非空或栈非空时继续 if (p) { Push(S, p); // 先入栈不访问 p p-lchild; // 向左下走 } else { Pop(S, p); // 弹出栈顶此时左子树已空 printf(%d , p-data); // 访问根结点 p p-rchild; // 转向右子树 } } }逻辑说明外层的 while 循环条件是p 或栈至少一个不为空代表“还有结点没处理”。内层先一路向左入栈走到空后弹出一个结点访问再转向右子树整个过程模拟了“左根右”的顺序。参数说明这里的BiTree是指向二叉树结点的指针类型Stack是定义好的栈结构如果你手写代码时没有InitStack可以直接用一个数组模拟栈把入栈写成s[top] p出栈写成p s[top--]阅卷老师也算对。2.3 图的存储与遍历邻接矩阵和邻接表的得分差异图这章的复习重点有两个最小生成树和最短路径但概念题里存储结构也占了不少分。邻接矩阵适合稠密图判断两点是否相邻的时间复杂度是 O(1)但存储空间是 O(n²)。邻接表适合稀疏图存储空间降到 O(ne)判断相邻需要遍历链表。期末简答题经常问“给定场景选哪种存储”答案不是固定的得分点在你要说出理由——是空间省还是时间快。图遍历里深度优先搜索DFS和广度优先搜索BFS的手算序列是必考题。这里最常见的错误是同一个图从同一个顶点出发因为邻接表里边的存储顺序不同遍历序列就不同。所以你看到题目给的答案和自己算的不一样先别怀疑自己算错了检查一下邻接表里每个顶点的邻接点顺序是不是按题目给的顺序建立的。最小生成树这里Prim 算法适合稠密图Kruskal 算法适合稀疏图这是选填题的高频答案。手算时我提供一个操作习惯Kruskal 就按权值从小到大一条条加边每次加边前确认不形成回路Prim 就从任意顶点出发每次找当前已选顶点集合能连到未选顶点集合的最小权值边。两种算法的时间复杂度分别是 O(n²) 和 O(eloge)简答题很可能让你写出来。2.4 重点概念识记表最后两天过一遍的高频考点清单下面这个表是我带学生期末冲刺时常让他们最后一遍确认的清单考前花半小时逐项过能挡住大部分选择题失分章节必背结论常见的出题方式线性表单链表插入删除的指针操作顺序给代码段问执行结果栈和队列循环队列队空队满条件选择/判断给具体值算结果树n0 n2 1、哈夫曼树带权路径长度选择/填空给叶子权值求 WPL图Prim/Kruskal 适用场景、DFS/BFS 序列给图手算最小生成树或遍历序列查找二分查找的比较次数、平均查找长度ASL给有序序列手算 ASL排序各排序稳定性、时间/空间复杂度选择/填空3. 查找与排序算法设计题的高频出题区就盯六个算法查找和排序是期末大题的主产区。不是说树和图不重要而是查找排序更贴近“给你一个具体问题让你设计算法”的考试形式。而且很多同学发现复习到最后排序的代码是背得最熟、但手写时改动最多的。3.1 二分查找边界条件不写对代码写对了也是零分二分查找的代码几乎年年考但它考的不是你是否知道思路而是你是否能写对边界。我见过太多人在笔试里写while (left right)和while (left right)混着用结果 left 和 right 的更新逻辑没对上要么死循环要么错过目标。这里有一份可以直接抄的局面int binarySearch(int arr[], int n, int key) { int left 0, right n - 1; // 闭区间查找right 指向最后一个元素 while (left right) { // 闭区间用 因为 left right 时还可能命中 int mid left (right - left) / 2; // 防溢出的写法 if (arr[mid] key) return mid; else if (arr[mid] key) left mid 1; // 目标在右半区 else right mid - 1; // 目标在左半区 } return -1; // 循环结束未找到 }逻辑说明当left和right构成闭区间时left right意味着区间里还有一个元素需要检查所以循环条件必须包含等于。找到目标后直接返回下标每次更新区间时mid已经检查过所以左边界取mid 1、右边界取mid - 1。参数说明mid left (right - left) / 2是为了防止left right整数溢出这种写法在刷题平台很常见期末手写代码时用mid (left right) / 2也没问题。手算题里二分查找的平均查找长度 ASL 需要按判定树来算。一棵 n 个结点的判定树每层结点数就是比较次数相同的元素个数用“每层结点数 × 层号求和再除以”计算。这个公式别死记画树最稳。3.2 KMP 算法next 数组别再死记硬背了三步手算最稳KMP 算法在西电期末里属于“老师觉得你该会、但你总觉得没学透”的考点。它考的不是匹配过程的代码而是 next 数组的手算和它对暴力匹配的优化逻辑。暴力枚举是 O(n×m)KMP 把时间复杂度压到 O(nm)这个对比是常考填空。next 数组手算有个三步法我每次都用它第一步把模式串每个位置对应的前缀后缀最长相等长度算出来记为pi数组。第二步next[0]规定为 -1有些教材是 0看你们上课用的定义。第三步从第 1 位开始next[j] pi[j-1]。这样推出来和教材完全一致不用背那套“next[j1] 和 next[j] 的关系”的递归公式。举个例子模式串ABABAC前缀后缀最长相等长度依次是0, 0, 1, 2, 3, 0那么next数组就是-1, 0, 0, 1, 2, 3。手算时注意一个常见坑pi数组求的是“不等于整个串自身”的最长相等前后缀比如ABA的 pi 值最大取到1而不是2因为整个串不能算自己。3.3 七种排序的复杂度与稳定性一张表给你背全附快排手的写代码范例排序这一章期末一定会考 1 到 2 道简答或应用大题“给你一组数写出快排每一趟的结果”或“写出堆排序的建堆过程”。复杂度表属于送分题但稳定性判定经常有人记混。排序方法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(nlogn)O(n²)O(logn)不稳定简单选择排序O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定快速排序的手写代码是期末大题的常客它的核心是 partition 这一步int partition(int arr[], int low, int high) { int pivot arr[low]; // 取第一个元素为枢轴 while (low high) { while (low high arr[high] pivot) high--; // 从右找比枢轴小的 arr[low] arr[high]; // 移过去 while (low high arr[low] pivot) low; // 从左找比枢轴大的 arr[high] arr[low]; // 移过去 } arr[low] pivot; // 枢轴归位 return low; // 返回枢轴最终位置 }逻辑说明这是“挖坑法”把arr[low]的值保存在pivot里low 的位置就成了一个坑。先从右侧找一个比 pivot 小的值填到坑里这时 high 位置变成新坑再从左侧找一个比 pivot 大的值填到 high 去直到 low 和 high 相遇。参数说明内层两个 while 都要带low high条件防止越界比较时用和可以让相同元素不交换稍微提升稳定性——但注意快排整体仍然不稳定。每次 partition 结束后pivot 左边的元素都比它小、右边的都比它大。如果要手算“第一趟快排结果”你得写完整这个 low 和 high 交替扫描的过程阅卷老师会看中间过程给分不要只写最终结果。4. 算法设计题的高频套路递归分治、动态规划、回溯剪枝三条路帮你兜底期末大题最后一道往往不是单纯的某个数据结构实现而是让你设计一个解决具体问题的算法。常见给定场景如“求二叉树最大深度”“判断括号匹配”“求子集和问题”这些题的通用解法套路集中在三块递归与分治、动态规划、回溯剪枝。掌握套路比背代码有效得多。4.1 递归与分治从“求二叉树深度”到“归并排序”分清递推与回归分治算法的核心是三段式分解、解决、合并。写递归代码最容易犯的错误是只写递推、忘了回归条件或者递归出口放的位置不对导致栈溢出。二叉树求最大深度是最经典的递归题int maxDepth(BiTree T) { if (T NULL) return 0; // 递归出口空结点深度为 0 int left maxDepth(T-lchild); // 递归求左子树深度 int right maxDepth(T-rchild); // 递归求右子树深度 return (left right ? left : right) 1; // 较大值加 1 就是本层深度 }逻辑说明return前一层的值被上层接收这就是“回归”过程。递归出口写在函数最前面保证空指针不被解引用。参数说明这里不传附加参数深度信息通过返回值从下往上传递。时间复杂度是 O(n)每个结点访问一次空间复杂度是 O(h)h 是树高最坏情况下树退化成链表时递归栈深度等于 n。如果期末考试让你写斐波那契的递归你写完一定要补一句“存在重复计算”然后顺手给出优化版——用一个数组缓存算过的值这就是记忆化搜索能额外加分。4.2 动态规划从斐波那契到 0-1 背包递推方程要写得让阅卷老师一眼看懂动态规划在西电期末里不一定考难题但一定会考基础模型。最常出现的是求最长公共子序列长度、最大连续子段和、0-1背包。前两个在期末卷子里出现的概率很大因为它们的递推方程好写、好算。最大连续子段和的动态规划思路是dp[i]表示以第 i 个元素结尾的最大子段和。递推方程是dp[i] max(nums[i], dp[i-1] nums[i])最终答案是所有dp[i]里的最大值。拿到一道动态规划题你按五个步骤写就能保证得分第一步定义状态含义dp[i]是什么。第二步写递推方程从dp[i-1]到dp[i]怎么转移。第三步初始化边界dp[0]或dp[0][0]是什么。第四步确定遍历顺序是从前往后还是两层循环。第五步返回哪个状态作为答案。阅卷老师按步骤给分前三步写对就能拿一半分。4.3 回溯与剪枝暴力枚举的进阶版代码量小、拿分稳当题目给的数据规模很小——比如 n 小于 20——暴力枚举往往是可行的但直接枚举所有组合会超时或看着太傻这时候要用回溯配合剪枝。期末考试里回溯法最典型的场景是“求出所有子集”和“迷宫找路径”。常见的模板是进入递归时标记当前选择递归返回时撤销标记。撤销这一步是回溯的精髓很多人写回溯代码漏了撤销导致结果集里全是同一个状态。写代码时记住这句话递归前做选择递归后撤销选择。剪枝的意思是如果当前路径已经不可能得到合法解直接return不再递归下去。比如求子集和时当前和已经超过目标值后面就不用再尝试了。期末答题时回溯题不需要你把所有剪枝优化都写出来但一定要体现出“剪枝”这个意识——在递归入口加一个条件判断阅卷老师看到就会给步骤分。这和考研 408 一脉相承算法设计题最怕的不是笨而是没有思路。5. 期末复习避坑指南四类高频丢分点每条都是血泪经验以下是根据历年学生在复习和考试里最常见的翻车现场整理的避坑记录。老话说得好真题做错不可怕可怕的是同样的坑下次还跳。对着这份清单自查一遍比多做两套卷子都管用。5.1 现象手写算法题时只写代码不写算法思路说明原因很多同学觉得代码对了就行忽略了题目要求里那句“写出算法思想”或“分析算法时间空间复杂度”。期末阅卷的得分点是按步骤给的思路写清楚占 3 至 5 分甚至更多。解决代码前写两句话一句话说明算法核心思想比如“利用栈的后进先出特性实现逆序”一句话写出时间复杂度和空间复杂度。哪怕是强行分析也要写出来——空着肯定零分写了就有机会。5.2 现象快速排序手算时只写最终一趟结果原因快排手算题要求“写出各趟排序结果”阅卷老师实际是想看你对 low 和 high 交替扫描过程的理解。直接写最后结果等于跳过了全部得分步骤得 1 分算运气好。解决每一趟都写清中间过程至少要把每趟结束后的数组状态写出来。推荐用挖坑法的步骤格式标出每一趟的枢轴元素它最后放的位置其他元素按左右分区写清楚。5.3 现象KMP 的 next 数组和上课讲的对不上原因KMP 算法里有 next 数组和 nextval 数组两种不同教材对 next[0] 的定义不一样。有的定义 next[0] 0有的定义为 -1还有的教材直接给 nextval。如果你跟的是西电课堂版以老师讲义为准但你要知道另一个定义的存在不然看到题目的答案会怀疑自己算错了。解决考前去老师 PPT 或讲义里确认 next 数组的定义和下标起点。如果题目明确给出了 next 数组的初始规定按题目来如果没说默认 you 最常用的“从 -1 开始”的版本并在答题时标注清楚。5.4 现象堆排序手算建堆时老是在最后一个非叶子结点上犯迷糊原因建堆要从最后一个非叶子结点开始调整下标是n/2 - 1数组索引从 0 开始。很多人从小到大调整或者从根开始调调完发现序列根本不是堆。解决先画出对应的完全二叉树从n/2 - 1结点开始往前逐个调整每次调整要一直下沉到叶子为止。不要只调一层——新换上去的结点可能继续违反堆的性质。提示期末考前一晚把上面四条通读一遍。你会发现丢分都不是因为不会而是因为“差一点”。6. 考场上最后的验证技巧答案写完别急着交卷花两分钟做这三件事手写算法题的验证方式和平常刷题完全不同没有编译器给你兜底只能靠人工模拟。我给自己定的规则是每道大题写完花两分钟按下面三个步骤走一遍能救回不少粗心分。第一步代入最小边界样例验证代码逻辑。比如写了二分查找就用数组长度n1和n0去脑海里过一遍看循环边界和返回条件是否成立。写了链表删除就考虑删除头结点时头指针是否更新。我见过最多的翻车就是边界条件处理不周而边界样例往往只有一两行验证成本极低。第二步检查复杂度标注是否合理。很多同学算法是 KMP 的复杂度却写了O(n×m)白白送分。写完代码后看一眼循环嵌套层数再结合是否使用了递归把空间复杂度里的递归栈深度标出来。第三步确认题目要求的输出形式是否对上了。有的题要求返回下标有的要求返回元素值有的要求直接打印你代码里如果返回类型写错了就是看懂了算法也拿不到分。这几步做完再翻到选择题检查所有关于时间复杂度和稳定性的判断画没画对。排序稳定性的口诀“插冒归基稳定其他都不稳定”——直接插入、冒泡、归并、基数四个稳定这句话能在三十秒内帮你复查完一整块记忆点。数据结构与算法这门课复习时能做对的唯一技巧是把每个结论落到具体的代码和具体的样例上而不是停留在“我听懂了”。这份知识点总结的价值就是帮你把一整学期的内容压缩成一个考前可执行的排查清单。你花一星期把它吃透比自己闷头翻书两周效率高得多。我当年期末复习时也吃过“看啥都觉得会、一写就废”的亏后来养成的习惯就是每看完一章立刻在纸上默写核心代码写不出来就回头再看——这个方法帮我也帮我的学生渡过了很多次期末。希望帮到你。本文还有配套的精品资源点击获取