数据结构与算法期末复习：从知识点归纳到考场手写代码的6个关键动作

简介这份《西安电子科技大学-数据结构与算法-期末知识点总结》面向高校计算机及相关专业学生尤其适合正在备考数据结构期末、需要系统梳理知识框架的读者。内容围绕基本概念、线性表、栈与队列、树与二叉树、图、查找与排序算法展开对顺序表与单链表的存储结构对比、循环队列的队空队满判定、二叉树性质与遍历方式等高频考点均有归纳可作为复习提纲与考前速查使用。资源包共1个PDF文件约2.09MB页面结构清晰便于打印或平板阅读。目前已有1230人学习下载说明其在同类复习资料中具有一定参考价值。读者可借助这份总结快速定位薄弱章节配合教材与习题查漏补缺提升期末复习效率。1. 数据结构与算法期末复习从「背了忘」到「考场能写」的 6 个关键动作期末周的图书馆里最常见的场景不是没人复习而是复习方式本身出了问题把《数据结构与算法》的知识点总结 PDF 从头翻到尾链表、栈、队列、树、图、排序、查找全都「看过」合上书却写不出一道完整的算法题。这份「西安电子科技大学-数据结构与算法-期末知识点总结.pdf」之所以被反复搜索本质上是因为大家需要的不是又一份目录而是一条能把零散知识点串成可答题能力的路径。数据结构与算法这门课期末考的从来不是记忆力而是你能不能在有限时间里判断该用哪种结构、写出关键代码、算对复杂度。这篇笔记面向正在准备期末、考研 408 数据结构或者想把 C 语言版知识点重新捡起来的人按「先立框架、再攻高频、最后避坑」的顺序把复习动作拆到可以照着执行。2. 先搭骨架数据结构与算法知识点归纳的正确打开方式2.1 为什么按「逻辑结构 存储结构 操作」三列归纳最省时间很多人复习数据结构时习惯按章节顺序抄笔记线性表、栈、队列、串、树、图一路抄下去抄完发现脑子里还是一团。问题在于章节顺序是教材的叙述顺序不是考点的组织顺序。真正高效的归纳方式是给每个数据结构建一张三列表逻辑结构是什么、存储结构怎么实现、核心操作有哪些。比如「栈」这一行逻辑结构是受限线性表存储结构可以是顺序栈或链栈核心操作是入栈、出栈、取栈顶、判空。这样归纳的好处是考试里一旦出现「用两个栈实现队列」这类题你能立刻定位到操作层面而不是从头回忆栈的定义。我一般会建议用一张 A3 纸横过来左边写结构名中间写存储方式右边写操作和时间复杂度。线性表、栈、队列、串、树、二叉树、图、查找结构、排序算法各占一行。这张表填完你对整门课的覆盖范围就有了全局感后面再往里填细节不会出现「复习到图的时候忘了线性表」的情况。数据结构学习最怕的就是碎片化先有骨架再填肉效率差好几倍。2.2 用一张表把线性表、树、图的操作复杂度钉死复杂度是期末必考、也是很多人最容易记混的部分。与其死记不如按操作类型横向对比。下面这张表是我复习时反复用的版本覆盖了最高频的几类结构结构存储方式查找插入删除备注顺序表数组O(1) 按下标O(n)O(n)随机访问快单链表指针O(n)O(1) 已知前驱O(1) 已知前驱不支持随机访问二叉搜索树链式平均 O(log n)平均 O(log n)平均 O(log n)退化成 O(n)平衡二叉树链式O(log n)O(log n)O(log n)需旋转维护哈希表数组链平均 O(1)平均 O(1)平均 O(1)冲突时退化邻接矩阵图二维数组O(1) 查边O(1)O(1)空间 O(n²)邻接表图数组链O(度)O(1)O(度)空间 O(ne)这张表的关键不是背而是理解每一格背后的原因。比如单链表插入为什么是 O(1)前提是「已知前驱节点」如果只给了值要你先找位置那查找本身就是 O(n)。考试里经常在这种前提条件上设陷阱把「已知前驱」偷偷去掉很多人就掉进去了。2.3 复习顺序先线性结构再树最后图与排序知识点归纳做完之后复习顺序也有讲究。我的建议是先攻线性表、栈、队列、串这部分逻辑直观、代码短容易建立信心然后进树和二叉树重点是遍历和递归思维最后才是图和排序因为图算法依赖队列和栈排序依赖数组操作前面的基础不牢后面会很痛苦。每复习完一个模块立刻做三件事手写核心代码、画一遍操作示意图、算一遍复杂度。这三件事做完才算真正过了一遍。3. 高频考点逐个拆链表、KMP、树遍历、排序算法怎么落到笔头3.1 单链表反转与合并手写代码的三个边界链表是期末代码题的重灾区其中反转和合并出现频率最高。很多人觉得自己会一上手就发现指针指丢了。下面是我复习时反复默写的单链表反转模板// 单链表节点定义 typedef struct ListNode { int val; struct ListNode *next; } ListNode; // 反转单链表返回新头节点 ListNode* reverseList(ListNode* head) { ListNode *prev NULL; // 前驱指针初始为空 ListNode *curr head; // 当前指针从头开始 while (curr ! NULL) { ListNode *nextTemp curr-next; // 先保存下一个节点 curr-next prev; // 当前节点指向前驱 prev curr; // 前驱后移 curr nextTemp; // 当前后移 } return prev; // prev 最终指向原链表尾即新头 }这段代码的逻辑核心是「先存后断再移」保存 next、断开当前指针、移动 prev 和 curr。参数上唯一需要注意的是循环终止条件是 curr 为 NULL返回的是 prev 而不是 curr。三个边界必须检查空链表直接返回 NULL、只有一个节点时循环走一次就结束、反转后原头节点的 next 必须为 NULL。我见过太多人写完忘了最后一步导致链表成环考试直接扣分。合并两个有序链表的思路类似用哑节点dummy node可以省掉头节点特判ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy; // 栈上哑节点 ListNode *tail dummy; // 尾指针 while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; // 接上剩余部分 return dummy.next; }哑节点的作用是让「第一个节点」和「后续节点」的处理逻辑统一不用单独判断 tail 是否为空。参数上注意比较用保证稳定性剩余部分直接接上不用循环。3.2 KMP 算法next 数组到底怎么手算不翻车KMP 是字符串章节的必考算法也是很多人复习时的玄学重灾区。核心就一句话next 数组记录的是「模式串当前位置之前的最长相等前后缀长度」。手算的时候不要背公式按下面步骤走第一步next[0] 固定为 -1或 0取决于教材约定西电教材常用 -1 版本。第二步从第二个字符开始看它前面子串的最长相等前后缀。第三步把这个长度填到 next 数组的对应位置。以模式串ababaa为例下标012345字符ababaanext-100123next[3]1 是因为aba的最长相等前后缀是a长度 1next[4]2 是因为abab的最长相等前后缀是ab长度 2。手算时容易错的地方是把「前缀」和「后缀」搞反或者把整个子串本身算进去。记住前后缀不能是子串本身长度必须小于当前子串长度。匹配阶段的代码模板// 计算 next 数组模式串 pat长度 m void getNext(char *pat, int m, int *next) { next[0] -1; int i 0, j -1; while (i m - 1) { if (j -1 || pat[i] pat[j]) { i; j; next[i] j; // 记录最长相等前后缀长度 } else { j next[j]; // 回退 } } } // KMP 匹配返回首次出现下标未找到返回 -1 int kmp(char *text, char *pat, int n, int m) { int next[m]; getNext(pat, m, next); int i 0, j 0; while (i n j m) { if (j -1 || text[i] pat[j]) { i; j; } else { j next[j]; // 模式串右滑 } } return j m ? i - m : -1; }参数说明next 数组长度等于模式串长度j 回退到 next[j] 而不是 next[j-1]这是最容易写错的地方。KMP 的时间复杂度是 O(nm)比朴素匹配的 O(n*m) 快在「主串指针不回退」。3.3 二叉树三种遍历递归与非递归的转换套路二叉树遍历是树章节的基础递归写法几乎人人会但期末经常要求写非递归版本。三种遍历的递归模板高度统一区别只在访问根节点的时机// 中序遍历递归版 void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); // 左 visit(root); // 根 inorder(root-right); // 右 }非递归版本用栈模拟中序的写法是「一路向左压栈弹栈时访问再转向右子树」void inorderIter(TreeNode *root) { TreeNode *stack[100]; // 假设树不超过 100 节点 int top -1; TreeNode *curr root; while (curr ! NULL || top ! -1) { while (curr ! NULL) { // 一路向左 stack[top] curr; curr curr-left; } curr stack[top--]; // 弹栈 visit(curr); // 访问 curr curr-right; // 转向右子树 } }前序和后序的非递归只需调整访问时机和压栈顺序。后序稍麻烦常见做法是用两个栈或者记录上次访问节点。考试里如果只要求写一种非递归优先准备中序因为它的逻辑最清晰也最常考。3.4 排序算法对比冒泡、快排、归并、堆排的考场选择排序是期末必考选择题考复杂度稳定性代码题考快排和归并。先把对比表钉死算法平均时间最坏时间空间稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学、小数据快速排序O(n log n)O(n²)O(log n)不稳定通用最快归并排序O(n log n)O(n log n)O(n)稳定要求稳定、外排堆排序O(n log n)O(n log n)O(1)不稳定空间受限快排的核心是 partition代码如下// 快排划分返回基准最终位置 int partition(int *a, int low, int high) { int pivot a[low]; // 取第一个元素为基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; // 右边小的移到左边 while (low high a[low] pivot) low; a[high] a[low]; // 左边大的移到右边 } a[low] pivot; // 基准归位 return low; } void quickSort(int *a, int low, int high) { if (low high) { int p partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p 1, high); } }参数说明pivot 取第一个元素时必须先移动 high 指针再移动 low 指针顺序反了会出错。快排最坏情况出现在数组已经有序时退化成 O(n²)这也是为什么工程实现里常用随机基准或三数取中。归并排序的 merge 操作是重点两个有序子数组合并时用辅助数组暂存再拷回原数组空间换稳定。4. 复杂度分析O 和 Θ 什么时候用哪个别再混着写4.1 大 O、大 Θ、大 Ω 的区别与考场判断复杂度分析是选择题高频考点尤其是「什么时候用 O 什么时候用 Θ」这个问题。简单说大 O 表示上界大 Ω 表示下界大 Θ 表示紧确界。如果一个问题的最坏情况和最好情况同阶就可以用 Θ如果只关心最坏情况的上界用 O。比如快排平均时间是 Θ(n log n)最坏时间是 O(n²)这里用 O 是因为最坏情况只是一个上界估计实际可能不到。考试里如果题目问「该算法的时间复杂度」默认答最坏情况的大 O如果问「紧确界」才用 Θ。4.2 递归式求解主定理的三种情况怎么套递归算法的时间复杂度常用递归式表示比如归并排序是 T(n) 2T(n/2) O(n)。主定理Master Theorem是求解这类递归式的标准工具形式是 T(n) aT(n/b) f(n)比较 f(n) 和 n^(log_b a) 的大小情况一f(n) O(n^(log_b a - ε))则 T(n) Θ(n^(log_b a))情况二f(n) Θ(n^(log_b a))则 T(n) Θ(n^(log_b a) * log n)情况三f(n) Ω(n^(log_b a ε)) 且满足正则条件则 T(n) Θ(f(n))归并排序中 a2, b2, log_b a 1f(n) O(n) Θ(n^1)属于情况二所以 T(n) Θ(n log n)。二分查找中 a1, b2, log_b a 0f(n) O(1) Θ(n^0)也是情况二T(n) Θ(log n)。套公式时先算 log_b a再和 f(n) 的阶比较大部分期末题用这三种情况就够了。5. 避坑与排查期末复习里最容易翻车的 5 个地方5.1 指针操作链表代码写完不检查空指针现象手写链表插入或删除代码时运行报段错误或者考试时被扣分。原因没有判断头节点为空、没有判断待删除节点是否存在、没有处理删除尾节点的情况。解决写完链表代码后强制自己走一遍三种边界——空链表、单节点、操作头节点。特别是删除操作一定要先判断head NULL再判断是否删除的是头节点。5.2 KMP 的 next 数组教材版本不统一导致对不上答案现象自己算的 next 数组和答案不一样但匹配结果又是对的。原因不同教材对 next[0] 的约定不同有的用 -1有的用 0有的从 1 开始编号。解决考试时先看题目或教材用的是哪种约定西电常用 -1 版本。如果题目没说明在答题时标注你使用的约定避免因为版本差异被判错。5.3 排序稳定性把不稳定排序当成稳定用现象选择题问「下列哪个排序是稳定的」把快排或堆排选成稳定。原因只记了时间复杂度没记稳定性。解决记住稳定排序的口诀「冒泡、插入、归并、基数稳定」快排、选择、堆排、希尔不稳定。考试前把这张稳定性表默写一遍比考场上临时想靠谱得多。5.4 树的遍历递归和非递归搞混访问顺序现象写非递归中序时把访问时机写成了入栈时访问结果变成前序。原因没有理解「中序是弹栈时访问前序是入栈时访问」。解决记住一句话——前序在入栈前访问中序在弹栈后访问后序在左右子树都处理完后访问。写完后用一棵三节点的小树手动模拟一遍立刻能发现错误。5.5 复杂度分析把平均当最坏把最坏当平均现象题目问快排的时间复杂度答 O(n log n)但题目要的是最坏情况。原因没有看清题目问的是平均还是最坏。解决读题时圈出「平均」「最坏」「最好」这几个关键词。快排平均 O(n log n)、最坏 O(n²)归并平均和最坏都是 O(n log n)堆排平均和最坏都是 O(n log n)。这几个数字必须条件反射般准确。6. 考前一周怎么用这份知识点总结我的复盘习惯最后一周不要再从头翻 PDF 了效率极低。我的做法是拿一张白纸按「线性表、栈队列、串、树、图、查找、排序」七个模块每个模块默写三样东西核心操作的代码框架、关键复杂度、一个易错点。写不出来的地方标记出来只复习标记的部分。这个过程通常两小时能过完一轮比翻一天书有用得多。具体到这份「数据结构与算法期末知识点总结.pdf」我建议的用法是第一遍快速扫一遍确认覆盖范围第二遍只挑代码题高频章节链表、树遍历、快排归并精读第三遍合上资料手写默写。默写时用计时器模拟考场压力。我自己的血泪经验是平时写代码习惯开着编译器报错提示考场上手写时一个分号漏了都发现不了所以考前至少手写三遍完整代码不借助任何工具。验证复习效果的方法很简单找一套往年期末题或 408 真题限时做代码题部分。如果能在 20 分钟内写出链表反转、二叉树中序非递归、快排 partition 这三段代码且边界正确基本就稳了。如果写不出来回到对应章节重新默写不要心存侥幸。复习数据结构没有捷径但有针对性的重复可以省下大量时间。希望帮到你。本文还有配套的精品资源点击获取