期末最后一场考完楼道里全是讨论题目的声音“第二道算法题你用的递归还是非递归”“哈希那题平均查找长度算出来多少”哈尔滨工业大学2021年秋季学期数据结构期末试题在考后讨论里热度一直没降下去。不是因为题目偏而是它把“基础”二字考出了层次感——既有让人闭眼拿分的送分题也有让一半人卡在中途的代码题还有一道压轴设计题直接拉开区分度。这篇文章我打算从一个参加过这套卷复习、也带过不少学弟学妹做考前冲刺的视角把这套试卷的命题逻辑、核心考点、代表性题目解法以及背后折射出来的数据结构学习主线完整梳理一遍。内容不局限于“对答案”更重要的是讲清楚每一类题为什么这么出、应该用什么思路去拆。无论你是正在准备期末、备战考研还是单纯想检验一下自己的数据结构底子这份复盘都有参考价值。1. 试卷整体画像先看分值分布再看命题风格1.1 题型结构与分值占比从考后大家回忆拼出来的图景看这套试卷延续了哈工大近几年的稳定架构满分100分题型分为四大块题型题量分值考察侧重单项选择题10题20分基础概念、性质判定、时间复杂度填空题8题16分结论性知识、公式推理、存储结构细节简答与应用题4题32分树、图、查找、排序的综合计算与手工推演算法设计与分析2题32分链表/树相关代码编写策略分析和复杂度证明这个分值分配非常典型基础题选择填空占36分这部分考的是“背下来并能正确理解”的知识应用题占32分考的是“动笔算得出来”的功力算法设计占32分考的是“现场写得出代码且能分析”的能力。三个层次之间层层递进区分度也主要靠最后一大题拉开。1.2 难度梯度和命题倾向如果给这套卷子的难度画一条曲线大概是开篇选择题平缓起步中间应用题稳步爬坡最后算法题直接上强度。选择题第1到第5题基本是概念等价判断比如时间复杂度的量级比较、栈和队列的进出规则、二叉树性质公式这些题目不拐弯属于“复习过就能拿分”的类型。从第6题开始难度上来了。我印象比较深的一道选择题是关于循环队列的给出队头指针front和队尾指针rear的初始值以及入队出队若干次后的状态要求判断当前队列长度。这类题很容易在“牺牲一个存储单元判满”和“增设size域判满”两种方案之间绕晕本质考察的是你对两种实现方式差异的理解深度而不只是背公式。应用题部分图的最短路径和最小生成树是重头戏。考后很多人讨论Dijkstra算法的手算过程中某个中间节点的dist值更新顺序以及Prim算法从不同起点出发得到的结果是否一致。这类题目的杀伤力在于你理解了算法框架但不熟悉松弛操作的每一步很容易在中途写错一个数字后面全盘错。算法设计题暴露的问题最集中。第一题链表相关多数人能写但代码不够简洁第二题树相关压轴出现考后普遍反馈“有思路但不确定自己的实现是否符合最优复杂度要求”。这个下一章展开讲。1.3 与教材和课纲的对应关系哈工大本科阶段数据结构课程使用的教材是严蔚敏《数据结构C语言版》配套习题集在复习阶段使用率极高。这套期末试卷的命题范围严格对齐课纲没有超纲内容但部分题目难度高于教材课后习题更接近习题集里标记为“综合”或“提高”的题目。这意味着一个很关键的备考信息单纯刷课后题并不足以应对期末。你得学会把教材里分散在不同章节的知识串起来。比如试卷中有一道关于二叉树和栈结合的简答题让你用非递归方式实现中序遍历并写出过程中栈的状态变化。这题在教材上只出现在算法源码里但考试直接以“过程手写”的形式出现说明老师默认你对非递归遍历的栈操作非常熟练——这正是只看不练的人最容易翻车的地方。2. 核心考点逐项拆解六个板块一个不落2.1 线性表与链表变化最多的基础题线性表部分在试卷里占比不重选择题和填空题各占一道但算法设计题第一题基本锁定链表。这很好理解链表作为最基础又最具操作感的数据结构是考察“指针操作基本功”的最佳载体。相关热搜词里有一个很有意思数据结构链表。这说明大家普遍觉得链表知识零散、指针绕来绕去容易晕。但期末考并不像面试那样要求你在十分钟内手写一个复杂的链表操作而是更看重你对链表基本操作的掌握和对边界条件的敏感度。这套卷子里链表相关的题目从考后反馈拼出来看大致有这几类给定单链表头指针删除值为x的所有节点要求时间O(n)、空间O(1)判断一个单链表是否有环并给出证明将两个递增有序链表合并为一个递减有序链表这类题的共同特点是算法本身不难但代码的细节决定成败。以删除值为x的所有节点为例很多人会忘记处理头节点就是x的情况。正确做法是引入一个虚拟头节点dummy让dummy-next指向原链表头这样对原头节点的操作就统一成了对普通节点的操作代码逻辑立刻清晰。实际上我在辅导过程中发现链表题的代码风格往往能看出一个人是不是真的理解指针。写得干净的人一定会优先想到虚拟头节点写得乱的人基本上是在用if硬分类讨论。期末复习时如果能把“虚拟头节点”“双指针”“递归转迭代”这三板斧练熟链表题基本可以做到秒写。2.2 栈与队列概念少计算多栈和队列在这套卷子里的表现是不鸣则已一鸣惊人。选择题有一道关于栈的经典坑题元素a、b、c、d、e依次入栈不可能得到的出栈序列是什么这类题在期末题库里反复出现但2021年这道题加了一个变化出栈过程中允许入栈操作暂停本质考的仍然是卡特兰数约束下的合法性判断。队列部分的考察集中在循环队列。填空题让你写出在“牺牲一个存储单元”的方案下队列满的判断条件(rear 1) % MaxSize front以及队列长度公式(rear - front MaxSize) % MaxSize。很多人只背了公式遇到队列指针增减的变体题就开始乱套公式其实追根到底这两个公式都是从“队头指针指向队头元素队尾指针指向队尾元素的下一个位置”这个约定推导出来的。理解了约定的背后逻辑任何变体题都迎刃而解。应用题里有一道表达式求值给出中缀表达式A B * (C - D) / E要求写出转换为后缀表达式的过程并说明栈的变化。这道题非常经典在考研408和各大厂笔试里都是常客。解法的关键点是操作符的入栈和出栈时机取决于当前操作符与栈顶操作符的优先级比较。当当前操作符优先级低于等于栈顶时栈顶出栈并输出。括号的处理则是左括号直接入栈遇到右括号则依次弹出直到左括号。这类题一旦你把规则总结成“优先级比栈顶低就弹栈括号特殊处理运算数直接输出”那无论表达式怎么变你都能手算出来完全不需要临时推理。2.3 树与二叉树试卷的分水岭树是数据结构课程的核心也是这套期末试卷的分水岭。选择、填空、简答、算法设计全覆盖分值占比接近30%是所有章节里最高的。这跟热词里数据结构树的高热度完全吻合——树学不好数据结构等于没学。选择题里有几道考察二叉树基本性质的题目度为2的节点数等于叶子节点数减1n个节点的完全二叉树深度为floor(log2n)1二叉树的第i层最多有2^(i-1)个节点。这些公式简单但考试不会直接让你默写而是包装成应用场景。比如已知一棵完全二叉树有1001个节点求叶子节点个数。这种题需要你综合运用完全二叉树的性质和满二叉树的结构特点来推导光靠背公式是拿不稳的。简答题里最经典的一道已知一棵二叉树的中序序列和后序序列要求画出这棵二叉树并写出先序序列。这个考法在哈工大期末几乎是必考题因为它综合考察了三种遍历顺序之间的关系。解法思路是后序序列的最后一个节点是根节点找到根节点在中序序列中的位置左边是左子树、右边是右子树递归地对左右子树重复以上过程。这个“从后序找根、用中序切分”的模板是解决一切遍历序列还原问题的关键。哈夫曼树和哈夫曼编码也出现在填空题里让你根据给定权值构造哈夫曼树并计算带权路径长度WPL。这题不难但计算量大很多人容易在合并最小两个节点时看走眼。避免错误的方法是每次从森林中选权值最小的两个节点合并后重新放回森林并用笔把每一轮的森林状态列清楚不要纯靠心算。2.4 图算法多手算易错图这一章在试卷里占了相当比重主要是应用题。最小生成树和最短路径是两座大山2021年秋季学期试卷里两座大山都考了。Prim算法和Kruskal算法的区别是选择题常客。Prim从一个顶点出发逐步扩展生成树适合稠密图Kruskal按边权递增顺序选择边用并查集判断是否成环适合稀疏图。表格对比是复习时的主要工具算法策略数据结构时间复杂度适用场景Prim从点出发每次选最小邻接边邻接矩阵/堆O(V^2)或O(E log V)稠密图Kruskal按边权排序选不成环的边并查集O(E log E)稀疏图Dijkstra算法的手算过程是应用题重头戏。题目给出一个带权有向图和源点要求写出从源点到各顶点的最短路径生成过程。很多人在这里丢分不是因为不会算法而是因为中间过程的表格填写不完整。这里有一个实用技巧手工执行Dijkstra时一定要用表格记录每个顶点的dist值和path值每一轮选择一个未访问的最小dist顶点加入集合然后更新邻接顶点的dist。表格列清楚既方便检查也方便阅卷老师给分。最短路径相关热词里还有数据结构排序算法这两个章节在应用层面经常结合。比如2021年试卷里有一道综合题给出一个图要求先画出邻接表再基于邻接表写出从某顶点出发的DFS和BFS序列。这类题的难点在于邻接表中每个顶点的邻接点顺序会影响遍历结果。如果你在图里把边的存储顺序写错了后面所有序列都会跟着错。所以做题顺序很重要先认真画邻接表检查每个顶点的邻接点顺序是否合理再开始遍历。2.5 查找哈希题正在成为必考查找这一章2021年秋季学期期末的命题集中在哈希表和二叉排序树。热词里有数据结构高频核心知识点面试查找结构恰好是笔试面试都喜欢考的内容。二叉排序树的题目通常是这样的给定一个关键字序列依次插入构造二叉排序树求查找成功的平均查找长度ASL或者给定一个待删除节点要求删除后仍然保持二叉排序树性质。删除操作是重点也是难点删除叶子节点直接删删除只有一个子树的节点则用子树顶替删除有两个子树的节点用左子树最大值或右子树最小值顶替。哈希表题目出得非常典型给定关键字序列和哈希函数H(key) key % 11用线性探测法处理冲突构造哈希表并计算等概率情况下查找成功的平均查找长度。这类题需要你把每个关键字的探测过程写清楚计算ASL时统计每个关键字在查找时比较的次数。网上相关高频热词“哈希链”也反映出大家对哈希结构的关注。链地址法和线性探测法是两种互补的冲突处理方法期末一般只考一种但复习时两种都要掌握。链地址法计算ASL时每个链表的第一个节点比较次数为1第二个为2依此类推这个规则很直观。一个重要提醒哈希表的表长选择会影响探测次数。比如哈希函数取模11那表长一般设置成大于等于11的质数这样能有效减少冲突。试卷里如果给出的表长不是质数你要警惕计算结果可能不如预期那么整齐。2.6 排序稳定性、比较次数、每一趟结果排序是期末必考且最容易出计算量的大题。2021年秋季学期试卷里直接插入排序、快速排序和堆排序都有出镜其中快速排序的手算过程是很多人的失分点。热词里有数据结构python排序算法说明排序算法的实现语言差异也是大家关心的话题。但期末考拿着C语言教材命题核心还是算法思想本身语言只是实现工具。给你一个序列要求写出快速排序每一趟的结果这种题考察的是对划分过程的精确掌握。很多人只记住了快排的平均时间复杂度是O(n log n)却不清楚一趟划分后枢轴元素放在了哪个位置导致后续步骤全部错误。排序题有一个高频对比考点是稳定性。表格式记忆是最有效的方式排序算法稳定性平均时间复杂度最坏时间复杂度空间复杂度直接插入稳定O(n^2)O(n^2)O(1)希尔排序不稳定O(n^1.3)O(n^2)O(1)冒泡排序稳定O(n^2)O(n^2)O(1)快速排序不稳定O(n log n)O(n^2)O(log n)简单选择不稳定O(n^2)O(n^2)O(1)堆排序不稳定O(n log n)O(n log n)O(1)归并排序稳定O(n log n)O(n log n)O(n)这个表格建议打印下来贴在书桌前考前看一眼能避免很多“记混”的惨剧。3. 典型真题解析三道必会题带完整推演3.1 由中序和后序序列还原二叉树试卷简答题部分有一道非常规整的题已知二叉树的中序遍历序列为D B G E A C F后序遍历序列为D G E B F C A要求画出该二叉树并写出先序遍历序列。解题过程分三步走第一步从后序序列中取最后一个元素A它是整棵树的根节点。在中序序列中找到A的位置左侧D B G E是左子树的中序序列右侧C F是右子树的中序序列。第二步回到后序序列中左子树中序序列对应的后序片段是D G E B右子树对应的是F C。在D G E B中最后一个元素B是左子树的根同样在F C中最后一个元素C是右子树的根。第三步递归重复。B的左子树中序为D后序为D所以D是B的左孩子B的右子树中序为G E后序为G EE是根G是E的左孩子。C的右子树中序为F后序为F所以F是C的右孩子。最终二叉树结构清晰可画先序遍历序列为A B D E G C F。这类题不光期末要考考研408也频繁出现。核心是“递归切分”四个字任何包含树还原的题目都绕不开这个思想。3.2 哈希表构造与平均查找长度计算应用题里的哈希题是这样出的设哈希表长为11哈希函数H(key) key % 11采用线性探测法处理冲突将关键字序列{19, 14, 23, 1, 68, 20, 84, 27, 55, 11}依次插入表长为11的哈希表中。计算过程19 % 11 8放入下标8 14 % 11 3放入下标3 23 % 11 1放入下标1 1 % 11 1冲突线性探测到下标2放入 68 % 11 2冲突探测到下标4放入 20 % 11 9放入下标9 84 % 11 7放入下标7 27 % 11 5放入下标5 55 % 11 0放入下标0 11 % 11 0冲突依次探测下标1、2、3、4、5、6放入下标6最终哈希表状态为下标0到10依次存放55、23、1、14、68、27、11、84、19、20、空。平均查找长度ASL (1112311117) / 10 19 / 10 1.9。这道题的坑点在第10个关键字11的插入过程。因为前面已经有很多元素堆在表头区域导致线性探测走了很长一段路。很多同学算出来ASL偏小是因为只统计了成功查找的比较次数没有把探测过程中的每一步都算清楚。3.3 快速排序每趟结果手算排序题给的是序列{50, 26, 38, 80, 70, 90, 8, 30, 40, 60}要求写出快速排序前两趟划分后的序列状态第一趟以第一个元素50为枢轴。第一趟划分过程从右往左找比50小的元素找到40交换位置后序列为40, 26, 38, 80, 70, 90, 8, 30, 50, 60。 从左往右找比50大的元素找到80交换后序列为40, 26, 38, 50, 70, 90, 8, 30, 80, 60。 从右往左找比50小的元素找到30交换后序列为40, 26, 38, 30, 70, 90, 8, 50, 80, 60。 从左往右找比50大的元素找到70交换后序列为40, 26, 38, 30, 50, 90, 8, 70, 80, 60。 从右往左找比50小的元素找到8交换后序列为40, 26, 38, 30, 8, 90, 50, 70, 80, 60。 从左往右找比50大的元素找到90交换后序列为40, 26, 38, 30, 8, 50, 90, 70, 80, 60。此时枢轴50已经到达最终位置前半部分为40, 26, 38, 30, 8后半部分为90, 70, 80, 60。第二趟快排需要分别对左右两个子序列进行划分。左子序列以40为枢轴划分后得到8, 26, 38, 30, 40右子序列以90为枢轴划分后得到60, 70, 80, 90。因此第二趟结束后序列变为8, 26, 38, 30, 40, 50, 60, 70, 80, 90。手算快排要记住一个口诀先从右往左找小再从左往右找大每次交换后换方向继续直到两个指针相遇。很多同学考试时习惯用“挖坑法”手算会更快更清晰但前提是必须清楚每一步挖坑的位置在哪里。4. 备考策略与易错点把功夫花在刀刃上4.1 期末冲刺的阶段性安排如果你是目标明确的期末考生复习时间建议至少留出三周。第一周用来过教材课后题和课上例题目标是唤醒记忆第二周集中刷题目标是把每个章节的典型题做熟第三周做真题和模拟题目标是把状态调整到考场节奏。配套资料上严蔚敏教材的课后题是底线习题集里的“算法设计题”是重点王道数据结构可以作为补充。但要注意一点期末考和考研408的难度方向不完全一样。408更偏重概念理解和综合应用但哈工大期末卷对代码书写能力的要求更高代码题分值占比大所以复习时不能只看不写一定要亲手在纸上写代码写到没有语法错误为止。王道课件在热词里出现率很高它最大的价值在于知识点的系统梳理。如果时间有限优先看王道的章节总结部分把每个章节的知识框架搭起来再去填充细节。4.2 考场答题节奏与取舍这套卷子的题量在中上水平正常速度做完整套卷大概需要100分钟留20分钟检查。但这只是理想情况实际考场上很多人会在应用题的某一步卡住导致算法题时间不够。我建议的答题策略是先花5分钟快速浏览全卷判断题目的难易分布选择题和填空题一气呵成遇到拿不准的题先标记跳过不要恋战简答题和应用题按顺序做但如果在某一步算错导致后面连续错误果断重算不要将错就错算法设计题留足30到40分钟第一题链表如果思路清晰先写第二题树如果没思路先写一个暴力解保底分数。这里有一个很重要的应试技巧算法设计题的阅卷通常是按点给分即使你写不出最优解只要思路正确、代码主体框架完整、核心操作写对也能拿到大部分分数。所以千万不要空题空题是最可惜的丢分方式。4.3 高频易错点清单根据考后大家的反馈结合我辅导过程中积累的经验这套卷子暴露出的高频易错点集中在以下几个方面易错点错误表现正确理解循环队列长度计算直接记忆公式遇到指针增减变化就混淆理解队尾指针指向最后一个元素的下一位置二叉树度与节点关系混淆度为2和度为1的节点数N0 N2 1总节点数 N0 N1 N2完全二叉树深度忘记向下取整floor(log2n) 1哈夫曼树构造合并后忘记重新排序每次选最小的两个节点Dijkstra更新dist更新时未考虑所有邻接顶点松弛操作必须检查所有未访问邻接点DFS和BFS序列未注意邻接表边的存储顺序邻接点顺序决定遍历结果快排稳定性误认为快速排序稳定不稳定交换可能改变相等元素相对顺序栈和队列的判满判空混淆两种方案牺牲单元法和size域法条件不同哈希表ASL计算只统计成功查找忽略探测次数从每个关键字的探测起点开始累计这张表考前最后一天过一遍比多做三套模拟题都管用。因为这些都是命题老师最喜欢埋的雷你提前排掉了考场上的容错率就高很多。5. 从期末卷看考研408与面试同一套知识体系的两种考法5.1 与考研408数据结构的重合度很多备考考研的同学也在关注这套期末试卷因为它和408数据结构科目的重合度很高。回顾一下试卷中的考点二叉树遍历还原、图的最短路径、哈希表查找、快速排序过程——这些在408真题里几乎是年年出现的“常客”。但二者有一个明显区别408的数据结构选择题更侧重概念对比比如某些操作的适用场景、时间复杂度的量级判断而哈工大期末卷更侧重手算过程和代码书写。所以如果你要同时备考期末和408复习策略应该是用408的选择题来巩固概念用期末的应用题和代码题来训练深度理解。两条线并行反而能互相成就。热词里的数据结构考研热度也印证了这一点。数据结构是计算机考研的专业课核心学透了期末内容408的数据结构部分基本上就有了七成以上的把握。剩下的三成需要靠真题训练来补齐。5.2 面试高频题在试卷中的投影值得关注的是这套期末试卷的算法设计题与互联网公司面试的高频手写代码题高度重叠。反转链表、判断链表是否有环、二叉树的中序遍历非递归实现、层序遍历、快排和归并的手写——这些既出现在期末试卷里也出现在面试官的题库里。数据结构面试热度在热词里的占比很高说明大家在求职时也在啃同一块硬骨头。如果你还在校认真准备这套期末试卷本质上就是在为将来的面试打基础。尤其是链表和二叉树这两类算法题面试中出现的概率极高而期末卷恰好把它们放在压轴位置逼你练熟这种“被迫式”训练其实是最有效的。面试和期末有一个差异面试允许你边想边写甚至可以和白板面试官讨论思路但期末是限时闭卷写错了没有反馈机会。所以在期末复习阶段我建议你在白纸上模拟面试场景看题、想思路、写代码、检查边界条件整个过程控制在15分钟内。这个训练对口试和笔试都有帮助。5.3 这套试卷给我的最大启发做完整套卷子复盘我最大的感受是数据结构这门课你真的不能靠“背”过关。选择填空考的是记忆但应用题和算法设计题考的是理解深度。你在考场上能写出多少正确代码取决于你在平时亲手写过多少行相关代码。这是最朴素也最真实的道理。如果你现在正在准备这门课的期末考试我的建议很直接别只看题动笔算别只背代码动笔写。把每个数据结构的操作亲手在纸上过一遍把每个算法的时间复杂度亲手推一遍比看任何辅导视频都管用。毕竟考场上拿笔的手不会骗你。
哈工大数据结构期末试题复盘：核心考点与算法设计全解析
期末最后一场考完楼道里全是讨论题目的声音“第二道算法题你用的递归还是非递归”“哈希那题平均查找长度算出来多少”哈尔滨工业大学2021年秋季学期数据结构期末试题在考后讨论里热度一直没降下去。不是因为题目偏而是它把“基础”二字考出了层次感——既有让人闭眼拿分的送分题也有让一半人卡在中途的代码题还有一道压轴设计题直接拉开区分度。这篇文章我打算从一个参加过这套卷复习、也带过不少学弟学妹做考前冲刺的视角把这套试卷的命题逻辑、核心考点、代表性题目解法以及背后折射出来的数据结构学习主线完整梳理一遍。内容不局限于“对答案”更重要的是讲清楚每一类题为什么这么出、应该用什么思路去拆。无论你是正在准备期末、备战考研还是单纯想检验一下自己的数据结构底子这份复盘都有参考价值。1. 试卷整体画像先看分值分布再看命题风格1.1 题型结构与分值占比从考后大家回忆拼出来的图景看这套试卷延续了哈工大近几年的稳定架构满分100分题型分为四大块题型题量分值考察侧重单项选择题10题20分基础概念、性质判定、时间复杂度填空题8题16分结论性知识、公式推理、存储结构细节简答与应用题4题32分树、图、查找、排序的综合计算与手工推演算法设计与分析2题32分链表/树相关代码编写策略分析和复杂度证明这个分值分配非常典型基础题选择填空占36分这部分考的是“背下来并能正确理解”的知识应用题占32分考的是“动笔算得出来”的功力算法设计占32分考的是“现场写得出代码且能分析”的能力。三个层次之间层层递进区分度也主要靠最后一大题拉开。1.2 难度梯度和命题倾向如果给这套卷子的难度画一条曲线大概是开篇选择题平缓起步中间应用题稳步爬坡最后算法题直接上强度。选择题第1到第5题基本是概念等价判断比如时间复杂度的量级比较、栈和队列的进出规则、二叉树性质公式这些题目不拐弯属于“复习过就能拿分”的类型。从第6题开始难度上来了。我印象比较深的一道选择题是关于循环队列的给出队头指针front和队尾指针rear的初始值以及入队出队若干次后的状态要求判断当前队列长度。这类题很容易在“牺牲一个存储单元判满”和“增设size域判满”两种方案之间绕晕本质考察的是你对两种实现方式差异的理解深度而不只是背公式。应用题部分图的最短路径和最小生成树是重头戏。考后很多人讨论Dijkstra算法的手算过程中某个中间节点的dist值更新顺序以及Prim算法从不同起点出发得到的结果是否一致。这类题目的杀伤力在于你理解了算法框架但不熟悉松弛操作的每一步很容易在中途写错一个数字后面全盘错。算法设计题暴露的问题最集中。第一题链表相关多数人能写但代码不够简洁第二题树相关压轴出现考后普遍反馈“有思路但不确定自己的实现是否符合最优复杂度要求”。这个下一章展开讲。1.3 与教材和课纲的对应关系哈工大本科阶段数据结构课程使用的教材是严蔚敏《数据结构C语言版》配套习题集在复习阶段使用率极高。这套期末试卷的命题范围严格对齐课纲没有超纲内容但部分题目难度高于教材课后习题更接近习题集里标记为“综合”或“提高”的题目。这意味着一个很关键的备考信息单纯刷课后题并不足以应对期末。你得学会把教材里分散在不同章节的知识串起来。比如试卷中有一道关于二叉树和栈结合的简答题让你用非递归方式实现中序遍历并写出过程中栈的状态变化。这题在教材上只出现在算法源码里但考试直接以“过程手写”的形式出现说明老师默认你对非递归遍历的栈操作非常熟练——这正是只看不练的人最容易翻车的地方。2. 核心考点逐项拆解六个板块一个不落2.1 线性表与链表变化最多的基础题线性表部分在试卷里占比不重选择题和填空题各占一道但算法设计题第一题基本锁定链表。这很好理解链表作为最基础又最具操作感的数据结构是考察“指针操作基本功”的最佳载体。相关热搜词里有一个很有意思数据结构链表。这说明大家普遍觉得链表知识零散、指针绕来绕去容易晕。但期末考并不像面试那样要求你在十分钟内手写一个复杂的链表操作而是更看重你对链表基本操作的掌握和对边界条件的敏感度。这套卷子里链表相关的题目从考后反馈拼出来看大致有这几类给定单链表头指针删除值为x的所有节点要求时间O(n)、空间O(1)判断一个单链表是否有环并给出证明将两个递增有序链表合并为一个递减有序链表这类题的共同特点是算法本身不难但代码的细节决定成败。以删除值为x的所有节点为例很多人会忘记处理头节点就是x的情况。正确做法是引入一个虚拟头节点dummy让dummy-next指向原链表头这样对原头节点的操作就统一成了对普通节点的操作代码逻辑立刻清晰。实际上我在辅导过程中发现链表题的代码风格往往能看出一个人是不是真的理解指针。写得干净的人一定会优先想到虚拟头节点写得乱的人基本上是在用if硬分类讨论。期末复习时如果能把“虚拟头节点”“双指针”“递归转迭代”这三板斧练熟链表题基本可以做到秒写。2.2 栈与队列概念少计算多栈和队列在这套卷子里的表现是不鸣则已一鸣惊人。选择题有一道关于栈的经典坑题元素a、b、c、d、e依次入栈不可能得到的出栈序列是什么这类题在期末题库里反复出现但2021年这道题加了一个变化出栈过程中允许入栈操作暂停本质考的仍然是卡特兰数约束下的合法性判断。队列部分的考察集中在循环队列。填空题让你写出在“牺牲一个存储单元”的方案下队列满的判断条件(rear 1) % MaxSize front以及队列长度公式(rear - front MaxSize) % MaxSize。很多人只背了公式遇到队列指针增减的变体题就开始乱套公式其实追根到底这两个公式都是从“队头指针指向队头元素队尾指针指向队尾元素的下一个位置”这个约定推导出来的。理解了约定的背后逻辑任何变体题都迎刃而解。应用题里有一道表达式求值给出中缀表达式A B * (C - D) / E要求写出转换为后缀表达式的过程并说明栈的变化。这道题非常经典在考研408和各大厂笔试里都是常客。解法的关键点是操作符的入栈和出栈时机取决于当前操作符与栈顶操作符的优先级比较。当当前操作符优先级低于等于栈顶时栈顶出栈并输出。括号的处理则是左括号直接入栈遇到右括号则依次弹出直到左括号。这类题一旦你把规则总结成“优先级比栈顶低就弹栈括号特殊处理运算数直接输出”那无论表达式怎么变你都能手算出来完全不需要临时推理。2.3 树与二叉树试卷的分水岭树是数据结构课程的核心也是这套期末试卷的分水岭。选择、填空、简答、算法设计全覆盖分值占比接近30%是所有章节里最高的。这跟热词里数据结构树的高热度完全吻合——树学不好数据结构等于没学。选择题里有几道考察二叉树基本性质的题目度为2的节点数等于叶子节点数减1n个节点的完全二叉树深度为floor(log2n)1二叉树的第i层最多有2^(i-1)个节点。这些公式简单但考试不会直接让你默写而是包装成应用场景。比如已知一棵完全二叉树有1001个节点求叶子节点个数。这种题需要你综合运用完全二叉树的性质和满二叉树的结构特点来推导光靠背公式是拿不稳的。简答题里最经典的一道已知一棵二叉树的中序序列和后序序列要求画出这棵二叉树并写出先序序列。这个考法在哈工大期末几乎是必考题因为它综合考察了三种遍历顺序之间的关系。解法思路是后序序列的最后一个节点是根节点找到根节点在中序序列中的位置左边是左子树、右边是右子树递归地对左右子树重复以上过程。这个“从后序找根、用中序切分”的模板是解决一切遍历序列还原问题的关键。哈夫曼树和哈夫曼编码也出现在填空题里让你根据给定权值构造哈夫曼树并计算带权路径长度WPL。这题不难但计算量大很多人容易在合并最小两个节点时看走眼。避免错误的方法是每次从森林中选权值最小的两个节点合并后重新放回森林并用笔把每一轮的森林状态列清楚不要纯靠心算。2.4 图算法多手算易错图这一章在试卷里占了相当比重主要是应用题。最小生成树和最短路径是两座大山2021年秋季学期试卷里两座大山都考了。Prim算法和Kruskal算法的区别是选择题常客。Prim从一个顶点出发逐步扩展生成树适合稠密图Kruskal按边权递增顺序选择边用并查集判断是否成环适合稀疏图。表格对比是复习时的主要工具算法策略数据结构时间复杂度适用场景Prim从点出发每次选最小邻接边邻接矩阵/堆O(V^2)或O(E log V)稠密图Kruskal按边权排序选不成环的边并查集O(E log E)稀疏图Dijkstra算法的手算过程是应用题重头戏。题目给出一个带权有向图和源点要求写出从源点到各顶点的最短路径生成过程。很多人在这里丢分不是因为不会算法而是因为中间过程的表格填写不完整。这里有一个实用技巧手工执行Dijkstra时一定要用表格记录每个顶点的dist值和path值每一轮选择一个未访问的最小dist顶点加入集合然后更新邻接顶点的dist。表格列清楚既方便检查也方便阅卷老师给分。最短路径相关热词里还有数据结构排序算法这两个章节在应用层面经常结合。比如2021年试卷里有一道综合题给出一个图要求先画出邻接表再基于邻接表写出从某顶点出发的DFS和BFS序列。这类题的难点在于邻接表中每个顶点的邻接点顺序会影响遍历结果。如果你在图里把边的存储顺序写错了后面所有序列都会跟着错。所以做题顺序很重要先认真画邻接表检查每个顶点的邻接点顺序是否合理再开始遍历。2.5 查找哈希题正在成为必考查找这一章2021年秋季学期期末的命题集中在哈希表和二叉排序树。热词里有数据结构高频核心知识点面试查找结构恰好是笔试面试都喜欢考的内容。二叉排序树的题目通常是这样的给定一个关键字序列依次插入构造二叉排序树求查找成功的平均查找长度ASL或者给定一个待删除节点要求删除后仍然保持二叉排序树性质。删除操作是重点也是难点删除叶子节点直接删删除只有一个子树的节点则用子树顶替删除有两个子树的节点用左子树最大值或右子树最小值顶替。哈希表题目出得非常典型给定关键字序列和哈希函数H(key) key % 11用线性探测法处理冲突构造哈希表并计算等概率情况下查找成功的平均查找长度。这类题需要你把每个关键字的探测过程写清楚计算ASL时统计每个关键字在查找时比较的次数。网上相关高频热词“哈希链”也反映出大家对哈希结构的关注。链地址法和线性探测法是两种互补的冲突处理方法期末一般只考一种但复习时两种都要掌握。链地址法计算ASL时每个链表的第一个节点比较次数为1第二个为2依此类推这个规则很直观。一个重要提醒哈希表的表长选择会影响探测次数。比如哈希函数取模11那表长一般设置成大于等于11的质数这样能有效减少冲突。试卷里如果给出的表长不是质数你要警惕计算结果可能不如预期那么整齐。2.6 排序稳定性、比较次数、每一趟结果排序是期末必考且最容易出计算量的大题。2021年秋季学期试卷里直接插入排序、快速排序和堆排序都有出镜其中快速排序的手算过程是很多人的失分点。热词里有数据结构python排序算法说明排序算法的实现语言差异也是大家关心的话题。但期末考拿着C语言教材命题核心还是算法思想本身语言只是实现工具。给你一个序列要求写出快速排序每一趟的结果这种题考察的是对划分过程的精确掌握。很多人只记住了快排的平均时间复杂度是O(n log n)却不清楚一趟划分后枢轴元素放在了哪个位置导致后续步骤全部错误。排序题有一个高频对比考点是稳定性。表格式记忆是最有效的方式排序算法稳定性平均时间复杂度最坏时间复杂度空间复杂度直接插入稳定O(n^2)O(n^2)O(1)希尔排序不稳定O(n^1.3)O(n^2)O(1)冒泡排序稳定O(n^2)O(n^2)O(1)快速排序不稳定O(n log n)O(n^2)O(log n)简单选择不稳定O(n^2)O(n^2)O(1)堆排序不稳定O(n log n)O(n log n)O(1)归并排序稳定O(n log n)O(n log n)O(n)这个表格建议打印下来贴在书桌前考前看一眼能避免很多“记混”的惨剧。3. 典型真题解析三道必会题带完整推演3.1 由中序和后序序列还原二叉树试卷简答题部分有一道非常规整的题已知二叉树的中序遍历序列为D B G E A C F后序遍历序列为D G E B F C A要求画出该二叉树并写出先序遍历序列。解题过程分三步走第一步从后序序列中取最后一个元素A它是整棵树的根节点。在中序序列中找到A的位置左侧D B G E是左子树的中序序列右侧C F是右子树的中序序列。第二步回到后序序列中左子树中序序列对应的后序片段是D G E B右子树对应的是F C。在D G E B中最后一个元素B是左子树的根同样在F C中最后一个元素C是右子树的根。第三步递归重复。B的左子树中序为D后序为D所以D是B的左孩子B的右子树中序为G E后序为G EE是根G是E的左孩子。C的右子树中序为F后序为F所以F是C的右孩子。最终二叉树结构清晰可画先序遍历序列为A B D E G C F。这类题不光期末要考考研408也频繁出现。核心是“递归切分”四个字任何包含树还原的题目都绕不开这个思想。3.2 哈希表构造与平均查找长度计算应用题里的哈希题是这样出的设哈希表长为11哈希函数H(key) key % 11采用线性探测法处理冲突将关键字序列{19, 14, 23, 1, 68, 20, 84, 27, 55, 11}依次插入表长为11的哈希表中。计算过程19 % 11 8放入下标8 14 % 11 3放入下标3 23 % 11 1放入下标1 1 % 11 1冲突线性探测到下标2放入 68 % 11 2冲突探测到下标4放入 20 % 11 9放入下标9 84 % 11 7放入下标7 27 % 11 5放入下标5 55 % 11 0放入下标0 11 % 11 0冲突依次探测下标1、2、3、4、5、6放入下标6最终哈希表状态为下标0到10依次存放55、23、1、14、68、27、11、84、19、20、空。平均查找长度ASL (1112311117) / 10 19 / 10 1.9。这道题的坑点在第10个关键字11的插入过程。因为前面已经有很多元素堆在表头区域导致线性探测走了很长一段路。很多同学算出来ASL偏小是因为只统计了成功查找的比较次数没有把探测过程中的每一步都算清楚。3.3 快速排序每趟结果手算排序题给的是序列{50, 26, 38, 80, 70, 90, 8, 30, 40, 60}要求写出快速排序前两趟划分后的序列状态第一趟以第一个元素50为枢轴。第一趟划分过程从右往左找比50小的元素找到40交换位置后序列为40, 26, 38, 80, 70, 90, 8, 30, 50, 60。 从左往右找比50大的元素找到80交换后序列为40, 26, 38, 50, 70, 90, 8, 30, 80, 60。 从右往左找比50小的元素找到30交换后序列为40, 26, 38, 30, 70, 90, 8, 50, 80, 60。 从左往右找比50大的元素找到70交换后序列为40, 26, 38, 30, 50, 90, 8, 70, 80, 60。 从右往左找比50小的元素找到8交换后序列为40, 26, 38, 30, 8, 90, 50, 70, 80, 60。 从左往右找比50大的元素找到90交换后序列为40, 26, 38, 30, 8, 50, 90, 70, 80, 60。此时枢轴50已经到达最终位置前半部分为40, 26, 38, 30, 8后半部分为90, 70, 80, 60。第二趟快排需要分别对左右两个子序列进行划分。左子序列以40为枢轴划分后得到8, 26, 38, 30, 40右子序列以90为枢轴划分后得到60, 70, 80, 90。因此第二趟结束后序列变为8, 26, 38, 30, 40, 50, 60, 70, 80, 90。手算快排要记住一个口诀先从右往左找小再从左往右找大每次交换后换方向继续直到两个指针相遇。很多同学考试时习惯用“挖坑法”手算会更快更清晰但前提是必须清楚每一步挖坑的位置在哪里。4. 备考策略与易错点把功夫花在刀刃上4.1 期末冲刺的阶段性安排如果你是目标明确的期末考生复习时间建议至少留出三周。第一周用来过教材课后题和课上例题目标是唤醒记忆第二周集中刷题目标是把每个章节的典型题做熟第三周做真题和模拟题目标是把状态调整到考场节奏。配套资料上严蔚敏教材的课后题是底线习题集里的“算法设计题”是重点王道数据结构可以作为补充。但要注意一点期末考和考研408的难度方向不完全一样。408更偏重概念理解和综合应用但哈工大期末卷对代码书写能力的要求更高代码题分值占比大所以复习时不能只看不写一定要亲手在纸上写代码写到没有语法错误为止。王道课件在热词里出现率很高它最大的价值在于知识点的系统梳理。如果时间有限优先看王道的章节总结部分把每个章节的知识框架搭起来再去填充细节。4.2 考场答题节奏与取舍这套卷子的题量在中上水平正常速度做完整套卷大概需要100分钟留20分钟检查。但这只是理想情况实际考场上很多人会在应用题的某一步卡住导致算法题时间不够。我建议的答题策略是先花5分钟快速浏览全卷判断题目的难易分布选择题和填空题一气呵成遇到拿不准的题先标记跳过不要恋战简答题和应用题按顺序做但如果在某一步算错导致后面连续错误果断重算不要将错就错算法设计题留足30到40分钟第一题链表如果思路清晰先写第二题树如果没思路先写一个暴力解保底分数。这里有一个很重要的应试技巧算法设计题的阅卷通常是按点给分即使你写不出最优解只要思路正确、代码主体框架完整、核心操作写对也能拿到大部分分数。所以千万不要空题空题是最可惜的丢分方式。4.3 高频易错点清单根据考后大家的反馈结合我辅导过程中积累的经验这套卷子暴露出的高频易错点集中在以下几个方面易错点错误表现正确理解循环队列长度计算直接记忆公式遇到指针增减变化就混淆理解队尾指针指向最后一个元素的下一位置二叉树度与节点关系混淆度为2和度为1的节点数N0 N2 1总节点数 N0 N1 N2完全二叉树深度忘记向下取整floor(log2n) 1哈夫曼树构造合并后忘记重新排序每次选最小的两个节点Dijkstra更新dist更新时未考虑所有邻接顶点松弛操作必须检查所有未访问邻接点DFS和BFS序列未注意邻接表边的存储顺序邻接点顺序决定遍历结果快排稳定性误认为快速排序稳定不稳定交换可能改变相等元素相对顺序栈和队列的判满判空混淆两种方案牺牲单元法和size域法条件不同哈希表ASL计算只统计成功查找忽略探测次数从每个关键字的探测起点开始累计这张表考前最后一天过一遍比多做三套模拟题都管用。因为这些都是命题老师最喜欢埋的雷你提前排掉了考场上的容错率就高很多。5. 从期末卷看考研408与面试同一套知识体系的两种考法5.1 与考研408数据结构的重合度很多备考考研的同学也在关注这套期末试卷因为它和408数据结构科目的重合度很高。回顾一下试卷中的考点二叉树遍历还原、图的最短路径、哈希表查找、快速排序过程——这些在408真题里几乎是年年出现的“常客”。但二者有一个明显区别408的数据结构选择题更侧重概念对比比如某些操作的适用场景、时间复杂度的量级判断而哈工大期末卷更侧重手算过程和代码书写。所以如果你要同时备考期末和408复习策略应该是用408的选择题来巩固概念用期末的应用题和代码题来训练深度理解。两条线并行反而能互相成就。热词里的数据结构考研热度也印证了这一点。数据结构是计算机考研的专业课核心学透了期末内容408的数据结构部分基本上就有了七成以上的把握。剩下的三成需要靠真题训练来补齐。5.2 面试高频题在试卷中的投影值得关注的是这套期末试卷的算法设计题与互联网公司面试的高频手写代码题高度重叠。反转链表、判断链表是否有环、二叉树的中序遍历非递归实现、层序遍历、快排和归并的手写——这些既出现在期末试卷里也出现在面试官的题库里。数据结构面试热度在热词里的占比很高说明大家在求职时也在啃同一块硬骨头。如果你还在校认真准备这套期末试卷本质上就是在为将来的面试打基础。尤其是链表和二叉树这两类算法题面试中出现的概率极高而期末卷恰好把它们放在压轴位置逼你练熟这种“被迫式”训练其实是最有效的。面试和期末有一个差异面试允许你边想边写甚至可以和白板面试官讨论思路但期末是限时闭卷写错了没有反馈机会。所以在期末复习阶段我建议你在白纸上模拟面试场景看题、想思路、写代码、检查边界条件整个过程控制在15分钟内。这个训练对口试和笔试都有帮助。5.3 这套试卷给我的最大启发做完整套卷子复盘我最大的感受是数据结构这门课你真的不能靠“背”过关。选择填空考的是记忆但应用题和算法设计题考的是理解深度。你在考场上能写出多少正确代码取决于你在平时亲手写过多少行相关代码。这是最朴素也最真实的道理。如果你现在正在准备这门课的期末考试我的建议很直接别只看题动笔算别只背代码动笔写。把每个数据结构的操作亲手在纸上过一遍把每个算法的时间复杂度亲手推一遍比看任何辅导视频都管用。毕竟考场上拿笔的手不会骗你。
