简介一份面向计算机考研408与893自命题考生的数据结构算法题总结36页PDF浓缩了数组、链表、栈、队列、二叉树等核心结构的常考题型涵盖合并排序数组、约瑟夫环、栈实现队列、最小栈、循环队列、链表删除/反转/环入口、二叉树前中后序与层序遍历、排序与Top K问题、双指针、二分查找、贪心及动态规划等机试高频题。每个题目给出C语言实现与关键思路适合对照练习和快速复盘。内容按数组合并排序、链表操作、二叉树遍历、排序算法、递归与非递归、图遍历等模块清晰编排基本覆盖考研算法题的主要出题方向代码风格简洁便于直接理解运行逻辑。资源本身是单个PDF文件共36页约1.67MB方便在手机、平板或电脑上阅读也适合打印成纸质版做冲刺笔记。目前已有1681人学习下载对于正在刷leetcode或准备自命题机试的同学是一份高性价比的浓缩复习资料能节省大量整理时间并快速定位薄弱环节。1. 考研数据结构算法题总结36页拿到手先看什么九月中旬我开始刷408真题发现最耽误时间的不是选择题而是每年最后那道15分的代码大题。当时手上资料不少但没一份能直接告诉我“考场上怎样把代码写到不丢分”。《考研数据结构算法题总结36页893408》是我复习后期翻得最勤的一份资料它把两套考纲交叉后的高频算法点按题型压成36页每一页都是“题干思路代码复杂度”四件套。适合两类人跨考、手写代码心里没底的人复习时间紧、想快速找回手感的人。先说结论它替代不了真题但能帮你把代码题从“玄学”变成“公式”。2. 先拆408和893的命题差异这份总结按什么逻辑编排2.1 408统考算法题的命题边界两道大题、复杂度红线408统考的数据结构大约占45分代码题一般出现在综合应用题里通常是最后一道15分的大题偶尔前面还会有一个小的算法设计填空。题目风格是“给你一个场景写核心代码并分析复杂度”比如给定一个链表要求O(n)时间删除倒数第K个结点。这种题LeetCode上有原型但考场上没有测试数据阅卷只看三段逻辑是否完整、边界是否覆盖、复杂度是否达标。复杂度是408明确会关注的一条线。评分标准里经常写着“时间复杂度O(n)得满分O(n^2)给一半”。所以这份总结里每道题都单独标注了时间复杂度和空间复杂度我当时的做法是每页先看复杂度要求再看题目描述最后才对思路。如果你和我一样是从代码量开始复习的建议把这个顺序反过来先逼自己养成看复杂度的习惯。提示408代码题的复杂度红线一般是O(n)或O(n log n)。如果题目没给数据规模默认不能出现双重循环。从覆盖内容看36页对应的是考研数据结构的七个章节线性表、栈与队列、串、树与二叉树、图、查找、排序。看起来和各教材目录一样但它的编排不是按章节而是按“考察方式”走。比如链表和数组被放在同一组因为它们经常以相同题型出现图的遍历和树的遍历也归在一起因为套路一样。这是这份资料和教材目录最大的区别教材按知识结构组织它按答题套路组织。2.2 893自命题的差异偏基础还是偏综合如果说408是“全国统一难度”893就是“每个学校各自出题”。同样是考数据结构算法题A学校可能出三道手写代码B学校可能出五个算法填空C学校甚至直接从教材习题里挑原题。刷多了893真题会发现自命题普遍比408更贴近教材也更容易出现“直接背模板就能写”的题。这里有两个常见误区一是认为自命题比408简单随便刷刷就行二是把LeetCode的中等难题刷遍了回来自命题简单题却写不顺。真实的893命题有两个明显特点第一题目描述通常很长会给你完整的结构体定义和函数签名实际上是把代码框架都搭好了你要填的是核心逻辑第二它允许的复杂度往往比408宽松很多题O(n^2)就能拿满分前提是你必须老老实实把代码写完整。对比维度408统考893自命题题目来源改编经典算法偏应用场景教材习题原题居多偏基础代码量一道大题15分代码量中等3~5道小题单题代码量小复杂度要求严格O(n)/O(n log n)相对宽松O(n^2)常可接受判分重点思路复杂度边界代码完整度能否运行复习策略练变体题背教材代码模板这张对比表是我复习时自己整理的后来对照这份总结的目录发现它对两种考试的处理方式不一样通用题型会标注“408/893均适用”偏教材原型的题会单独标“893常考”偏场景改编的题标“408常考”。这个细节帮我省了很多时间因为自命题复习到后期我基本只挑“893常考”的页面过408的大题再单独练变体。2.3 36页总结怎么用一轮复习和冲刺阶段的不同打开方式同样是36页一轮复习和考前两周的用法完全不同。我第一遍复习时是把这个总结当题库用的先看题目不看答案在草稿纸上写核心代码再和答案对照。这个过程非常费时间一页可能花掉四十分钟但收获也是最大的因为代码题只有自己写过一遍才算真的会了。到了十月下旬时间紧起来我换了一种方式每天早中晚各翻十页只读“题干复杂度”两行然后在脑子里过一遍解题步骤最后只看代码里的关键三行。这个阶段的目的不是写代码而是保持对题型的敏感度。真正的冲刺阶段我反而把总结放回抽屉改成用真题模拟考场每套真题做完之后再翻总结看自己哪一类题失分再回到对应页面去补。阶段时间建议打开方式目标一轮复习910月先做题再看答案建立手写能力强化阶段1011月只看题干想思路训练题型识别冲刺阶段考前两周真题为主总结补漏保持手感和节奏我特别想提醒的一点是不要把这份总结当成“背多分”资料从头背到尾。它36页按题型压缩过但仍然需要你动笔。我在第二轮曾经偷懒只看答案结果模拟考时连单链表反转都写得磕磕绊绊。从那以后我给自己定了个规矩看一页总结至少要在白纸上写十行代码才能翻下一页不管代码是不是和答案一致。3. 字符串与数组高频题复现从暴力枚举到KMP3.1 暴力枚举不是笨办法先写对然后再优化考场上最容易出现的情况是拿到题就想最优解想了十分钟没思路最后连暴力解也没时间写。暴力枚举在算法题里听起来不高级但它是手写代码的基本功。一个不超时的暴力解配合清晰的注释在408里至少能拿六成分数在893自命题里甚至能拿满分因为很多自命题根本没限制复杂度。以LeetCode上最经典的“两数之和”为例题目给一个数组和一个目标值要求返回两个下标。很多人的第一反应是哈希表但考场上如果一时间想不起哈希表怎么写暴力枚举完全够用def two_sum(nums, target): # 暴力枚举固定一个数往后找补数 n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这段代码的逻辑很简单外层循环固定i内层循环从i1开始扫避免同一对元素被重复统计。时间复杂度O(n^2)空间复杂度O(1)。两个参数里nums是输入数组target是目标值返回的是下标列表。注意内层循环起点是i1而不是0这是最容易写错的地方写成0会多算很多无效pair极端情况下会出现自身加自身等于target的错误。如果题目要求O(n)再往哈希表版本升级def two_sum_hash(nums, target): seen {} # 值 - 下标的映射 for i, x in enumerate(nums): need target - x if need in seen: return [seen[need], i] seen[x] i return []这个思路的关键是“边查边存”当前元素查需要的补数是否已经出现过再把当前元素存进哈希表。这样每个元素只扫一遍时空复杂度都是O(n)。考研答题时建议把哈希表版本的注释也写上尤其是“need target - x”这一步阅卷人一眼就能看出你思路清楚。我在复习中发现的规律是数组类算法题暴力解往往是理解题意的第一层最优解是第二层。资料里数组部分的题目基本都给了两层答案我先抄一遍暴力解再抄一遍优化解对比两个版本的差异这样比直接背最优解要牢得多。3.2 KMP的核心next数组和退化场景KMP是字符串匹配里的高频考点408和893都可能直接考“写出next数组”或者“用KMP算法求匹配位置”。很多复习到KMP就放弃的人其实是死在了next数组的求法上因为不同教材对next的定义不一样有的从0开始有的从1开始有的用-1手写的时候一混就全错了。我用的版本是考研最常用的next数组定义next[0] -1-1表示主串指针也要后移next[1] 0因为第一个字符失配时没有前缀可以回退。求next的代码写下来是这样// p: 模式串, next: 长度为模式串长度的数组 void get_next(char *p, int *next) { int i 0, j -1; next[0] -1; while (p[i] ! \0) { if (j -1 || p[i] p[j]) { i; j; next[i] j; // 当前前缀长度就是i失配时要回退的位置 } else { j next[j]; // 不匹配回退到更短的前缀 } } }这里最核心的是else分支里的“j next[j]”。很多初学的人在这个位置写成了“j 0”表面上看也能跑通部分用例但遇到真回退时会漏掉已有匹配。i是当前正在比较的主串位置j是模式串中已匹配的长度。每轮循环要么i和j同时前进要么j回退到next数组指向前的位置这样保证i不回头整个匹配过程线性。理解完next数组KMP匹配本身反而简单主串和模式串一起走失配时模式串跳到next[j]主串不回溯。408一般不要求写完整的KMP匹配函数更多是给你一个模式串让你手算next数组或者给你next数组让你分析匹配过程。我在资料里看到KMP这部分时特别注意了它给的“退化场景”如果模式串全是同一个字符比如“aaaa”next数组是递增的但匹配时的比较次数依然不会退回O(mn)这就是KMP的价值所在。3.3 双端队列与单调队列小众但能救场双端队列在数据结构教材里是一个线性表考点但代码题里它经常以“单调队列”的形式出现。最经典的场景是滑动窗口最大值给一个数组和一个窗口大小k求窗口从左滑到右每个位置的最大值。暴力做法是每个窗口扫一遍时间复杂度O(nk)用双端队列可以压到O(n)。from collections import deque def max_sliding_window(nums, k): q deque() # 存下标下标对应的值从队头到队尾递减 res [] for i, x in enumerate(nums): if q and q[0] i - k: q.popleft() # 队头下标已经滑出窗口直接移除 while q and nums[q[-1]] x: q.pop() # 队尾元素不大于x它再也不会成为最大值 q.append(i) # 当前下标入队 if i k - 1: res.append(nums[q[0]]) # 队头就是当前窗口最大值 return res这段代码的注释已经把每个分支都说明了。队头存的是窗口内最大值的下标队尾存的是有可能成为最大值的候选下标。第一次写这个题的人通常会在“队尾弹出”这一步犹豫拿不定该弹出小于还是小于等于当前值的元素。我一般建议弹出“不大于当前值”的所有下标也就是用这样重复元素也能正确处理。在自命题考试里如果考纲里出现了双端队列滑动窗口最大值几乎就是必背模板。即使是408没考过这个场景它也是一种通用思路用双端队列维护一个单调序列可以解决很多“找区间最值”的问题比如求每个长度为k的子数组最小值、求滑动窗口中的中位数等等。把这些场景在总结里记在一起比孤立记“双端队列”四个字有用得多。4. 树与图算法题怎么练排序、遍历与递归返回值的取舍4.1 冒泡排序与堆排序408爱考过程893爱考代码排序是考研数据结构算法题里性价比最高的一块因为它既容易出大题也容易出选择题。408和893对排序的考法有明显差异408喜欢考“过程”比如给你一个初始序列让你写出冒泡排序第一趟和第二趟之后的结果或者问比较次数893则更喜欢直接让你写出完整排序函数甚至给你结构体数组按成绩字段排序。以冒泡排序为例标准代码几乎每个考场都会用到def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a这里的swapped标志位是区分“标准冒泡”和“优化冒泡”的关键它的作用是在某一趟没有任何交换发生时提前终止。对408的选择题来说这个标志位会影响“最少趟数”的结论对893的手写题来说写上它能体现你对内层循环边界的理解。注意内层循环的范围是n-1-i因为每一趟结束后最大的i1个元素已经沉到底部不需要再参与比较。堆排序在考研代码题里出现的频率更高因为它的过程更复杂适合出成“手写建堆”或“手写调整”。核心是堆调整函数def heapify(a, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest ! i: a[i], a[largest] a[largest], a[i] heapify(a, n, largest) def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): heapify(a, n, i) # 从最后一个非叶子节点开始建堆 for i in range(n - 1, 0, -1): a[0], a[i] a[i], a[0] # 堆顶与末尾交换 heapify(a, i, 0) # 新的堆顶调整堆大小减1 return a我写这段代码时最容易错的是“建堆循环的范围”。n//2-1是最后一个非叶子结点的下标从它开始往前逐个调整才能保证整个数组成为大根堆如果从0开始往下调会出现局部有序但全局没排好的情况。交换a[0]和a[i]之后堆的有效长度变成i所以第二次heapify传的是i而不是n。堆排序时间复杂度稳定在O(n log n)空间复杂度O(1)但要注意它是不稳定排序408选择题经常拿这个当考点。4.2 图的遍历邻接表与邻接矩阵的取舍图的数据结构题在408里一般以应用题出现在893里则以手写遍历居多。最常见的两个考点是深度优先搜索和广度优先搜索。实现方式取决于存储结构邻接矩阵写起来最简单查两点是否相邻是O(1)但遍历所有邻接点要扫一整行邻接表写起来要处理指针或链表但遍历时只访问实际存在的边复杂度是O(VE)。存储结构判断两顶点是否相邻遍历顶点v的邻接点适用场景邻接矩阵O(1)O(n)稠密图、选择题判断邻接表O(degree(v))O(degree(v))稀疏图、手写遍历代码对代码题来说我更推荐用邻接表理由其实就一句话代码量不大复杂度又好写清楚。一个简单的DFS如下def dfs(adj, visited, u): # adj: 邻接表visited: 布尔数组u: 当前顶点编号 visited[u] True print(u, end ) for v in adj[u]: if not visited[v]: dfs(adj, visited, v)这段代码的逻辑是教科书标准版但有一个细节常被忽略visited[u] True必须放在递归调用之前不能放在循环之后。如果你先遍历邻接点再标记当前点同一层里会出现大量重复打印甚至因为相互引用导致递归无法终止。递归结束后不需要还原visited因为图遍历要求每个顶点只访问一次只有求所有路径时才需要回溯还原那是另一类题。BFS的代码和DFS长得像区别只是把系统栈换成显式队列from collections import deque def bfs(adj, visited, start): q deque([start]) visited[start] True while q: u q.popleft() print(u, end ) for v in adj[u]: if not visited[v]: visited[v] True q.append(v)这里最容易踩坑的是入队时就要立刻标记visited。如果你等出队时再标记同一个节点会被多个邻居重复入队在小规模数据上可能看不出问题但在有环的图里会直接死循环。我把“标记”和“入队”视为一个原子操作写BFS就不会乱。4.3 树的递归返回值设计决定成败树的算法题是自命题的最爱因为它代码短、逻辑清晰、适合手写。最常见的是求树的高度、判断平衡二叉树、求直径、最近公共祖先。这类题统一用递归解决关键是设计好递归函数的“返回值”。我见过很多翻车代码不是递归写不出来而是返回值定义模糊导致上层调用没法判断结果。先看最简单的求二叉树高度def tree_height(root): if not root: return 0 left_h tree_height(root.left) right_h tree_height(root.right) return max(left_h, right_h) 1这里的返回值定义很明确返回以root为根的子树高度。空节点高度是0叶子节点高度是1。递归过程是自底向上的先问左子树多高再问右子树多高取较大值加1。这种设计不需要额外参数也天然处理了只有左子树或只有右子树的非平衡情况。如果题目升级成“判断是否是平衡二叉树”就不能只返回高度了。我常用的做法是让递归函数返回两个信息——子树高度和是否平衡用一个特殊值表示“不平衡”def is_balanced(root): def check(node): if not node: return 0 lh check(node.left) if lh -1: return -1 rh check(node.right) if rh -1: return -1 if abs(lh - rh) 1: return -1 # -1 表示不满足平衡条件 return max(lh, rh) 1 return check(root) ! -1这个版本的返回值设计是正常情况返回子树高度一旦发现左右子树高度差超过1立即返回-1让上层递归剪枝。注意两个if的判断顺序先检查左子树是否不平衡再看右子树这样能提前结束递归避免做无意义的深度累加。如果只按“算高度再单独判断”的写法每个节点会被重复访问多次时间复杂度会从O(n)退化到O(n^2)。树的递归题我总结出一个通用流程第一步定义返回值的含义第二步确定空节点返回值第三步想清楚当前节点如何组合子节点的返回值第四步写边界。36页总结里树的题目其实都是这四步区别只在第3步的组合方式不同。5. 算法题刷题避坑五个高频翻车现场与修复方案5.1 样例过了交上去全错现象做模拟题或自命题机试时题目给出的示例输入跑一遍完全正确自己额外造几组数据就崩了。比如链表题示例是1-2-3-4删除倒数第2个节点输出1-2-4没问题换成5个节点的链表或者链表只有1个节点程序直接报错或返回空。原因只按示例数据写代码没有覆盖边界条件。考研手写代码虽然没有测试用例阅卷时会按步骤给分边界处理是评分表里明确的一档缺失会整体降档。解决写任何题之前先问自己三件事输入为空怎么处理只有一个元素怎么处理重复元素怎么处理把这三个分支在代码里显式写出来即使不完整阅卷人也能看到你在考虑边界。我后来给自己定的习惯是每写一个函数至少测三组数据正常数据、最小数据、重复数据。这里尤其要提链表类题目单链表删除的代码很容易在只有一个节点时越界。我考前专门把“空链表、单节点、头节点被删”三种情况抄在总结的空白页上每天看一遍后来再遇到删除类题目基本能条件反射地补上判断。5.2 KMP的next数组背了又忘手写时死循环现象考场上写get_nextwhile循环里忘记让i前进代码一跑就死循环或者next数组结果跟标准答案对不上。原因next数组的标准代码依赖“j回退到next[j]”这个动作死循环通常是因为把else分支的“j next[j]”写成“j 0”在特定模式串下j会一直停在0i永远不动。解决先不看代码自己手推一次next数组再对照。推荐记两个锚点next[0]-1next[1]0。写代码时盯着else分支不匹配就必须让j回退回退不出去就把jnext[j]打印出来看确认j在递减。这个坑我在模拟考翻过两次后来每次写KMP都会先画一遍模式串的前后缀表画完再写代码基本不会再错。如果你用的是从1开始的教材定义那就整份资料都用那一套定义千万别一套题里混用两种next。阅卷人按答案步骤给分定义混用会导致后面的匹配过程完全对不上丢分会非常可惜。5.3 树的递归栈溢出或死循环现象代码看起来没问题但遇到深度较大的树时程序崩溃或者递归结束后输出重复结果。原因递归终止条件写错是最大隐患。常见错误是“只判空节点返回0但不判当前节点是否为空”导致空节点的left被访问另一个错误是递归函数里重复调用自身但方向不对比如求树高度时把左子树的递归写在右子树的返回值里导致无限递归。解决树递归的终止条件必须在函数第一行先判空再访问属性。如果发现死循环优先检查是不是在递归入口就访问了node.left而没有判node本身为空。我自己的检查方法是把递归函数的第一行固定写成“if not node: return 0”形成肌肉记忆写树题就不再翻车。更深一层的问题是“递归返回值类型”没想清楚。树的高度返回int判断存在性返回bool这两个东西不能用同一个模板硬套。我在资料上看到树的章节特意把两类题目分开排版就是为了避免把返回值的语义搞混。5.4 时间复杂度被扣分只算最好情况现象自认为算法复杂度达标结果被阅卷或面试官问住因为写的代码在“最坏情况”下反而退化到O(n^2)。比如哈希表扩容分析或者快速排序在基本有序时退化成O(n^2)。原因默认输入是随机的没考虑极端输入快排的哨兵取第一个元素遇到降序数组每次只能排一个元素。解决分析复杂度时一律按最坏情况写出来快排写“平均O(n log n)最坏O(n^2)”。408评分看重复杂度的分析过程哪怕代码里用的堆排序只要把复杂度边界写清楚至少能拿步骤分。我在总结里看到快排那页旁边手写了一行“哨兵取中间位置”就是用来提醒自己最坏情况的来源。更实用的做法是给代码里的关键循环打标注。比如“for i in range(n): for j in range(i1,n):” 直接在注释后写“O(n^2)”这样一眼就能看到哪一段是复杂度瓶颈。阅卷人不需要你去解释标注本身就是得分点。5.5 盲目刷LeetCode自命题反而写不顺现象LeetCode刷了几百题模拟893自命题时遇到课本原题却无从下手或者写出来的答案不符合题目要求的函数签名。原因LeetCode强调的是最优解、异常输入、极端用例所有代码都要在编译器里跑考研手写代码更强调代码可读性、结构体定义匹配、注释清晰。两者评分标准不一样。解决分清两者的时间分配。我在冲刺期把LeetCode当成“锻炼思路”的工具刷题时只看题解思路不在编辑器里调一晚上手写代码用真题和总结里的题目练要求自己能在十五分钟内写完一题不能改不能重跑。真正上考场时代码是直接写在答题纸上的没有编译器帮你检查平时训练就应该闭卷写。这里还有一个小技巧893自命题如果给了结构体定义答题时先原样抄一遍结构体再写函数体。很多学校是按“结构体定义是否正确”给分的抄错一个字段名就可能丢掉一整档分。我见过好几个同学在自命题考场上因为没写结构体代码逻辑全对但只拿了一半分非常冤。6. 最后两周的收尾技巧复杂度口算与答题模板化6.1 一个数快速判断你的算法能不能过考研没有在线评测但复杂度分析要写在答题纸上。我有个笨但实用的方法先看题目是否给数据规模给了就估算一个数量级然后对照下面这张表判断你的方案是否在安全线内。数据规模n可用复杂度典型算法n 10O(n!)全排列暴力n 20O(2^n)状态压缩、剪枝搜索n 10^3O(n^2)冒泡、暴力枚举n 10^5O(n log n)快排、堆排、KMPn 10^7O(n)双指针、哈希表更关键的是408代码题一般不会给你特别大的n它的目的是让你写出“复杂度正确”的算法而不是真去跑数据。所以答题纸上写的复杂度分析必须和你的代码实现完全对应。哪怕你实际用了O(n^2)的暴力解你写“时间复杂度O(n^2)”也比写了O(n)却实现得不对要好。6.2 三个背下来就能救场的模板最后两周我不再追求新题只过三个高频模板双指针判断回文、单链表反转、二叉树递归遍历。这三个模板覆盖了数组、链表、树三类最常见的代码题。# 双指针判断回文背下来的模板 left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True# 单链表反转模板 def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev每个模板都对应一类题型。双指针是“一对多”题型的基础还能推广到有序数组的两数之和、删除重复元素单链表反转是所有链表题的基础很多链表大题的核心步骤就是在局部做反转二叉树递归模板其实就是前面写的判空、递归左右孩子、组合返回值那三步。把这三个模板写在总结第1页每天默写一遍比刷十道LeetCode更稳。6.3 考场上最后五分钟查什么我模拟考时养成了一个习惯代码写完后不急着做下一题回头检查三个位置——递归的终止条件有没有写在第一行循环的边界是小于还是小于等于有没有返回空值。这三个位置占了代码题80%的低级错误。从那以后我每次模拟考都强制走一遍这三查自命题考试的最后一道代码题基本能在十分钟内干干净净写完。这份36页的总结不一定完美但它帮我稳住了最不踏实的一块希望帮到你。本文还有配套的精品资源点击获取