考研数据结构算法题总结36页：893+408可默写代码模板库

简介这份PDF资料面向备战计算机考研数据结构与算法的考生尤其适合同时准备408统考与893自命题的读者用于系统梳理高频算法题型与解题模板。内容围绕数组、链表、栈、队列、二叉树等核心结构展开覆盖合并排序数组、链表删除与环检测、栈实现队列、最小栈、二叉树各类遍历与构建、有序数组转二叉搜索树等经典题目并延伸至冒泡、快排、堆排、归并、基数等排序算法以及双指针、二分查找、贪心、动态规划、DFS等编程技巧还包含约瑟夫环、Top K、背包问题等杂题思路。资源共1个PDF文件约1.67MB篇幅36页目录按数据结构与算法模块编排便于按专题查阅与复盘。目前已有1683人学习下载适合作为冲刺阶段的题型速查与代码模板参考帮助读者在有限时间内抓住排序、树遍历、递归与非递归等重点提升解题效率与代码实现能力。1. 考研数据结构算法题总结36页893408一份能直接背的代码模板库到底长什么样如果你正在准备 408 或者 893 的数据结构大概率经历过这个阶段真题里的算法题翻来覆去就那几类但每次自己写都要从头推边界考场上时间根本不够用。那份流传的「36 页总结」之所以被反复转手核心不是它押中了题而是它把线性表、树、图、查找排序里最高频的算法骨架压缩成了可背诵、可默写的模板。它解决的是「知道思路但写不完整」这个最要命的问题——适合已经过了一遍教材、需要把算法题从「会想」变成「能写对」的考生。这一章先把这份总结的定位讲清楚后面几章拆它的组织逻辑、默写方法、参数边界和常见翻车点。2. 36 页总结的骨架893 和 408 到底共用哪几类算法模板2.1 为什么这两套卷子的算法题可以合并整理893 和 408 在数据结构算法题上的考查范围高度重叠差异主要在题型配比和分值分布而不是知识点本身。408 的算法题通常是一道大题偏重「设计算法 分析复杂度」代码量在 15 到 30 行893 的算法题可能拆成多道小题单题代码量更短但覆盖面更广链表、树、图、排序都可能各出一道。合并整理的价值在于你不需要维护两套模板。把两套卷子近十年的算法题按数据结构类型归类会发现重复出现的骨架就那么几个——链表反转与合并、二叉树遍历的变体、图的 BFS/DFS 框架、快排和归并的分区与合并逻辑、二分查找的边界处理。36 页的容量刚好够把这些骨架各写一遍标准版再附上两到三个变体。我一般建议按「数据结构类型」而不是「年份」来组织复习。按年份刷题的问题是同一类算法隔几个月才遇到一次每次都要重新回忆按类型整理同一类算法连续写五道变体肌肉记忆才建立得起来。2.2 36 页的典型目录结构拆解一份能用的算法总结目录必须能让你在 30 秒内定位到目标模板。常见的组织方式是按数据结构分章每章内部再按「基础操作 → 真题变体 → 边界处理」三层展开。下面这张表是我整理时用的分类框架你可以直接对照自己的笔记检查有没有漏项。模块核心模板数高频变体方向建议默写遍数线性表顺序链式6反转、合并、找中点、删重复5栈与队列4括号匹配、单调栈、循环队列3二叉树8遍历、深度、路径、BST 操作6图5BFS/DFS、拓扑排序、最短路4查找4二分变体、哈希冲突处理4排序6快排分区、归并合并、堆调整5这张表的关键不是数字而是「高频变体方向」那一列。很多人背了基础模板但真题一变形就卡住原因是没把变体方向单独拎出来练。比如链表的「找中点」基础版是快慢指针变体可能是「找倒数第 k 个」或者「判断是否有环并找入口」骨架相同但边界条件不同。2.3 从真题反推模板怎么判断哪些算法值得背不是所有算法都值得做成模板。判断标准有三个第一近五年出现过两次以上第二代码结构有固定骨架换汤不换药第三边界条件容易出错不背容易翻车。以二叉树为例「非递归中序遍历」值得背因为它的栈操作逻辑固定手写时容易在循环条件上出错而「计算二叉树宽度」这种题思路简单但实现依赖具体场景背模板的收益就不大。具体操作上你可以拿近五年的真题把每道算法题的核心操作抽出来写成一句话。比如「在有序数组中找第一个大于目标值的元素位置」核心操作是「二分查找的左边界变体」。把这类描述归类出现频率最高的那几类就是你的模板清单。# 二分查找左边界模板找第一个 target 的位置 def lower_bound(nums, target): left, right 0, len(nums) # 注意 right 取 len 而不是 len-1 while left right: # 循环条件是 而不是 mid left (right - left) // 2 if nums[mid] target: left mid 1 # 严格小于才右移 else: right mid # 大于等于都收缩右边界 return left # 返回 left 即第一个 target 的位置这段代码的逻辑说明right初始化为len(nums)而不是len(nums)-1是因为搜索区间定义为左闭右开[left, right)。循环条件用left right而非left right因为当left right时区间为空。nums[mid] target时left mid 1nums[mid] target时right mid这样最终left指向的就是第一个大于等于目标值的位置。参数上nums必须是有序数组target是目标值返回值在[0, len(nums)]范围内等于len(nums)表示所有元素都小于目标值。这个模板值得背的原因是它的变体覆盖了「找第一个等于」「找最后一个等于」「找插入位置」等至少四种考法而每次手写都容易在right的初始值和循环条件上翻车。3. 把 36 页压缩成可默写的代码块分模块默写方法与参数边界3.1 线性表链表操作的三个必背骨架链表题在 408 和 893 里都是高频考点但很多人写链表代码时习惯在纸上画图推考场上时间不够。我的做法是把三个骨架背到条件反射反转、合并、找中点。反转链表的迭代版是基础中的基础但要注意头结点的处理。合并两个有序链表的关键是虚拟头结点的使用避免对空链表的单独判断。找中点用快慢指针慢指针走一步快指针走两步快指针到尾时慢指针正好在中点。# 链表反转迭代版 def reverse_list(head): prev None curr head while curr: nxt curr.next # 先保存下一个节点 curr.next prev # 反转指针 prev curr # prev 前移 curr nxt # curr 前移 return prev # prev 最终指向新头节点 # 合并两个有序链表虚拟头结点 def merge_two_lists(l1, l2): dummy ListNode(0) # 虚拟头结点避免处理空链表 tail dummy while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 if l1 else l2 # 接上剩余部分 return dummy.next # 找链表中点快慢指针 def find_middle(head): slow fast head while fast and fast.next: # fast.next 判空防止越界 slow slow.next fast fast.next.next return slow # 偶数个节点时返回靠右的中点逻辑说明反转链表的循环不变式是「prev 指向已反转部分的头curr 指向未处理部分的头」。合并链表的虚拟头结点技巧可以把「结果链表为空」和「结果链表非空」两种情况统一处理。找中点的while fast and fast.next条件缺一不可只写fast.next会在偶数节点时越界。参数边界方面反转链表传入None时直接返回None因为while curr不会执行合并链表传入两个None时返回dummy.next即None找中点传入单节点时返回该节点本身。3.2 二叉树递归与非递归的转换套路二叉树的递归写法几乎不用背因为结构太固定。真正需要背的是非递归写法尤其是中序和后续遍历因为栈的操作顺序容易搞混。非递归中序遍历的核心逻辑是「一路向左入栈弹出时访问并转向右子树」。非递归后序遍历有两种写法一种是双栈法一种是单栈加标记法。双栈法更好记先按「根右左」入栈再反转输出就是「左右根」。# 非递归中序遍历 def inorder_traversal(root): stack, result [], [] curr root while curr or stack: while curr: # 一路向左 stack.append(curr) curr curr.left curr stack.pop() # 弹出栈顶 result.append(curr.val) curr curr.right # 转向右子树 return result # 非递归后序遍历双栈法 def postorder_traversal(root): if not root: return [] stack1, stack2 [root], [] while stack1: node stack1.pop() stack2.append(node) if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) return [node.val for node in reversed(stack2)]逻辑说明中序遍历的while curr or stack条件保证「当前节点为空但栈不为空」时继续处理。后序遍历双栈法的巧妙之处在于stack1按「根右左」顺序弹出压入stack2后反转就是「左右根」。参数上空树传入None时中序返回空列表后序在函数开头直接返回空列表。3.3 图与排序BFS/DFS 框架和快排分区的固定写法图的 BFS 和 DFS 框架几乎可以原样套用到所有题上区别只在访问标记和入队/入栈时机。BFS 用队列DFS 用栈或递归。拓扑排序本质是 BFS 的变体只是入队条件从「未访问」变成「入度为 0」。快排的分区函数是排序模块里最值得背的因为它的边界处理最容易出错。Lomuto 分区方案用最后一个元素作基准代码简洁但交换次数多Hoare 分区方案用首元素作基准交换次数少但边界更难写对。考试里建议用 Lomuto因为不容易写错。# BFS 框架 from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # 快排 Lomuto 分区 def partition(nums, low, high): pivot nums[high] # 选最后一个元素作基准 i low - 1 # i 指向小于区的最后一个元素 for j in range(low, high): if nums[j] pivot: i 1 nums[i], nums[j] nums[j], nums[i] nums[i1], nums[high] nums[high], nums[i1] return i 1 # 返回基准最终位置逻辑说明BFS 的visited在入队时就标记而不是出队时标记否则同一节点可能被重复入队。快排 Lomuto 分区的i始终指向「小于等于基准区」的最后一个元素循环结束后i1就是基准的正确位置。参数上low和high是闭区间下标调用时传0和len(nums)-1。4. 默写训练怎么排从 36 页到考场输出的 4 周节奏4.1 第一周按模块过一遍只求写对不求写快第一周的目标是把 36 页里的每个模板至少手写一遍不掐时间但要求编译通过或者逻辑自洽。我的习惯是拿一张白纸看完模板后合上凭记忆写写完再对照。写错的地方用红笔标出来第二天先默写昨天错的那几个。这一周最容易犯的错是「看懂了但写不出」。看懂和写出之间隔着一条肌肉记忆的鸿沟只有手写才能填上。链表反转的指针操作、二叉树非递归的栈条件、快排分区的边界这些地方看十遍不如写一遍。具体安排上线性表和栈队列两天二叉树三天图和查找两天排序两天。每天写完后花 10 分钟把当天的模板在脑子里过一遍不写代码只想逻辑。4.2 第二周掐时间默写把单题控制在 15 分钟内第二周开始掐时间。408 的算法题建议控制在 15 到 20 分钟893 的单道小题控制在 10 分钟。掐时间的目的不是制造焦虑而是暴露「哪里卡住了」。卡住的地方通常不是思路而是某个边界条件或者某个变量的初始值。我一般会准备一个「卡壳记录表」每次掐时间默写时把卡住超过 30 秒的地方记下来。一周下来卡壳点会集中在三到五个地方比如「二分查找的 right 初始值」「快排分区的 i 初始值」「BFS 的 visited 标记时机」。这些就是你的个人易错清单考前只看这个清单。4.3 第三周真题变体训练每道题先判断骨架再写第三周开始做真题但做法要变。拿到一道算法题先不写代码用一句话说出它的核心骨架是什么属于哪个模板的变体。判断完骨架后再写写的时候刻意往模板上靠。比如题目是「判断二叉树是否对称」核心骨架是「递归遍历的变体」具体是「同时遍历左右子树并比较」。题目是「找到数组中第 k 大的元素」核心骨架是「快排分区的变体」用分区函数定位第 k 大的位置。这一周的关键是建立「题目 → 骨架」的映射速度。映射速度上来了考场上才能快速判断该用哪个模板。4.4 第四周模拟卷实战把默写时间压到 10 分钟以内第四周用模拟卷实战按考试时间做整套卷子。算法题部分目标是把默写时间压到 10 分钟以内留出时间给其他题型。这一周不再学新模板只反复默写易错清单上的那几个。模拟卷做完后重点分析算法题的失分点。如果是思路错说明骨架判断有问题如果是边界错说明默写不够熟如果是时间不够说明默写速度还需要提。针对不同失分点最后几天做针对性训练。5. 避坑默写算法模板时最容易翻车的 5 个地方5.1 二分查找的 right 初始值和循环条件不匹配现象写二分查找时有时候能过有时候死循环或者返回的位置差一位。原因right的初始值和while循环条件、left/right的更新方式必须配套。right len(nums)对应左闭右开区间循环条件用left rightright len(nums)-1对应闭区间循环条件用left right。混用就会出错。解决固定一套写法。我建议统一用左闭右开[left, right)right初始化为len(nums)循环条件left right这样不容易死循环。5.2 链表操作忘记保存 next 指针现象反转链表或删除节点时代码执行后链表断了或者陷入死循环。原因修改curr.next之前没有保存原来的next节点导致后续节点丢失。解决养成习惯只要要修改curr.next第一行先写nxt curr.next。这个习惯能避免 90% 的链表断链问题。5.3 二叉树非递归遍历的栈条件写反现象非递归中序遍历时节点访问顺序不对或者栈溢出。原因while curr or stack写成了while curr and stack导致当前节点为空但栈不为空时提前退出。解决记住「或」不是「与」。当前节点为空但栈里还有节点时需要弹出栈顶继续处理所以条件是or。5.4 快排分区返回的基准位置差一位现象快排结果不正确或者递归时区间划分错误。原因Lomuto 分区返回的是i1不是i。i指向的是小于区的最后一个元素基准在i1的位置。解决写完分区函数后用一个简单例子手动验证比如[3,1,2]看返回的位置是不是基准2的正确下标。5.5 BFS 的 visited 标记时机错误现象BFS 遍历时同一节点被多次访问队列爆炸或者结果重复。原因visited在出队时标记而不是入队时标记导致同一节点被多个邻居重复入队。解决入队的同时标记visited出队时不再判断。这样每个节点最多入队一次。6. 从默写到变形用「骨架 边界」法处理没见过的新题考场上遇到没见过的算法题是常态但绝大多数「新题」都是旧骨架的变形。我处理这类题的习惯是两步先找骨架再定边界。找骨架的方法是问自己三个问题这道题的操作对象是什么数组、链表、树、图核心操作是什么遍历、查找、修改、合并有没有现成的模板覆盖这个操作组合比如「在二叉搜索树中找第 k 小的元素」操作对象是 BST核心操作是遍历骨架就是「中序遍历 计数器」。定边界的方法是列出所有可能出错的输入空输入、单元素、重复元素、目标值不存在、目标值在两端。每列一个就在代码里加一个对应的处理。这一步花不了两分钟但能避免大部分边界失分。下面这张表是我常用的「骨架 → 变体」映射你可以对照自己的易错清单补充。骨架常见变体边界重点二分查找找左边界、找右边界、找插入位置right 初始值、循环条件链表反转反转前 k 个、反转区间、k 个一组反转断链保存、头结点处理二叉树遍历层序、锯齿层序、右视图队列长度快照、空节点判断快排分区找第 k 大、颜色分类、三路分区基准位置、递归区间BFS最短路、拓扑排序、连通分量visited 时机、入队条件最后说一个我自己的教训早期复习时我总想把每个模板的每个变体都背下来结果 36 页变成了 60 页考前反而不知道看哪个。后来改成「只背骨架变体靠现场推」反而更稳。骨架是有限的变体是无限的把有限的骨架背到条件反射考场上才有余力处理变形。希望帮到你。本文还有配套的精品资源点击获取