简介这是一份专为考研学子整理的数据结构与算法题总结文档覆盖893自命题与408统考常考题型适合计算机类专业备考人群使用。资料以PDF格式呈现共1个文件压缩包大小约1.67MB内容精炼但涵盖面广。目前已由1681人学习浏览足见其备考参考价值。文档围绕数组、链表、栈、队列、二叉树等核心数据结构系统梳理了合并排序数组、约瑟夫环、栈实现队列、链表删除与反转、二叉树遍历与构建等典型题目算法部分则涉及插入、快排、堆排、归并等排序方法以及双指针、二分查找、贪心、动态规划、DFS等高频解题技巧。所有题目均整理为可直接练习的形式部分附有C代码示例与解题思路便于考生对照自查、反复演练。无论是冲刺阶段的题型回顾还是平时的专项突破这份36页的总结都能帮助读者快速定位薄弱环节提升解题效率。1. 考研数据结构的 36 页提炼法893 和 408 两套考点从题型差异切入考研数据结构是计算机考研人绕不开的一道坎。408 统考里数据结构只占 150 分中的一小部分算法题藏在大题里分值有限而 893 这类自命题科目经常把代码题铺满一整张卷子链表、树、图轮着出。一份 36 页的总结要同时服务两套卷子靠的不是把教材抄薄而是把高频考点压缩成一张可反复过的地图——哪些题必考、哪些模板必背、哪些边界条件容易丢分。这篇笔记就按这个思路拆开讲先捋清 893 和 408 的差异再拆高频算法题的模板和手写规范最后是踩坑与冲刺用法。2. 893 和 408 的题型差异早一天看清少走十天弯路很多人拿到复习资料第一反应是翻开第一页顺着背花了两周翻完才发现重点错了。与其盲目从头读不如先花半天弄清楚 893 和 408 两套卷子的差异把 36 页的使用策略定下来。这个半天花得非常值它直接决定你按什么顺序复习、在哪些页上停留多久、哪些页面可以直接跳过。2.1 408 统考数据结构的分量选择题靠概念大题靠代码408 是计算机学科专业基础综合的统考代码涵盖数据结构、计算机组成原理、操作系统、计算机网络四门科目总分 150 分。数据结构在里面一般占 45 分上下考试安排在选择题和综合应用题两种题型里选择题大约 11 道多数考查概念辨析和简单推导综合题会有一到两道以数据结构为主题的题目其中经常包含一个设计算法并写出代码的小问。这里有个容易被低估的事实选择题覆盖广泛错了就是实打实的 2 分算法大题分值更高但考法非常稳定历年真题的算法设计题基本绕不开链表操作、二叉树遍历、排序和查找这几个主题。换句话说算法大题的分数是最容易通过模板训练拿到的。复习材料大家平时用王道、天勤这类辅导书但到了临考阶段一本按题型整理的 36 页笔记比零散翻一本大书效率高得多。408 的复习节奏建议前期用辅导书打基础第一轮重点是理解概念和做选择题中期开始把算法大题的常见题型分类整理进自己的总结资料后期每天默写一到两个代码模板维持手写手感。数据结构这门课的代码题属于投入产出比最高的部分因为出题方向有限练熟五六个模板就能覆盖绝大多数考点。2.2 893 自命题的考察方式代码量更大题目更直给893 是部分院校自命题科目的代码具体科目名称和考试大纲要上目标院校官网查。不同学校 893 的风格差异比较大但总体有几个共性代码题分值占比明显高于 408可能达到卷面的一半以上线性表和树是命题重点图有时会出复杂的应用题题目描述通常比较简练给的信息比 408 少需要自己判断边界条件。举个例子408 的二叉树题通常要求写出遍历序列或判断性质但 893 可能要求写出计算二叉树中所有结点值之和的递归函数甚至要求处理带父指针的结点结构。这类题本身不难但如果你一直按 408 的难度准备考场上会感觉题面很陌生思路要卡好一会儿。如果你的目标院校是 893 自命题建议在 36 页的代码模板区里多增补链表增删改查、二叉树递归算法、图的深度优先遍历三个方向的模板。同时一定要找目标院校近三年的真题核对一次看它的大题到底考了什么再决定在 36 页的哪些位置补充内容。最好把真题的题型归类写进总结的最后一页冲刺阶段反复对照。2.3 拿到 36 页先分块按题型排而不是按章节排许多同学整理笔记习惯按教材章节线性表一章、栈队列一章、树一章这种排法适合第一轮系统学习。但到了总结阶段一份能直接用于答题的 36 页材料应该按题型重新排列。常见的排列结构是五大块概念快查区5 页左右时间复杂度计算规则、栈和队列进出序列推导、二叉树性质、排序稳定性和复杂度对比、哈希冲突处理。这些是选择题的高频点考前每天翻一遍。代码模板区12 页左右每一页一个完整可用的代码模板链表逆置、链表删除、二叉树非递归遍历、图的 DFS/BFS、Dijkstra、快速排序 partition、KMP next 数组。页面下方留白写这个模板常考的变形点。应用套路区8 页左右把大题的常见场景归纳为固定解法例如判断二叉树是否二叉搜索树用中序遍历、求两个有序序列的中位数用归并思想、判断图中是否有环用拓扑排序。易错点清单6 页左右记录刷题过程中反复出错的地方例如忘记判空、循环边界写错、递归缺少终止条件等每条配一个正确的代码片段。附录区剩余页放真题高频考点统计表和复杂度速查表。拿到手的 36 页如果本身已经分好章节建议在目录页做三个记号标红的页属于代码模板区标蓝的页属于概念快查区标黄的页属于应用套路区。这样做的好处是最后两周复习时只翻标黄区和标红区标蓝区每周过一遍即可。别小看这个整理动作它决定了冲刺阶段你是在翻资料还是在查答案。3. 高频算法题模板链表、树、图、串的四个固定套路考研范围内的算法题考的全是套路。不管是 408 还是 893出题人不会故意出偏题怪题每个知识点都有两三个固定考法。把套路拆成模板之后剩下的事情只是填参数。这一章把最常考的四个方向逐一类比过去每个模板都是可以直接抄进自己 36 页的标准形态。3.1 链表题头结点、双指针、就地逆置三个固定套路链表是最爱出代码题的数据结构因为它既能考指针操作又能考边界条件。考研链表题绝大多数可以归入三个套路。第一个套路是头结点的妙用。考研常用的链表定义是带头结点的单链表头结点不存数据只做标记。它的作用是让空表和非空表的处理逻辑统一在表头插入元素时不需要单独讨论头指针是否为空。插入操作的代码骨架长这样typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 带头结点的链表插入在第 i 个位置插入元素 e bool ListInsert(LinkList L, int i, int e) { if (i 1) return false; LNode *p L; // p 指向头结点 int j 0; // 当前 p 指向的是第 j 个结点头结点算第 0 个 while (p ! NULL j i - 1) { // 找到第 i-1 个结点 p p-next; j; } if (p NULL) return false; // i 超出了链表长度插入位置非法 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next p-next; p-next s; return true; }这段代码的关键在于循环条件j i - 1和p ! NULL缺一不可漏掉前者会把元素插到目标位置的下一个漏掉后者则会在插入位置越界时访问空指针。很多同学考试时把j i - 1写成j i元素永远错位这就是对头结点算第 0 个结点这个约定不熟的表现。第二个套路是双指针也叫快慢指针。找链表的中间结点、判断链表是否有环、找倒数第 k 个结点都可以用快慢指针在 O(n) 时间内完成。核心理念是一个指针每次走一步另一个指针每次走两步当快指针到达尾端时慢指针正好在中间。判断有环时让快指针不断追赶慢指针相遇就说明有环。第三个套路是就地逆置链表这个几乎是 893 的必考池。就地逆置用三个指针 pre、p、r 依次把每个结点的 next 指向前驱代码模板固定为// 带头结点链表的就地逆置 LinkList ReverseList(LinkList L) { if (L-next NULL) return L; // 空链表直接返回 LNode *pre L-next; // pre 指向原链表第一个结点 LNode *p pre-next; // p 指向第二个结点 LNode *r; pre-next NULL; // 逆置后第一个结点变成尾结点 while (p ! NULL) { r p-next; // 先保存下一个结点防止断链 p-next pre; // 当前结点指向前驱 pre p; // pre 往后移动 p r; // p 往后移动 } L-next pre; // 最后 pre 就是逆置后的第一个结点 return L; }注意两处一是r p-next必须在修改 next 之前执行否则一旦改了 next 就找不回原链表的后续结点了二是循环结束后 pre 停在原链表最后一个结点上把 L 的 next 指向它即可。这个顺序写错是链表逆置题最常见的翻车原因。3.2 树与二叉树递归遍历和非递归遍历的填空式模板树的代码题是 893 的高频区408 也喜欢在这里出应用题。二叉树的遍历是树题目的基本功递归遍历背下来很简单但考试真正拉开差距的是非递归遍历。先看递归遍历的最简形式以中序为例void InOrder(BiTree T) { if (T NULL) return; InOrder(T-lchild); // 遍历左子树 visit(T); // 访问根结点 InOrder(T-rchild); // 遍历右子树 }递归版只要记住一句话左根右、根左右、左右根。但很多 408 和 893 的题目会要求写出不用递归的中序遍历算法这里的本质是让你用手动栈模拟递归过程。非递归中序的标准写法是void InOrderNonRecur(BiTree T) { Stack S; InitStack(S); BiTree p T; while (p ! NULL || !StackEmpty(S)) { if (p ! NULL) { Push(S, p); // 根结点进栈 p p-lchild; // 一路向左把所有左子树结点压栈 } else { Pop(S, p); // 弹出一个结点 visit(p); // 访问它 p p-rchild; // 转向右子树 } } }非递归中序的循环条件是p ! NULL || 栈不空缺了栈不空这个条件遍历到根结点之后循环会提前结束。先序非递归只需把访问挪到入栈前后序非递归要加一个标记位区分右子树是否已处理多数学校要求不高但中序和先序必须能默写。树相关的应用题还会利用遍历顺序的性质出题。比如给定前序和中序序列重建二叉树本质是找根结点并递归切分左右子树判断一棵树是否为二叉搜索树就是中序遍历并检查是否递增求二叉树高度就是后序遍历的变种。这类题比单纯遍历更简单因为在访问结点的位置替换成具体逻辑就行。3.3 图与字符串拓扑排序、KMP next 数组的固定解法图这个章节在 408 里选择题占多数在 893 里可能出大题。图的代码题最常考的是遍历和拓扑排序遍历代码本身就是模板很少变形// 已知邻接表 G从顶点 v 开始深度优先遍历 void DFS(ALGraph G, int v, bool visited[]) { visited[v] true; visit(v); // 访问顶点 v ArcNode *p G.vertices[v].firstarc; while (p ! NULL) { int w p-adjvex; if (!visited[w]) { DFS(G, w, visited); // 递归访问未访问的邻接顶点 } p p-nextarc; } }DFS 的代码本身不复杂真正的坑在外面那层循环。要遍历整个图的所有连通分量必须在外层遍历所有顶点for (int v 0; v G.vexnum; v) if (!visited[v]) DFS(G, v, visited);这个外层循环如果漏写非连通图就无法完整遍历在判断图中两个顶点是否连通的题目里会直接丢分。字符串算法里最值得下功夫的是 KMP。408 考选择题算 next 数组属于送分题893 偶尔要求写出 next 数组推导或完整的 KMP 函数。next 数组的推导有一个固定口诀最长相等前后缀长度右移一位首位填 -1。代码模板长期不变// 计算模式串 T 的 next 数组0 下标版本next[0] -1 void get_next(char T[], int next[]) { int i 0, j -1; next[0] -1; int n strlen(T); while (i n - 1) { if (j -1 || T[i] T[j]) { i; j; next[i] j; } else { j next[j]; // 回溯这是 KMP 的精髓 } } }这里用的是 0 下标版本的 next 数组初值 next[0] -1。不少教材用 1 下标版本next[1] 0两者之间差一位换算不同资料混看时最容易绕晕。建议备考时选定一个版本练到底做题时先确认题目给出的下标起点否则整个数组都会错位。这些模板抄一遍不算完要按先读懂、再默写、最后变体三步来练。读懂变量含义默写时不看参考变体训练是让自己能调整循环条件去适应题目的具体场景。4. 手写代码题的判分逻辑从草稿到成稿的流程与复杂度验证考研算法题和算法工程师面试有个明显区别面试更看重思路和沟通而笔试阅卷是按步骤给分的卷面上留下的推理过程、边界判断、复杂度分析都会被纳入评分。理解判分逻辑就能反过来指导你如何组织答案。4.1 判分逻辑边界、复杂度、命名都算分408 和 893 的算法大题没有全国统一评分细则阅卷通常按步骤给分阅卷老师拿到一份答案后会重点看三个位置循环边界、空指针判断、返回值。如果你的答案里只有一段代码而没有文字说明即使代码逻辑正确也容易丢掉算法思路那几个步骤分。常见做法是在代码开头用两三行写上算法思想例如采用双指针法pre 指向当前结点的前驱p 遍历链表遇到值为 x 的结点则删除。这句话不需要写得多专业但它能让阅卷老师快速理解你的代码逻辑也能在代码有小错时帮你保留主要分数。复杂度也值得单列一行写在答案末尾时间复杂度 O(n)空间复杂度 O(1)。这既是给阅卷老师看的也是给你自己看的。如果你设计的算法是双重循环却写了个 O(n) 的复杂度那就说明代码和思路不匹配需要回头检查。复杂度分析不是形式主义的附加题它是验证答案正确性的一道保险。4.2 一道完整题目的手写过程从题干到落笔成稿以一道典型的链表题为例设计一个尽可能高效的算法删除带头结点单链表 L 中所有值为 x 的结点。这道题在 408 和 893 里都出现过类似版本正好用来演示完整的手写答题流程。第一步读题确认数据结构定义。题面说带头结点所以 L 指向头结点L-next 指向第一个数据结点。第二步画草图。在草稿纸上画出链表被删结点的三个位置x 在头部、x 在中间、x 在尾部。画完就会发现三个位置的处理逻辑其实一样用 pre 和 p 两个指针就行。第三步写成稿代码// 删除带头结点单链表中所有值为 x 的结点 void DeleteAllX(LinkList L, int x) { LNode *pre L; // pre 始终指向当前结点的前驱 LNode *p L-next; // p 从第一个数据结点开始扫描 while (p ! NULL) { if (p-data x) { LNode *temp p; pre-next p-next; // 跳过当前结点 p pre-next; // p 往后移动pre 保持不动 free(temp); // 释放被删除的结点 } else { pre p; // 不删除时pre 跟上 p p p-next; // p 往后移动 } } }这段代码的关键在删除分支里pre不动、p直接指向下一个结点因为删掉当前结点后 pre 仍然是新当前结点的前驱只有不删除时 pre 才跟着 p 移动。这个分支逻辑搞反的话连续两个相同值的结点就删不干净。第四步验证边界。空链表时 L-next 为 NULL循环直接不进入链表只有一个结点且值为 x 时删除后 pre-next 变成 NULL符合预期x 在链表头部时pre 指向头结点p 指向第一个数据结点删除后头结点顺势成为链表的开头这也是带头结点设计的好处。第五步补充复杂度。时间复杂度 O(n)因为只遍历了一遍空间复杂度 O(1)因为只用了常数个辅助指针。这样的话这份答案从算法思路、代码到边界说明和复杂度分析就完整了考试中属于能拿大部分甚至满分的答案。4.3 用复杂度分析反向验证答案复杂度是最好的自查工具写完代码后不写复杂度直接进入下一题是很多人的习惯但这个习惯会埋下隐患。复杂度不只是给阅卷老师看的它就是你的自检工具。假如你设计的是一个双层循环嵌套的算法却在复杂度里写 O(n)那一定是循环结构没分析清楚反过来如果你打算用暴力枚举的方式解一道题写完发现复杂度是 O(n²)而题目的数据范围提示你该用 O(n log n)这时你会立刻意识到自己的思路有问题。备考阶段建议养成两个习惯。第一每次写完代码在末尾强制写一行时间复杂度 XXX空间复杂度 XXX写不出来就说明这个算法还没被自己真正理解。第二把常用算法的复杂度整理成一张速查表放在总结的附录区包括各种排序的时间空间复杂度、图遍历的 O(ne)、Dijkstra 的 O(n²) 等没事翻一眼。提示复杂度分析不是精确数学证明考研答题只需要给对大阶即可。O(2n) 写成 O(n)O(n² 1) 写成 O(n²)阅卷和自检都按这个口径走。很多真题的尽可能高效其实就是在暗示复杂度阈值。尽可能高效通常指时间上要优于暴力枚举空间上不要用 O(n²) 的辅助数组。如果题目明说要求时间 O(n)、空间 O(1)那基本就是在考某个固定套路例如链表的快慢指针或树的遍历。复杂度分析熟练之后看题和选路都会快很多。5. 避坑考研数据结构刷题最容易翻车的 5 个地方刷题踩过的坑比背过的模板记忆更深。这一章整理的是复习过程中最常见的五个翻车点每一条都是很多人反复栽过的真实场景按现象、原因、解决来说明。5.1 链表题没判空直接对 NULL 取 next现象平时在编译器里练习时没出问题一到白纸手写就漏掉空链表判断写完还觉得自己逻辑没问题考后对答案才发现边界条件全错。原因在纸上写代码时脑内推演只走了链表非空这一条正常路径空链表和单结点链表的情况压根没进入意识。链表的陷阱恰恰在这些边界空表的 L-next 是 NULL单结点遍历时 pre 和 p 的移动方式会变。解决写完链表代码立刻默念三个边界条件——空链表、单结点链表、删除或插入位置在头部和尾部。每个条件在草稿纸上画一个小图对照代码走一遍循环。我一般会在总结的易错点区写一行字开写前先花 30 秒确认链表是否带头结点、是否可能为空。5.2 只背递归遍历非递归版本写不出来现象复习时觉得递归遍历已经滚瓜烂熟考试题目要求写出非递归算法时直接卡住或者写出来的代码逻辑混乱。原因递归和非递归在思路上是一回事但代码结构完全不同。非递归靠显式栈模拟要在压栈、弹栈、转向三个动作之间切换这个操作序列不默写几遍根本记不住。很多人以为记住访问顺序就行忽略了栈怎么操作才是真正的考点。解决三个遍历的非递归版本各手写三遍要求 20 分钟内默写出中序非递归。第一遍多半卡在循环条件第二遍卡在访问时机第三遍就能形成肌肉记忆。备考后期每天抽一个模板默写比看十遍书有用。5.3 快速排序的 partition 函数写反了现象排序思想讲得头头是道一写代码要么循环条件写错要么交换位置不对最后 partition 返回的不是基准元素的正确下标。原因考研对排序的平常考法多是手动模拟过程导致很多人从没真正手写过快速排序完整代码。但 408 曾考过基于快速排序思想求第 k 小元素这直接要用到 partition是丢分重灾区。解决把教材上的 partition 抄两遍再默写两遍特别注意 while 嵌套循环里low high的条件以及先从哪边扫描。这个顺序必须固定下来——从右往左找比基准小的再从左往右找比基准大的顺序反了分区结果必错。5.4 KMP 的 next 数组推导和考试题的版本对不上现象自己练习时 next 数组算得熟练考场上却和标准答案差一位甚至整套推导全部错位。原因KMP 的 next 数组存在 0 下标和 1 下标两个版本有些教材 next[1]0有些 next[0]-1还有资料用 nextval。不同版本就差一位换算拿自己的版本去套卷子的版本自然从头错到尾。这个问题被很多人形容为 KMP 的玄学其实只是版本没对齐。解决翻目标院校近三年的真题答案确认用的是哪个版本如果找不到就把两个版本的代码都写一遍分清下标起点。我自己在总结上专门用醒目标注写了条提示先看题干下标起点再做 next 数组。考场上这一眼能省下大把时间。5.5 只动眼不动手刷题全靠看现象每天看了大量题解觉得都懂了一模拟手写就卡壳经常写了开头忘了结尾。原因算法题的成绩来自手写能力阅读理解不等于输出能力。看了十道题和手写两道题对答题状态的提升完全不同。平时在 IDE 里调试能过是因为有编译器和报错信息在兜底考场上只剩下你一个人。解决所有算法题练习用手写方式完成在纸上写完整代码一遍写不好就再来一遍重点练变量声明、循环边界、函数返回三个位置。手写 20 道真题之后对代码哪些地方容易出错会形成一种直觉反应这种反应比任何模板都可靠。6. 最后两周的冲刺把 36 页从资料变成答题直觉到了冲刺阶段复习资料不应该是厚厚的书本而应该是查漏补缺的字典。36 页总结的正确用法是在最后两周里一遍又一遍地过越翻越薄最后变成几页关键内容。先做一轮倒背式快速过页第一天花两小时把 36 页从头翻到尾不纠结细节只标注完全没问题、基本会但容易错、完全不会三档。第二天只刷后两档的页。第三天把第三档页面重新抄一遍不是抄原文而是用自己的话把考点和模板压缩成几条要点。这轮之后 36 页会被压缩成 8 到 10 页真正有效的内容后面就只翻这些。然后是限时手写模拟每天下午固定 45 分钟随机抽两道代码题手写在空白纸上不查资料不看答案。写完对照 36 页里的模板用红笔标出差异。注意这里不是判断对错而是判断偏差——代码写错的概率很低但写着写着漏一个 return、丢一个边界判断这种问题只有白纸模拟才能暴露。最后做一张复杂度自查表放在总结附录区。我习惯用的工具表格是算法/操作时间复杂度空间复杂度链表按位查找O(n)O(1)快速排序O(n log n)O(log n)归并排序O(n log n)O(n)堆排序O(n log n)O(1)二叉树遍历O(n)O(1)非递归辅助栈另算图的 DFS/BFSO(ne)O(n)Dijkstra邻接矩阵O(n²)O(n)这张表的作用不是让你背复杂度数字而是在考场上判断自己的解法是否踩在题目暗示的复杂度范围里。题目说尽可能高效时优先考虑 O(n) 或 O(n log n) 的已知套路题目如果给了严格的时间限制暴力枚举的复杂度往往一眼就能排除。还有一件自己做过的小事值得分享把 36 页中自己返工最多的一页单独复印出来贴在书桌边每天出门前看一遍。我当年那页是 KMP 的 next 数组坚持了一周后考场上几乎是靠着肌肉记忆直接写出来的。冲刺阶段的复习不是去学新东西而是把已经会的练到不会错。希望这篇笔记能帮你在最后阶段把 36 页用出最大的价值。本文还有配套的精品资源点击获取