数据结构考研复习指南：王卓课程笔记与刷题规划全攻略

最近在为考研复习数据结构花了不少时间在王卓老师的《数据结构与算法基础》课程上攒了厚厚一本笔记。这篇我把整个听课、记笔记、结合刷题的经验梳理出来覆盖知识体系拆解、笔记方法、复习轮次安排还有我踩过的坑希望能给正在学这门课或者准备408统考的朋友一些参考。这门课是青岛大学的王卓老师主讲的全称叫“数据结构与算法基础”在B站上免费公开几乎是考研人入门数据结构的首选。王卓老师讲课非常细致从基础概念一路深入到算法设计知识点讲得很完整特别适合第一次系统学习数据结构的人。我印象最深的是她讲栈和队列、树和图这些抽象结构的时候全程都是先给生活化的场景再上逻辑图和代码演示一步一步带你把思路理顺。相比很多课程直接抛定义、甩代码这门课的推导过程做得很充足对零基础的人来说十分友好。这篇笔记不光是知识点摘要还包含了我自己整理的易混点对比表、时间复杂度口诀、刷题模板希望能帮你少走弯路。1. 课程怎么看先搞清楚这门课能给你什么1.1 课程定位与适合人群王卓老师的课本质上是一套完整的本科教学课程不是专门为考研设计的冲刺班。这个定位决定了它的讲解节奏和内容覆盖方式它会把每一个知识点讲透但不会像考研强化课那样直接对着题型开练。所以如果你基础薄弱这门课是绝佳的“打地基”材料如果你已经有一定基础可以用二倍速过知识点重点听那些自己总是搞混的部分。我个人的建议是如果你是跨考或者本科没认真学数据结构第一轮复习一定不要跳过这门课。因为408统考里的数据结构部分考察方式虽然灵活但底层全部是这些基础知识的组合。直接去刷题会非常痛苦甚至连题目在问什么都反应不过来。我当时就是先刷了两周题发现线性表、树、图的基础概念来回出错回去老老实实从头听课效果反而更高效。1.2 听课时的正确打开方式听课不是把视频放完就算完更不是一边听一边抄板书。我的做法是课前先把对应章节的教材目录扫一眼知道今天要讲什么的框架然后听的时候只记结构性的东西和板书里没有的补充说明尽量别逐字抄PPT。王卓老师的课里有很多她自己画的状态图、指针变化图比如链表插入删除、树的遍历过程这些图比文字重要得多一定要自己动手跟着画一遍。还有一个关键点遇到老师口头提到的“这里容易考”“这个要对比记忆”这类提示停一下不是划重点就完事而是马上在笔记里补一个“为什么这里容易考”的备注。比如她讲循环队列时提到判空判满的条件我在笔记里写的是“判满为什么要牺牲一个存储单元因为如果不牺牲rear front 既代表空也代表满产生二义性”——这个备注后来复习时帮了大忙。1.3 怎么分配学习时间这门课的内容量大一天内全听完不现实也没有效果。我第一阶段是用了一个半月过完第一轮每天留2小时听课、1小时整理笔记和写课后习题。如果时间紧可以跳过视频里大段的代码逐行讲解只看数据结构定义和算法思路部分。但千万不要跳过图算法和排序那部分这两块是408的大题高发区。另外课程配套的课后习题一定要写。不是写选择题而是把算法设计题自己动手在纸上做一遍。王卓老师的课每一章后面都有算法设计习题这些题基本是考研算法题的原型比如链表反转、二叉树层序遍历、图的深度优先搜索框架。很多同学觉得听懂了一动手就卡壳就是因为没有经历过“从思路到代码”的完整过程。2. 知识体系拆解把课程内容模块化2.1 八个核心模块的复习重难点数据结构的知识点看上去又杂又多但其实拆开就八个模块绪论复杂度分析、线性表、栈和队列、串、树与二叉树、图、查找、排序。每个模块的重要程度差别很大。从408历年考试来看线性表、树、图、排序是绝对的重点栈和队列常出小题串和查找属于“看起来少、考起来狠”的模块KMP算法和哈希查找几乎每年都有涉及。我的笔记里专门给每个模块做了标记用星号标出高频考点用问号标出自己容易出错的地方。我做的第一个工作就是把这八个模块做成了一张脑图主分支是结构类型每个分支下面记住三件事——“定义是什么、存储方式有哪几种、典型操作有哪些”。比如线性表分支下就有顺序表和链表两种存储方式典型操作是插入、删除、查找。树的下面有二叉树、线索二叉树、哈夫曼树等典型操作是各种遍历。这个三问法对建立知识骨架非常有效。2.2 关键公式和时间复杂度整理数据结构这门课绕不开时间复杂度的计算。第一遍听课很多同学容易把各种结构的时间复杂度记成一锅粥。我建议把所有核心操作的时间复杂度整理成一张总表贴在笔记本扉页或者做成手机壁纸反复看。以下是我整理的简版后面刷题时反复用到结构查找插入删除额外说明顺序表O(1)按位置/ O(n)按值O(n)移动元素O(n)随机访问能力强单链表O(n)O(1)已知位置O(1)已知前驱插入点本身需遍历找到栈O(1)O(1)O(1)只能操作栈顶队列O(1)O(1)O(1)循环队列注意判满二叉搜索树O(logn)~O(n)O(logn)~O(n)O(logn)~O(n)退化成链时最差平衡二叉树O(logn)O(logn)O(logn)旋转操作要画图理解哈希表O(1) 平均O(1) 平均O(1) 平均冲突处理影响实际性能图邻接矩阵O(1) 判断边O(1) 插入边O(1) 删除边空间O(n²)图邻接表O(度)O(1)O(需查找稀疏图更划算这张表不需要死记硬背关键是理解“为什么”。比如顺序表按值查找为什么是O(n)因为是逐个比较哈希表为什么平均是O(1)因为直接通过哈希函数计算地址。2.3 必须画图才能理解的知识点数据结构的很多概念光看文字和代码是学不懂的必须动手画图。我踩过最大的坑就是二叉树删除节点和图的遍历看视频觉得看懂了合上书什么都不记得。我的方法是把每一种操作画成带序号的状态图。比如平衡二叉树的LL、RR、LR、RL四种旋转我每一类都画一棵“变形前”和“旋转后”的对比图并标注旋转的轴心。图的最短路径用Dijkstra算法时每一轮更新dist数组的过程都画一行标出当前选中的顶点和更新后的路径长度。这些图不要求画得多美观自己看得懂就行但一定得自己动手画。链表插入删除就更不用说了。我用不同颜色的笔分别画出前驱节点、当前节点、后继节点的指针变化每一步指针改动都用箭头标出来。画过三遍之后指针操作基本不会再错。3. 笔记怎么做从课堂笔记到复习资料3.1 笔记工具选择和理由我最后用的是Markdown为主、线下手写为辅的方式。听课的时候先用纸笔快速记草稿主要是画图和写临时想法晚上整理成电子笔记用Typora编辑再用Obsidian建立双链把相关知识点串起来。比如我把“图的深度优先搜索”和“二叉树的先序遍历”做了关联链接把“栈的递归应用”和“快速排序的递归实现”做了关联复习的时候可以顺着链接跳转。不推荐直接拿别人整理好的笔记来背。笔记的价值在于整理过程本身——你在整理的时候会重新审视知识点发现听课时候没注意的细节。我一开始也下载过别人分享的数据结构笔记看完觉得都懂一合上就想不起来。后来换成了自己整理的版本效果好很多。3.2 笔记里必备的六类内容我总结了一份合格的数据结构笔记应该包含六类内容第一是定义和术语比如栈的LIFO特性、二叉树的五种基本形态、图的有向无向区分这些都是做题的基本语言。第二是结构体定义和关键代码不是所有代码都要记只记那些能体现结构本质的代码比如链表节点定义、二叉树节点定义、邻接表定义。第三是操作思路的文字描述代码容易忘但“先找到待删节点的前驱再修改指针”这种话不容易忘。第四是手绘状态图指针变化图、递归展开图、遍历顺序图都算。第五是易混点对比表比如B树和B树的区别、最小生成树和最短路径的区别。第六是自己编的口诀和错题记录。3.3 我的四轮复习笔记法整个学习过程中我同一个知识点实际上记了四遍笔记每一轮的侧重点完全不同。第一轮是跟课笔记就是上面说的粗记目标是跟上老师的节奏把知识的骨架立起来。第二轮是章节整理笔记学完一章之后不看视频、不看教材凭记忆把这一章的核心内容默写出来再用红笔对照教材补缺。这个方法很残酷但效果奇好能立刻找出自己哪里没有真正记住。第三轮是刷题笔记把做题过程中遇到的经典错题、好题、模板题记录下来标注考点和“下次遇到应该怎么想”。第四轮是考前速记笔记每个章节只留一页纸写最核心的定义、口诀、复杂度表、算法模板用于考前几天的快速回顾。四轮下来一个知识点至少被主动回忆了四次。等到考前我基本已经不需要再翻教材了四轮笔记层层递进直接看最后一轮就能撑起整个知识框架。3.4 一个可以直接抄的笔记模板我用的章节笔记模板大概是这样的结构供你参考章节名称与核心问题这一章解决什么问题核心定义清单名词解释性质的知识点列表数据结构定义C语言结构体代码或伪代码操作要点插入、删除、查找等核心操作的文字描述易错点预警自己容易错、或者老师特意强调过的坑复杂度表本章所有操作的时间复杂度、空间复杂度算法模板可复用的代码框架如树的遍历框架、图的DFS框架自测题章末挑两三道代表性题目不写答案只写思路4. 刷题路线搭配课程笔记的三步走4.1 第一步章节课后题打底听完一章立刻做两件事一是做课程配套的课后选择题巩固基础知识二是从课后算法设计题里挑两道直接在白纸上写完整代码。这一步的核心目标是检测“是否真的理解了”不需要追求题量但每题都要能独立写出来。我印象最深的是学完线性表之后狂练链表反转相关的题。课后题从“反转整个链表”一路做到“反转链表前N个节点”再到“K个一组反转链表”每次都是先自己写写不出来就看答案、理解思路、隔两天再独立写一遍。到后来做算法大题时链表类题目基本上就是送分题。4.2 第二步按专题刷LeetCode基础打牢之后我按照专题刷LeetCode上的经典题目每类结构选10到20道有代表性的题不贪多。集中刷题的部分尽量不要略过的内容包括用栈实现队列、用队列实现栈、有效的括号、二叉树的前中后层序遍历、二叉树的最大深度和最小深度、验证二叉搜索树、岛屿数量DFS/BFS典型题、反转链表、环形链表、合并两个有序链表、排序链表。这些题可以看作是数据结构知识在算法题里的标准应用形式做熟这几类后面的难题才有基础。刷题的时候我坚持先口述思路再动手。比如做二叉树遍历题先问自己“这题是用递归还是迭代递归的终止条件是什么每层递归要返回什么”想清楚了再写代码。这个习惯让我养成了写题前先理逻辑的毛病有效降低了调试时间。4.3 第三步回扣408真题最后阶段要回到408真题和模拟题。这个阶段做的不是“会不会写代码”而是“在有限时间内能不能做对”。数据结构的真题分布很规律选择题偏基础大题偏综合经常会把多个知识点串在一道题里考。一个典型的综合题模式是给你一个二叉树/图的存储结构问你某个遍历的输出序列或者让你设计一个算法实现某个功能。这种题的关键在于看懂题目给的存储结构定义。408的算法题一般不会限制你用哪种语言但会在题目描述里用类似C语言的结构体定义给出数据组织方式刷题时必须习惯读这种“题目里带结构体定义”的方式。4.4 刷题中一定要记住的四个习惯第一个习惯是写题先写复杂度分析。每道题写完代码我在IDE上方或者纸上都会写一行“时间复杂度O(?)空间复杂度O(?)”。408算法题经常在题目最后问“你的算法时间复杂度和空间复杂度是多少”平时不练这个考场上很容易写错。特别要注意有时候题目会有附加条件比如“设计一个时间复杂度为O(n)的算法”这时候哪怕你能写出来O(n²)的解法也算不得分。第二个习惯是注意边界条件。链表为空、树只有一个节点、数组下标越界这些是数据结构题里最容易被坑的地方。我整理了一个边界条件自查清单每次写完代码逐条对照检查刚开始会觉得麻烦后面形成肌肉记忆之后就很快。第三个习惯是不要过分依赖IDE调试。408考试是纸质答题编译器不等于考试环境。我后期练习时规定自己简单题在纸上写代码、纸上演算只有遇到确实查不出的逻辑问题时才打开编译器。第四个习惯是定期重刷错题。我做错题集会记录日期和“错误原因”比如“对平衡二叉树旋转方向判断错误”“忘记考虑Dijkstra的已访问数组更新”每周固定一个晚上重新做一遍本周错题。数据结构的题做了第一次不叫会能做对第二次才算真的掌握了。5. 常见问题与排查技巧实录复习数据结构的过程中我遇到过很多典型问题这里把最有代表性的几个整理成一个速查表希望能帮你提前避开坑。问题现象原因分析解决办法循环队列判空判满总混淆没有理解牺牲一个存储单元的设定画一个循环数组图标出front和rear的移动方向记住“队空frontrear队满(rear1)%MaxSizefront”KMP算法的next数组算不对对“最长相等前后缀”理解不透先手动计算“abcab”这类短串的前后缀再套next推导流程。注意next[1]通常取0或-1取决于题目约定二叉树递归代码会写但不会分析递归过程抽象难懂用很小的例子3个节点手动展开递归调用栈画出每一层的返回结果分析完一个例子就掌握了套路图的深度优先和广度优先遍历顺序错没有区分辅助数据结构DFS用栈递归也可BFS用队列。做题时先标出访问起始点再按“未访问邻接点”逐个处理最小生成树和最短路径混淆两者名字相似但目标不同最小生成树是让所有顶点连通且总权值最小最短路径是两点之间路径长度最短。做一道Kruskal和一道Dijkstra题对比即可排序算法稳定性记不住全靠死记硬背用“一句话口诀”记忆选堆希快不稳定其余稳定选择、堆、希尔、快排不稳定。再理解每个不稳定原因哈希查找的查找长度算错冲突处理过程没数清楚画表模拟每个元素的插入过程ASL成功所有元素比较次数之和/元素个数。注意ASL失败的计算分母是哈希表长度算法大题不会设计代码积累不够背熟树的遍历模板、图的DFS/BFS模板、链表操作模板遇到新题先套模板再改动。平时积累多于10个题型模板5.1 时间复杂度的记忆窍门复杂度这块我单独拎出来讲因为它太重要了。不止选择题会直接考后面的大题设计也要求你说明“我这个算法的复杂度是多少”。我的记忆方法是把算法按“增长率”分成几个档次常数O(1) 对数O(logn) 线性O(n) 线性对数O(nlogn) 平方O(n²) 立方O(n³) 指数O(2ⁿ)。遇到一个循环嵌套先看有几层n级别的循环再看里面的操作是不是常数级。比如双重循环内是简单赋值复杂度就是O(n²)如果内层循环不是每一次都执行就要考虑最好、最坏和平均情况。很多排序算法为什么有“最好最坏”之分正是因为这个原因。5.2 图算法和树算法的常见卡壳点树和图是数据结构的半壁江山也是最容易卡壳的地方。树的部分卡壳点集中在线索二叉树的构造、哈夫曼树的WPL计算、平衡二叉树的旋转。图的部分卡壳点是拓扑排序的删除策略、Dijkstra算法与Floyd算法的适用场景区分、关键路径的ve和vl计算。我解决卡壳的办法异常朴素拿一个小例子上手算三遍。比如平衡二叉树旋转我用序列“13, 24, 37, 90, 53”建树先不旋转地插入一遍眼睁睁看着它变成链再按LL/LR/RR/RL规则旋转一遍对比两种结果就懂了。图的关键路径我自己画了5个活动、8条边的AOE网手推ve、vl、e、l四张表推完就再也忘不掉了。5.3 怎么摆脱“上课一听就会做题一写就错”这个问题很多人问过我。本质原因是“听懂”只是信息单向输入没有转化成你自己的“输出能力”。对策是进行大量“零参考输出”上课学完一章合上所有资料从零开始自己复现一遍核心代码。我学完二叉树遍历就是拿一张白纸自己写“先序递归遍历”的完整代码不偷看写不出来再翻笔记翻完隔两天再写一遍。写三遍之后这个代码基本就长在身上了。同样的道理适用于所有章节栈的括号匹配、队列的循环模拟、图的邻接表存储。说句实话这个过程很痛苦它相当于逼自己把“被动接受”变成“主动产出”。但数据结构和算法本来就是一门实践的课纸上谈兵最后一定翻车。我第一轮复习的时候就是因为偷懒只看不写到了模拟考阶段很多算法题连第一步结构体定义都写不出来吃了大亏才改过来。5.4 考前一周的高效回顾方式考前一周围绕“速记笔记”进行。我的速记笔记每章不超过一页只写五样东西核心定义、一句话操作思路、时间复杂度表、算法模板骨架、易错口诀。每天按“线性表→栈队列→串→树→图→查找→排序”的顺序把速记笔记快速过一遍然后挑一道这一章的经典算法题在白纸上手写一遍。一周下来相当于把所有高频算法题又亲手写了7遍。王卓老师在课上说过的“动手画、动手写”这个时候体现得淋漓尽致靠眼睛复习的同学在考场上容易手生靠手复习的同学下笔就顺。最后再分享一个小技巧是真题的错题复盘不要只记录“这道题答案选什么”要记录“这个考的是哪个章节的哪个知识点、我当时为什么错、下次怎么避免”。我见过太多人整理错题就是抄个答案一点用都没有。一份好的错题本应该是一份“自己给自己出的坑指南”每一次翻阅都能唤起你当时踩坑的记忆这样才算把一道错题的价值榨干了。数据结构与算法基础这门课内容多、理解难、考察灵活但它真的是计算机专业里最值得花功夫打底的科目之一。王卓老师的课把基础讲得很透再加上你自己动手实践、笔记整理和刷题巩固最后一定能建立起清晰的知识体系。