期末冲刺复习最怕的就是看着目录觉得都会合上书一动手全不会。数据结构这门课尤其如此它考的不只是记忆更是对“存储结构操作逻辑”的即时反应能力。这份冲刺指南上聚焦最核心的五大板块——线性表、栈队列、数组串、树与二叉树、并查集把常考的概念、高频题型、易错点和你可能漏掉的细节一次性捋清楚。我把每一个模块都按“核心原理 → 考点拆解 → 避坑提醒”的节奏来写尽量不绕弯子。如果你现在正处于考前一周到两周的状态这篇文章可以直接当复习地图用。1. 线性表顺序存储与链式存储的较量1.1 两种存储结构的本质差异线性表是数据结构里最基础也最“考验基本功”的一块。考试中关于线性表的题目本质只有一件事你清不清楚顺序表和链表的存储密度、访问方式、插入删除代价为什么不同。顺序表通常用数组实现的底层是连续内存空间这意味着它天生支持随机访问——给定下标O(1)就能定位元素。但它有两个硬伤第一插入和删除需要搬移大量元素平均时间复杂度O(n)第二容量是固定的扩容时要把整个数组复制到新空间这个操作的代价是O(n)。很多同学只记住了“顺序表插入删除慢”但没想清楚慢在“元素搬移”结果考到“在顺序表第i个位置插入元素需要移动几个结点”这类题时容易数错下标。链表则完全是另一套逻辑。它用指针把零散的内存结点串起来插入和删除只要修改指针指向O(1)完成前提是你已经知道目标结点的位置。但它失去了随机访问能力查找第i个元素必须从头开始遍历时间复杂度O(n)而且每个结点还要额外存一个指针域存储密度低于顺序表。考卷里常出现的对比维度我整理成一张表供你快速对照对比维度顺序表链表存储空间连续静态分配或动态扩容离散动态分配随机访问O(1)O(n)插入/删除O(n)需移动元素O(1)在已知位置前提下存储密度接近1小于1含指针开销适用场景查找多、长度稳定增删频繁、长度变化大1.2 高频题型的标准解法线性表这部分考试喜欢考几类题**第一类是“按值删除/按位删除”的实现题。**要求你写出删除顺序表中第一个值为x的元素或者删除链表中所有值为x的结点。后者更常考因为它要你同时维护两个指针一个pre指向当前结点的前驱一个p用于遍历。删除时先把pre的next指向p的next然后free掉p再让p重新指向pre的下一个结点。很多同学漏了“每次删完要更新pre的next”这个步骤代码跑起来就会断链。**第二类是“原地逆置”。**顺序表逆置的双指针法i指头、j指尾交换后i、j--很简单链表逆置则要用“头插法”的思想从原链表头开始逐个摘结点用头插法插入到新链表头部。这道题的核心不是写出来能跑而是理解它为什么能把顺序反转。**第三类是“有序表合并”。**两个递增有序链表合并成一个递增有序链表要求不额外申请结点空间。这类题用尾插法取两个链表中较小的那个结点接到结果链表的尾部剩下的结点直接整体拼接即可。考试评分标准里往往特别看重“是否释放了多余结点”和“是否处理了空表边界”。这部分我强烈建议你亲手写完一遍完整代码再进考场。只看不写是数据结构复习最大的陷阱因为你以为自己懂了但笔下逻辑根本连不起来的例子我每年都能见到一大批。2. 栈与队列受限线性结构的必考应用2.1 栈的考查核心和经典题目栈的特点是“后进先出”这个特性在括号匹配、表达式求值、递归模拟里都有体现。期末卷子上关于栈的题一般集中在以下角度。括号匹配考察的是栈的“先进后出”逻辑遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配则出栈不匹配或栈空则立即报错遍历结束后栈应该为空。这个算法本身的代码量不大但很多同学在“栈空时遇到右括号”这个分支上栽跟头。其实思路很清晰如果栈空说明前面没有对应的左括号直接返回不合法即可。中缀表达式转后缀表达式是栈的另一个核心考点。这个题目几乎必考算法流程要烂熟于心遇到操作数直接输出遇到左括号入栈遇到右括号依次弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符依次弹出栈中优先级大于等于当前运算符的栈顶运算符并输出然后把当前运算符入栈遍历结束后把栈中剩余运算符全部弹出。这个转换过程建议你在草稿纸上手动推演三个以上例子包括含括号和幂运算的混合表达式。熟能生巧推演多了以后你甚至不需要代码一眼就能看出中缀表达式的后缀形式长什么样。递归转非递归也经常出现考的其实是“手动维护栈”的能力。比如用栈模拟二叉树的前序遍历、中序遍历这实际上是函数递归调用栈的人工版本。你把“访问结点”和“保存右子树入栈”这两个动作拆开思考就能写出正确代码。很多同学写非递归中序时陷入死循环通常是因为出栈之后没有让指针立刻跳到右子树或者漏了“当前结点为空时出栈”的条件。2.2 队列的变种与边界处理队列是“先进先出”考试里问得最多的是循环队列。循环队列之所以出现是因为顺序队列反复入队出队时队尾指针会很快到达数组末尾但队头前面还空着大量位置。循环队列通过取模运算rear1% maxSize把数组首尾相接让空间能重复利用。循环队列有三组关键公式必须背到条件反射的程度队空条件front rear队满条件(rear 1) % maxSize front元素个数(rear - front maxSize) % maxSize注意最多能存maxSize-1个元素。这是牺牲一个存储单元来区分队空和队满的传统做法。如果你看到考题里说“重设一个标志位tag区分队空队满”那本质上就是允许存满maxSize个元素——入队时置tag1出队时置tag0判断队满就看tag是否为1且frontrear。队列的应用题常出“层次遍历二叉树”“模拟打印机任务调度”“用两个栈实现队列”等。其中“两个栈实现队列”的思路值得多想一步s1负责入队s2负责出队出队时如果s2为空就把s1的所有元素依次弹出并压入s2再从s2弹出队首。这个逻辑的复杂度值得分析一下每个元素最多入栈两次、出栈两次均摊时间复杂度是O(1)而不是每次都O(n)。3. 数组与串公式推导与模式匹配3.1 数组存储地址的计算套路数组这块的期末考试题本质上都是加减乘除。最常见的题型是已知某二维数组A[m][n]按行优先存储每个元素占k字节首元素地址是addr求A[i][j]的地址。按行优先的公式是地址(A[i][j]) 首地址 (i * n j) * k按列优先则是地址(A[i][j]) 首地址 (j * m i) * k看起来简单但很多人做题时看错数组下标范围。比如数组下标从0开始还是从1开始结果完全不同。如果下标从1开始那么A[i][j]前面有(i-1)n (j-1)个元素而不是in j。这个“下标基址偏移量”是失分重灾区请务必圈出题目里的下标起点。三维数组也不会太难无非是按页优先、行优先的复合。A[p][m][n]中求A[i][j][k]地址先算前面有几整页ipmn不是pm*n的总大小等一下页数乘以每页大小再加上页内的行偏移和列偏移。考试中出现三维数组主要是考你对“多维数组是按线性化后的地址存储”这个本质的理解。对称矩阵的压缩存储也算一个常驻考点。一个n阶对称矩阵只存下三角含对角线可以压成一维数组大小是n(n1)/2。下三角中A[i][j]在一维中的下标从0开始通常是i(i-1)/2 (j-1)如果下标从1开始从0开始就是i(i1)/2 j。同理上三角、对角矩阵也都可能被考到关键是画图辅助推导不要死记公式。3.2 字符串匹配与KMP算法的核心理解串这块朴素匹配暴力匹配人人都会就是两层循环逐个比对一失配就把模式串右移一位重新开始。可是你得能分析出最坏时间复杂度O(n*m)——主串长度n模式串长度m。KMP算法才是考试里的分水岭。它的核心不是匹配过程本身而是next数组的推导。很多人背了KMP的代码但看到求next数组的题需要手动推导时就懵了这是很要命的。next数组的含义要这样理解next[j]表示当模式串中第j个字符下标一般为0开始失配时模式串应该回退到哪个位置继续匹配。这个位置实际上是P[0..j-1]这个子串中最长的“相等前后缀”的长度。计算next数组时i是后缀指针j是前缀指针当P[i] P[j]时说明前缀和后缀继续匹配jnext[i] j当P[i] ! P[j]时j回退到next[j]直到j为0或找到匹配如果j已经是0则next[i] 0。我建议你用“ababc”这种短模式串手算一遍next数组然后对照代码验证。至少手推2到3个模式串考试中遇到“给定模式串求next数组”的题就能在规定时间内稳定输出正确结果。顺带提醒一下KMP改进版nextval数组也常出现在考研和部分高校期末考试中。nextval是在next基础上如果回退后的字符和当前字符相同就继续回退从而避免无意义的重复比较。如果考试没明确要求把next数组求对就足够拿分但如果你学有余力nextval的推导逻辑也最好掌握。4. 树与二叉树性质、遍历与还原4.1 常考性质总结与计算题二叉树是数据结构期末考试里占分最多的一块。它的性质很多但不需要死背任何一条抓住两个基本点就能推导出全部第i层最多有2^(i-1)个结点高度为h的二叉树最多有2^h - 1个结点最少有h个结点退化链状n0 n2 1叶子结点数等于度为2的结点数加1。n0 n2 1这个关系是高频中的高频而且经常结合完全二叉树出题。解法逻辑是完全二叉树中度为1的结点数要么是0要么是1设n2 x则n0 x1总点数n n0 n1 n2 2x1n1因为n1只有0或1两种取值所以n为奇数是n10n为偶数是n11。这类题值得你在草稿纸上推导一遍不要只记结论。树的遍历也常被挖空考察前序根左右、中序左根右、后序左右根、层次自上而下、从左到右。中序遍历是构建二叉树的关键原因在于它能把左右子树天然分开单独一个遍历序列无法唯一确定二叉树但“前序中序”或“后序中序”就能唯一确定。4.2 由遍历序列构造二叉树的实操方法考试中经常出现已知前序和中序序列要求画出二叉树。标准解法是分治每一步都做两件事前序中的第一个元素是根在中序里找到这个根的位置它左边的所有元素属于左子树右边的所有元素属于右子树根据左子树和右子树的长度回到前序序列中分割出对应的左右子树部分递归重复。举个例子。前序ABDEC中序DBEAC。前序的第一个是A所以根是A中序里A的位置在索引3从0开始左边是DBE右边是C。于是左子树由前序里从第1个位置开始、长度为3的元素构成即BDE右子树是C。然后对左子树递归B是根中序DBE中B在索引1左边D右边E于是一棵完整的二叉树就画出来了。你一定要亲手在这个例子上推两遍感受“前序分割子树序列”和“中序分割左右子树”的对应关系这是本科期末必考的手工题型。线索二叉树偶尔也会考小题。它是在普通二叉树的结点上加上ltag和rtag两个标志位值为0表示左右孩子指向真实子结点值为1表示指向前驱或后继线索。中序线索二叉树的后继很容易判断如果rtag为1右指针就是后继如果rtag为0则右子树中最左下的结点就是后继。这个点在选择题、填空题里出现频率不低。哈夫曼树也常出现在期末卷子上。构造过程是不断地从集合中取出两个权值最小的结点合并后放回反复直到只剩一个根结点。这里容易出错的地方有两个一个是合并顺序出错另一个是带权路径长度WPL的计算。WPL就是每个叶子结点的权值乘以它到根结点的路径长度之和。我建议你构造完哈夫曼树后立刻自己算一遍WPL并检查是不是所有叶子都在最底层或者适当位置——哈夫曼树没有度为1的结点。5. 并查集原理、实现与优化5.1 并查集的核心思想与基本实现很多同学把并查集当作某个难度较高的小众考点实际上它是数据结构课程里少有的“用数组就能实现的高效抽象结构”考试可以考到代码填空、手动模拟也可能出应用题。它的核心就两个字集合。它把多个元素划分成若干个不相交的集合每个集合选出一个代表元素称为根或代表元然后提供两种操作Find(x)查找x所属集合的代表元素Union(x, y)把x和y所在的集合合并。最简单的实现是双亲表示法的一个数组parent[]parent[i]表示结点i的父结点如果parent[i] i说明i是它所在树的根。Find的逻辑就是从i出发不断向上走直到parent[i] i。Union的逻辑更简单找到x和y的根rx、ry如果不同把parent[rx] ry或者parent[ry] rx让一棵树成为另一棵的子树。考试里最常见的并查集手动模拟题就是给出一系列Union操作序列让你画出最终的树形结构然后回答某个元素的根是谁。这种题只需要慢慢画双亲关系不会出错。5.2 路径压缩与按秩合并的优化代价朴素并查集如果不断合并树可能退化成一条链Find的复杂度退化为O(n)。所以考试很可能考按秩合并和路径压缩这两种优化策略。按秩合并的思路是每个根结点记录一个“秩”通常是树的高度上界或者子树大小合并时让秩较小的树挂到秩较大的树下面避免树长高。这样可以保证树高是O(log n)级别的。路径压缩的思路更巧妙在Find(x)的过程中顺手把路径上经过的所有结点直接挂到根结点下面以后再次查找这些结点就只需要O(1)。注意路径压缩只改动树的结构不改动秩的定义因此即使秩不再精确等于树高依然可以作为合并的启发式信息。这两种优化如果同时使用并查集的单次操作时间复杂度是反阿克曼函数级别近似看作常数。期末考试如果让你分析复杂度你答“近似O(1)”基本没有问题。并查集的应用题常见于判断无向图的连通分量个数、Kruskal最小生成树算法中判断是否形成回路、计算社交网络中的朋友圈个数。Kruskal那题尤其典型——按边权从小到大选边加入前先Find两个端点如果根相同说明会形成环跳过否则Union并计数。这个应用里并查集的“查环”角色是最高频的考查场景。我这里建议你手动模拟一个5个顶点、6条边的图跑一遍Kruskal全过程把并查集每一步的状态都画出来比盲目看代码管用得多。6. 冲刺阶段的时间分配与避坑清单6.1 考点优先级排序如果你只剩一周请把复习时间集中在最容易通过短期强化拿分的部分二叉树遍历与还原手工推导、哈夫曼树构造与WPL计算、KMP的next数组手工计算是性价比最高的三项只要推演过几遍考场上基本不失分。循环队列的公式、线性表的代码填空、数组地址计算也是高频题型属于“公式细心”的硬分数。并查集和栈的应用后缀表达式、括号匹配理解起来有门槛但一旦掌握很难出错。不建议在这个阶段去啃所有排序算法的完整代码推导更不建议死背散列表的冲突处理实现细节。先把高频、稳定的题保住再有余力才去碰更边缘的内容。6.2 最容易丢分的4个细节下标记作从1开始还是从0开始。数组地址计算、二叉树顺序存储中孩子下标的公式都要先看题目是否说明了“下标从1开始”。这一点在全卷多处出现有同学一路顺算结果全都偏了一位。KMP匹配过程没在草稿纸上推演。我强烈建议你在考前最后一个晚上亲手手算一个模式串的next数组并在主串上完整走一遍KMP匹配过程确保自己理解“失配后模式串如何回退”而不只是记忆代码。链表操作的边界条件。空表合并、单结点链表逆置、删除最后一个结点这些边缘场景极容易在实现题里写出越界访问。复习时逐个场景过一遍确认指针为NULL时不会访问非法内存。哈夫曼树的合并次序不严谨。每次必须取当前权值最小的两个结点很多同学凭直觉取“看起来比较小”的导致树的结构和WPL完全不对。建议用优先队列的思路按权值从小到大排列再合并。6.3 考前自测清单请你在正式走进考场前对着下面这份清单自查一遍哪一项不熟练就先补哪一项能白手写出顺序表按值删除和链表按值删除的完整函数能画出一个中缀表达式转后缀的完整过程包括括号和运算符优先级能手算任意模式串的next数组能根据前序中序序列还原一棵二叉树能计算完全二叉树中结点数为偶数时的n0、n1、n2能用并查集模拟Kruskal选边过程能写清楚循环队列队满、队空的条件和元素个数公式。这份清单覆盖了本次指南涉及的所有核心内容。考前不建议再大量刷题把这份清单上的每一项快速过一遍比刷十套卷子都更有针对性和安全感。
数据结构期末冲刺：五大核心模块考点与易错点全解析
期末冲刺复习最怕的就是看着目录觉得都会合上书一动手全不会。数据结构这门课尤其如此它考的不只是记忆更是对“存储结构操作逻辑”的即时反应能力。这份冲刺指南上聚焦最核心的五大板块——线性表、栈队列、数组串、树与二叉树、并查集把常考的概念、高频题型、易错点和你可能漏掉的细节一次性捋清楚。我把每一个模块都按“核心原理 → 考点拆解 → 避坑提醒”的节奏来写尽量不绕弯子。如果你现在正处于考前一周到两周的状态这篇文章可以直接当复习地图用。1. 线性表顺序存储与链式存储的较量1.1 两种存储结构的本质差异线性表是数据结构里最基础也最“考验基本功”的一块。考试中关于线性表的题目本质只有一件事你清不清楚顺序表和链表的存储密度、访问方式、插入删除代价为什么不同。顺序表通常用数组实现的底层是连续内存空间这意味着它天生支持随机访问——给定下标O(1)就能定位元素。但它有两个硬伤第一插入和删除需要搬移大量元素平均时间复杂度O(n)第二容量是固定的扩容时要把整个数组复制到新空间这个操作的代价是O(n)。很多同学只记住了“顺序表插入删除慢”但没想清楚慢在“元素搬移”结果考到“在顺序表第i个位置插入元素需要移动几个结点”这类题时容易数错下标。链表则完全是另一套逻辑。它用指针把零散的内存结点串起来插入和删除只要修改指针指向O(1)完成前提是你已经知道目标结点的位置。但它失去了随机访问能力查找第i个元素必须从头开始遍历时间复杂度O(n)而且每个结点还要额外存一个指针域存储密度低于顺序表。考卷里常出现的对比维度我整理成一张表供你快速对照对比维度顺序表链表存储空间连续静态分配或动态扩容离散动态分配随机访问O(1)O(n)插入/删除O(n)需移动元素O(1)在已知位置前提下存储密度接近1小于1含指针开销适用场景查找多、长度稳定增删频繁、长度变化大1.2 高频题型的标准解法线性表这部分考试喜欢考几类题**第一类是“按值删除/按位删除”的实现题。**要求你写出删除顺序表中第一个值为x的元素或者删除链表中所有值为x的结点。后者更常考因为它要你同时维护两个指针一个pre指向当前结点的前驱一个p用于遍历。删除时先把pre的next指向p的next然后free掉p再让p重新指向pre的下一个结点。很多同学漏了“每次删完要更新pre的next”这个步骤代码跑起来就会断链。**第二类是“原地逆置”。**顺序表逆置的双指针法i指头、j指尾交换后i、j--很简单链表逆置则要用“头插法”的思想从原链表头开始逐个摘结点用头插法插入到新链表头部。这道题的核心不是写出来能跑而是理解它为什么能把顺序反转。**第三类是“有序表合并”。**两个递增有序链表合并成一个递增有序链表要求不额外申请结点空间。这类题用尾插法取两个链表中较小的那个结点接到结果链表的尾部剩下的结点直接整体拼接即可。考试评分标准里往往特别看重“是否释放了多余结点”和“是否处理了空表边界”。这部分我强烈建议你亲手写完一遍完整代码再进考场。只看不写是数据结构复习最大的陷阱因为你以为自己懂了但笔下逻辑根本连不起来的例子我每年都能见到一大批。2. 栈与队列受限线性结构的必考应用2.1 栈的考查核心和经典题目栈的特点是“后进先出”这个特性在括号匹配、表达式求值、递归模拟里都有体现。期末卷子上关于栈的题一般集中在以下角度。括号匹配考察的是栈的“先进后出”逻辑遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配则出栈不匹配或栈空则立即报错遍历结束后栈应该为空。这个算法本身的代码量不大但很多同学在“栈空时遇到右括号”这个分支上栽跟头。其实思路很清晰如果栈空说明前面没有对应的左括号直接返回不合法即可。中缀表达式转后缀表达式是栈的另一个核心考点。这个题目几乎必考算法流程要烂熟于心遇到操作数直接输出遇到左括号入栈遇到右括号依次弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符依次弹出栈中优先级大于等于当前运算符的栈顶运算符并输出然后把当前运算符入栈遍历结束后把栈中剩余运算符全部弹出。这个转换过程建议你在草稿纸上手动推演三个以上例子包括含括号和幂运算的混合表达式。熟能生巧推演多了以后你甚至不需要代码一眼就能看出中缀表达式的后缀形式长什么样。递归转非递归也经常出现考的其实是“手动维护栈”的能力。比如用栈模拟二叉树的前序遍历、中序遍历这实际上是函数递归调用栈的人工版本。你把“访问结点”和“保存右子树入栈”这两个动作拆开思考就能写出正确代码。很多同学写非递归中序时陷入死循环通常是因为出栈之后没有让指针立刻跳到右子树或者漏了“当前结点为空时出栈”的条件。2.2 队列的变种与边界处理队列是“先进先出”考试里问得最多的是循环队列。循环队列之所以出现是因为顺序队列反复入队出队时队尾指针会很快到达数组末尾但队头前面还空着大量位置。循环队列通过取模运算rear1% maxSize把数组首尾相接让空间能重复利用。循环队列有三组关键公式必须背到条件反射的程度队空条件front rear队满条件(rear 1) % maxSize front元素个数(rear - front maxSize) % maxSize注意最多能存maxSize-1个元素。这是牺牲一个存储单元来区分队空和队满的传统做法。如果你看到考题里说“重设一个标志位tag区分队空队满”那本质上就是允许存满maxSize个元素——入队时置tag1出队时置tag0判断队满就看tag是否为1且frontrear。队列的应用题常出“层次遍历二叉树”“模拟打印机任务调度”“用两个栈实现队列”等。其中“两个栈实现队列”的思路值得多想一步s1负责入队s2负责出队出队时如果s2为空就把s1的所有元素依次弹出并压入s2再从s2弹出队首。这个逻辑的复杂度值得分析一下每个元素最多入栈两次、出栈两次均摊时间复杂度是O(1)而不是每次都O(n)。3. 数组与串公式推导与模式匹配3.1 数组存储地址的计算套路数组这块的期末考试题本质上都是加减乘除。最常见的题型是已知某二维数组A[m][n]按行优先存储每个元素占k字节首元素地址是addr求A[i][j]的地址。按行优先的公式是地址(A[i][j]) 首地址 (i * n j) * k按列优先则是地址(A[i][j]) 首地址 (j * m i) * k看起来简单但很多人做题时看错数组下标范围。比如数组下标从0开始还是从1开始结果完全不同。如果下标从1开始那么A[i][j]前面有(i-1)n (j-1)个元素而不是in j。这个“下标基址偏移量”是失分重灾区请务必圈出题目里的下标起点。三维数组也不会太难无非是按页优先、行优先的复合。A[p][m][n]中求A[i][j][k]地址先算前面有几整页ipmn不是pm*n的总大小等一下页数乘以每页大小再加上页内的行偏移和列偏移。考试中出现三维数组主要是考你对“多维数组是按线性化后的地址存储”这个本质的理解。对称矩阵的压缩存储也算一个常驻考点。一个n阶对称矩阵只存下三角含对角线可以压成一维数组大小是n(n1)/2。下三角中A[i][j]在一维中的下标从0开始通常是i(i-1)/2 (j-1)如果下标从1开始从0开始就是i(i1)/2 j。同理上三角、对角矩阵也都可能被考到关键是画图辅助推导不要死记公式。3.2 字符串匹配与KMP算法的核心理解串这块朴素匹配暴力匹配人人都会就是两层循环逐个比对一失配就把模式串右移一位重新开始。可是你得能分析出最坏时间复杂度O(n*m)——主串长度n模式串长度m。KMP算法才是考试里的分水岭。它的核心不是匹配过程本身而是next数组的推导。很多人背了KMP的代码但看到求next数组的题需要手动推导时就懵了这是很要命的。next数组的含义要这样理解next[j]表示当模式串中第j个字符下标一般为0开始失配时模式串应该回退到哪个位置继续匹配。这个位置实际上是P[0..j-1]这个子串中最长的“相等前后缀”的长度。计算next数组时i是后缀指针j是前缀指针当P[i] P[j]时说明前缀和后缀继续匹配jnext[i] j当P[i] ! P[j]时j回退到next[j]直到j为0或找到匹配如果j已经是0则next[i] 0。我建议你用“ababc”这种短模式串手算一遍next数组然后对照代码验证。至少手推2到3个模式串考试中遇到“给定模式串求next数组”的题就能在规定时间内稳定输出正确结果。顺带提醒一下KMP改进版nextval数组也常出现在考研和部分高校期末考试中。nextval是在next基础上如果回退后的字符和当前字符相同就继续回退从而避免无意义的重复比较。如果考试没明确要求把next数组求对就足够拿分但如果你学有余力nextval的推导逻辑也最好掌握。4. 树与二叉树性质、遍历与还原4.1 常考性质总结与计算题二叉树是数据结构期末考试里占分最多的一块。它的性质很多但不需要死背任何一条抓住两个基本点就能推导出全部第i层最多有2^(i-1)个结点高度为h的二叉树最多有2^h - 1个结点最少有h个结点退化链状n0 n2 1叶子结点数等于度为2的结点数加1。n0 n2 1这个关系是高频中的高频而且经常结合完全二叉树出题。解法逻辑是完全二叉树中度为1的结点数要么是0要么是1设n2 x则n0 x1总点数n n0 n1 n2 2x1n1因为n1只有0或1两种取值所以n为奇数是n10n为偶数是n11。这类题值得你在草稿纸上推导一遍不要只记结论。树的遍历也常被挖空考察前序根左右、中序左根右、后序左右根、层次自上而下、从左到右。中序遍历是构建二叉树的关键原因在于它能把左右子树天然分开单独一个遍历序列无法唯一确定二叉树但“前序中序”或“后序中序”就能唯一确定。4.2 由遍历序列构造二叉树的实操方法考试中经常出现已知前序和中序序列要求画出二叉树。标准解法是分治每一步都做两件事前序中的第一个元素是根在中序里找到这个根的位置它左边的所有元素属于左子树右边的所有元素属于右子树根据左子树和右子树的长度回到前序序列中分割出对应的左右子树部分递归重复。举个例子。前序ABDEC中序DBEAC。前序的第一个是A所以根是A中序里A的位置在索引3从0开始左边是DBE右边是C。于是左子树由前序里从第1个位置开始、长度为3的元素构成即BDE右子树是C。然后对左子树递归B是根中序DBE中B在索引1左边D右边E于是一棵完整的二叉树就画出来了。你一定要亲手在这个例子上推两遍感受“前序分割子树序列”和“中序分割左右子树”的对应关系这是本科期末必考的手工题型。线索二叉树偶尔也会考小题。它是在普通二叉树的结点上加上ltag和rtag两个标志位值为0表示左右孩子指向真实子结点值为1表示指向前驱或后继线索。中序线索二叉树的后继很容易判断如果rtag为1右指针就是后继如果rtag为0则右子树中最左下的结点就是后继。这个点在选择题、填空题里出现频率不低。哈夫曼树也常出现在期末卷子上。构造过程是不断地从集合中取出两个权值最小的结点合并后放回反复直到只剩一个根结点。这里容易出错的地方有两个一个是合并顺序出错另一个是带权路径长度WPL的计算。WPL就是每个叶子结点的权值乘以它到根结点的路径长度之和。我建议你构造完哈夫曼树后立刻自己算一遍WPL并检查是不是所有叶子都在最底层或者适当位置——哈夫曼树没有度为1的结点。5. 并查集原理、实现与优化5.1 并查集的核心思想与基本实现很多同学把并查集当作某个难度较高的小众考点实际上它是数据结构课程里少有的“用数组就能实现的高效抽象结构”考试可以考到代码填空、手动模拟也可能出应用题。它的核心就两个字集合。它把多个元素划分成若干个不相交的集合每个集合选出一个代表元素称为根或代表元然后提供两种操作Find(x)查找x所属集合的代表元素Union(x, y)把x和y所在的集合合并。最简单的实现是双亲表示法的一个数组parent[]parent[i]表示结点i的父结点如果parent[i] i说明i是它所在树的根。Find的逻辑就是从i出发不断向上走直到parent[i] i。Union的逻辑更简单找到x和y的根rx、ry如果不同把parent[rx] ry或者parent[ry] rx让一棵树成为另一棵的子树。考试里最常见的并查集手动模拟题就是给出一系列Union操作序列让你画出最终的树形结构然后回答某个元素的根是谁。这种题只需要慢慢画双亲关系不会出错。5.2 路径压缩与按秩合并的优化代价朴素并查集如果不断合并树可能退化成一条链Find的复杂度退化为O(n)。所以考试很可能考按秩合并和路径压缩这两种优化策略。按秩合并的思路是每个根结点记录一个“秩”通常是树的高度上界或者子树大小合并时让秩较小的树挂到秩较大的树下面避免树长高。这样可以保证树高是O(log n)级别的。路径压缩的思路更巧妙在Find(x)的过程中顺手把路径上经过的所有结点直接挂到根结点下面以后再次查找这些结点就只需要O(1)。注意路径压缩只改动树的结构不改动秩的定义因此即使秩不再精确等于树高依然可以作为合并的启发式信息。这两种优化如果同时使用并查集的单次操作时间复杂度是反阿克曼函数级别近似看作常数。期末考试如果让你分析复杂度你答“近似O(1)”基本没有问题。并查集的应用题常见于判断无向图的连通分量个数、Kruskal最小生成树算法中判断是否形成回路、计算社交网络中的朋友圈个数。Kruskal那题尤其典型——按边权从小到大选边加入前先Find两个端点如果根相同说明会形成环跳过否则Union并计数。这个应用里并查集的“查环”角色是最高频的考查场景。我这里建议你手动模拟一个5个顶点、6条边的图跑一遍Kruskal全过程把并查集每一步的状态都画出来比盲目看代码管用得多。6. 冲刺阶段的时间分配与避坑清单6.1 考点优先级排序如果你只剩一周请把复习时间集中在最容易通过短期强化拿分的部分二叉树遍历与还原手工推导、哈夫曼树构造与WPL计算、KMP的next数组手工计算是性价比最高的三项只要推演过几遍考场上基本不失分。循环队列的公式、线性表的代码填空、数组地址计算也是高频题型属于“公式细心”的硬分数。并查集和栈的应用后缀表达式、括号匹配理解起来有门槛但一旦掌握很难出错。不建议在这个阶段去啃所有排序算法的完整代码推导更不建议死背散列表的冲突处理实现细节。先把高频、稳定的题保住再有余力才去碰更边缘的内容。6.2 最容易丢分的4个细节下标记作从1开始还是从0开始。数组地址计算、二叉树顺序存储中孩子下标的公式都要先看题目是否说明了“下标从1开始”。这一点在全卷多处出现有同学一路顺算结果全都偏了一位。KMP匹配过程没在草稿纸上推演。我强烈建议你在考前最后一个晚上亲手手算一个模式串的next数组并在主串上完整走一遍KMP匹配过程确保自己理解“失配后模式串如何回退”而不只是记忆代码。链表操作的边界条件。空表合并、单结点链表逆置、删除最后一个结点这些边缘场景极容易在实现题里写出越界访问。复习时逐个场景过一遍确认指针为NULL时不会访问非法内存。哈夫曼树的合并次序不严谨。每次必须取当前权值最小的两个结点很多同学凭直觉取“看起来比较小”的导致树的结构和WPL完全不对。建议用优先队列的思路按权值从小到大排列再合并。6.3 考前自测清单请你在正式走进考场前对着下面这份清单自查一遍哪一项不熟练就先补哪一项能白手写出顺序表按值删除和链表按值删除的完整函数能画出一个中缀表达式转后缀的完整过程包括括号和运算符优先级能手算任意模式串的next数组能根据前序中序序列还原一棵二叉树能计算完全二叉树中结点数为偶数时的n0、n1、n2能用并查集模拟Kruskal选边过程能写清楚循环队列队满、队空的条件和元素个数公式。这份清单覆盖了本次指南涉及的所有核心内容。考前不建议再大量刷题把这份清单上的每一项快速过一遍比刷十套卷子都更有针对性和安全感。
