简介面向考研408与893自命题的数据结构算法题总结共36页系统梳理数组、链表、栈、队列、二叉树等核心数据结构并将排序、树的遍历、递归与非递归、图遍历、动态规划等高频算法浓缩成一份便携PDF。该PDF文档共1个文件压缩包仅1.67MB已有1680人学习下载资源轻量、便于随身翻阅。内容按专题清晰组织既有合并排序数组、约瑟夫环、栈实现队列、最小栈、循环队列、链表删除节点/反转/重排/排序等经典题目也覆盖二叉树前中后序与层序遍历、有序数组转二叉搜索树、Top K问题、双指针、二分查找、贪心、01背包、最长公共子序列等进阶内容。整体来看每题配有思路解析或C语言代码示例尤其适合备考后期快速刷题、查漏补缺图论遍历等易错点亦有提醒能帮助考生系统建立解题框架。1. 考研数据结构算法题这36页先解决的是信息差考研数据结构算法题和LeetCode刷题完全是两回事。你刷两百道LeetCode以为稳了上了考场才发现手写代码不给编译器、没有AC判定、判分标准是人工看的、函数签名还得按题目约定来。而且408统考和893这类自命题出题风格差异非常大——408更爱在链表和排序上做文章自命题则喜欢考树的递归和综合性应用题。这份36页的考研数据结构算法题总结893408核心就是把高频算法题提炼成可背诵、可默写的模板按考点和易错点重新组织了一遍。适合两类人408统考生想压缩算法题的复习时间893自命题考生想在有限篇幅里覆盖学校爱考的题型边界。不是刷题替代品是考点地图。2. 题型结构拆解408统考与893自命题的真题分布差异2.1 408统考与893自命题的题型差异先说408。408的大题里算法题通常是一道占13分左右放在数据结构部分。它的特点是题干很短但要求写的是完整函数而不是LeetCode那种类方法。比如给一个带头结点的单链表要求原地逆置空间复杂度O(1)——你要是写了个新建链表的解法思路对了也拿不到满分因为空间复杂度超了。893这类自命题则不一样代码题数量更多三四道很常见单题分值在10到20分之间。它不只考链表还会把树、排序、栈混着出甚至要求写出算法设计思路、时间复杂度和完整代码三段式。这就意味着你不能只背代码还得会说清楚为什么这么写。所以拿到这份36页总结第一件事不是从头翻到尾而是按自己的目标院校做题型映射。你考408重点看链表题、排序题、KMP你考自命题全书都得过但树的递归和图的遍历优先级要拉高。2.2 高频算法清单按考点优先级排序我把这份总结里的高频考点按考试出现频率和分值做了一个优先级分层你在复习时按这个顺序投入时间性价比最高。优先级考点常见出题形式建议投入时间S级链表操作逆置、合并、删除手写完整函数34天S级排序算法代码快排、归并、堆排写代码复杂度分析34天A级KMP算法手算next数组12天A级二叉树遍历与递归手写递归非递归23天A级查找二分、BST手写代码12天B级图DFS/BFS/最小生成树代码或算法思路12天这里有个很容易被忽略的点哈希表和栈在代码题里出现频率不高但在选择题里出镜率极高。所以如果你时间紧代码题复习优先级就按上表走选择题另开一条线刷王道单科书就好。我的习惯是先S级再A级B级如果时间实在不够至少把算法思路背下来。因为自命题的评分标准里思路分通常占30%左右代码写不全但思路清晰也能拿一半分。这也是为什么这份总结里每个题都配了复杂度分析和思路说明——它默认你写代码前先学会讲道理。3. 线性表与链表手写模板四个必背代码与边界处理3.1 头插法与尾插法建表模板与适用场景链表的代码题十个里有八个跟头插法、尾插法有关。头插法的核心特性是生成逆序链表尾插法生成正序链表。很多考题就是换个壳说“把数组元素按逆序存入链表”本质就是头插说“保持原顺序建表”就是尾插。// 头插法建立带头结点的单链表 // 输入数组a长度n // 输出带头结点的单链表L void createListHead(LinkList L, int a[], int n) { L (LNode*)malloc(sizeof(LNode)); L-next NULL; // 头结点next置空这是头插法的关键起点 for (int i 0; i n; i) { LNode* s (LNode*)malloc(sizeof(LNode)); s-data a[i]; s-next L-next; // 新结点指向原第一个结点 L-next s; // 头结点指向新结点 } }逻辑说明头插法的核心就两句——s-next L-next先把新结点链到原链表头部再把头结点的 next 指向新结点。注意顺序不能反反了会丢链。参数说明输入数组a[]保存待插入的元素n是数组长度LinkList L是引用传递函数内部对L的修改能传回调用方。这里用带头结点的写法是考研代码题的默认约定不要画蛇添足写不带头结点的版本。尾插法唯一的区别是维护一个尾指针r每次新结点插到r后面再更新r。考试里最常考的是“用头插法实现逆序”所以头插法一定要默写到条件反射级别。3.2 链表逆置三个指针的移动顺序链表逆置是408最爱的题之一难度不大但特别容易在指针移动顺序上翻车。核心思路是三个指针pre指向已逆置部分的头cur指向当前要处理的结点r暂存cur的下一个结点防止断链。// 单链表原地逆置空间复杂度O(1) // 输入带头结点的单链表L // 输出逆置后的单链表L void reverseList(LinkList L) { if (L-next NULL || L-next-next NULL) { return; // 空链表或只有一个结点不需要逆置 } LNode* pre L-next; // pre指向当前第一个结点 LNode* cur pre-next; // cur指向第二个结点 pre-next NULL; // 第一个结点变成逆置后的尾结点next置空 while (cur ! NULL) { LNode* r cur-next; // 先保存cur的后继防止断链 cur-next pre; // 反转指针指向 pre cur; // pre后移 cur r; // cur后移到原后继 } L-next pre; // 头结点指向逆置后的第一个结点 }逻辑说明这个是头插法的变体本质是“把第二个结点开始逐个用头插法插到已逆置部分的前面”。r这个临时变量是保命符漏了它cur一旦改了 next后面的结点就全丢了。参数说明LinkList L引用传递函数先做空表单结点判断这是加分项很多评分标准里边界判断单独有分。这里有个考场细节你一定要注意写完pre-next置空之后很多人的while里只写了cur-next pre和pre cur忘了先存r。这是链表题最大的知识空白点我见过太多人在这一步断链。3.3 有序表合并返回值与哨兵结点的取舍有序链表合并也是高频题往往和归并排序思想联动考查。题目一般给两个递增有序链表要求合并后依然递增且不占用额外空间。// 合并两个递增有序链表结果仍递增 // 输入带头结点的单链表L1, L2 // 输出合并后的链表L1 void mergeList(LinkList L1, LinkList L2) { LNode* p L1-next; LNode* q L2-next; LNode* tail L1; // tail指向新链表的尾结点初始为L1头结点 L1-next NULL; // 断开原L1从头构造 while (p ! NULL q ! NULL) { if (p-data q-data) { tail-next p; // 接上p tail p; // 尾指针后移 p p-next; } else { tail-next q; tail q; q q-next; } } if (p ! NULL) tail-next p; // 剩余部分直接拼接 if (q ! NULL) tail-next q; // 两个循环只可能有一个还有剩余 }逻辑说明注意这里把 L1 的头结点复用为新链表的头结点省了一个malloc。L2 的头结点在合并后成为游离结点很多答案会忽略释放它理论上有内存泄漏但考研手写代码一般不追究。参数说明p和q分别作为两条链的游标tail始终指向新链表的尾结点保证插入是 O(1) 的。核心判断是还是取决于题目要求稳定合并——稳定排序要求相等时先取 L1 的元素所以写成是更稳妥的习惯。自命题还有一种变体合并后去重。处理办法就是在else分支里先判断q-data是否等于tail-data相等就跳过q不接。这算一个小考点你拿这份总结复习时把去重版本也默写一遍考到就不慌。4. 排序、KMP与树的代码题拿分点都在边界条件里4.1 快速排序与归并排序考试更爱考哪一个408统考里排序算法的代码题其实不常直接让你写完整快排但选择题和综合题里稳定性和复杂度分析年年都有。893自命题则相反经常直接要求写一趟快排或完整归并。你得有能力根据院校方向做取舍。归并排序在自命题里出镜率比快排高原因很实际——它的递归模型清晰、代码结构固定判分容易给步骤分。而且归并排序天然适合考“两个有序序列合并”的子问题正好和有序表合并联动。// 归并排序完整代码 // 输入数组a下标low到high // 输出排序后的数组a通过tmp中转 void mergeSort(int a[], int low, int high) { if (low high) { int mid (low high) / 2; mergeSort(a, low, mid); // 递归排序左半 mergeSort(a, mid 1, high); // 递归排序右半 merge(a, low, mid, high); // 合并两个有序段 } } void merge(int a[], int low, int mid, int high) { int tmp[100]; // 临时数组注意大小要能覆盖题目给的数据范围 int i low, j mid 1, k low; while (i mid j high) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; // 左半有剩余 while (j high) tmp[k] a[j]; // 右半有剩余 for (i low; i high; i) { a[i] tmp[i]; // 数据拷回原数组空间O(n) } }逻辑说明递归边界是low high此时区间只有一个元素或为空天然有序。合并过程就是两个有序序列从头比较谁小先放谁。这里用保证稳定性。参数说明mid切分点写法是(lowhigh)/2注意别写成low (high-low)/2以外的方式其实两种都行但一定要用整型运算别溢出。tmp数组是临时工作区每一次合并都会整体用一遍这个写法时间O(nlogn)、空间O(n)。考场上的常见翻车点是递归函数写了merge函数忘了写或者merge里把low写成0导致拷回时数据错位。写完后拿[5,4,3,2,1]走一遍是最快的自查法。4.2 KMP的next数组手算流程与代码模板KMP在408里从来没考过写完整代码但手算next数组和nextval数组年年都有选择题。自命题则可能要求写出求next的代码。这篇总结里KMP部分的核心就是这个数组推导。// 求next数组代码模板目标串下标从1开始 // 输入模式串T长度n // 输出next数组next[1]0, next[2]1 void getNext(char T[], int n, int next[]) { int i 1, j 0; next[1] 0; while (i n) { if (j 0 || T[i] T[j]) { i; j; next[i] j; } else { j next[j]; } } }逻辑说明j始终记录“已经匹配的前缀长度”next[i]的值就是当第 i 个字符失配时模式串指针应该回退到的位置。j 0时表示前缀为空必须向右移动主串指针所以 i 和 j 都加 1。参数说明这个模板要求模式串下标从 1 开始所以字符串数组的 0 号位通常空出来或存一个无关字符。如果你用的是从 0 开始的数组整个公式要整体平移考试时最容易搞混的就是这个起点。手算快速法next[1]0next[2]1从第 3 个开始看前面字符串的最长相等前后缀长度再加 1。比写代码快而且不容易错。很多同学纠结 next 和 nextval 的区别——nextval 只是对 next 的一个优化修正考试里让你“求next数组”就老老实实写next别多此一举默认为nextval。4.3 树与递归遍历模板和边界条件树的代码题在自命题里基本是必考常见形式是要求写递归遍历或者在遍历基础上做统计操作。比如统计叶子节点数、求树的高度、判断两棵树是否相同。这类题的核心模板是递归三要素终止条件、递归调用、返回值。// 统计二叉树叶子节点数 // 输入二叉树根节点bt // 输出叶子节点个数 int countLeaves(BiTree bt) { if (bt NULL) { return 0; // 空树0个叶子 } if (bt-lchild NULL bt-rchild NULL) { return 1; // 左右子树都为空当前节点是叶子 } return countLeaves(bt-lchild) countLeaves(bt-rchild); }逻辑说明递归的终止条件有两个——空节点返回0叶子节点返回1。这是递归里最容易漏第二个条件的情况只判断NULL会导致叶子节点多算一层递归空调用最终结果还是对的但会多走几步。真正危险的是把叶子判断写成return 0那叶子本身就没计数。参数说明BiTree bt就是指向根节点的指针C语言里就是BiTNode*。这个函数没有副作用纯递归计算返回值适合作为子树操作的通用模板。把这题变一下求树的高度把叶子返回1改成return max(height(left), height(right)) 1判断两棵树是否相同再加一个参数传入第二棵树。树相关的算法题八成都基于这个递归结构变形模板背熟才能真正举一反三。5. 避坑手册手写代码与自命题判分的五个翻车点5.1 函数签名和题目约定不一致整题白写现象题目要求写“对带头结点的单链表进行逆置”考生写出来的函数没有返回链表而是在函数内部直接对参数操作但参数类型写成了值传递。原因很多同学在LeetCode刷惯了ListNode* reverseList(ListNode* head)这种返回值式写法太顺手到考研题目里没看清题目给的函数声明格式直接照搬。解决考前刻意做一件事——把每道题的函数签名单独抄一遍标注是引用传递还是返回值传递。C语言里链表题想要修改原链表必须用LinkList L引用或LinkList *L二级指针否则形参改了实参不变。自命题的题目有时会直接给出空函数让你填这时候一切以题干的函数签名为准。5.2 空间复杂度超限思路正确也拿不满分现象链表逆置题用新建链表存逆序结果最后复制回原链表。运行结果是对的但被扣了将近一半的分。原因题目明确写“空间复杂度O(1)”新建链表空间O(n)属于不满足题目硬性要求。408判分时算法思路分的权重很高但对复杂度超限的容忍度很低。解决背代码的时候把每个模板的时空复杂度写在代码块最上面默写时第一件事写复杂度再写代码。如果看到题目要求O(1)空间链表逆置、有序表合并这类题直接锁定三指针或尾插法思路。5.3 边界条件只判断NULL不判断单节点现象链表逆置的代码里只写了if (L-next NULL) return;没判断L-next-next NULL。单节点链表走进循环后代码逻辑还是能跑通但多一次无意义操作。原因边界判断不完整习惯性认为“链表为空就不用处理非空就进循环”。解决所有链表操作题一律按三档判空空链表、单节点链表、普通链表。每道模板题默写前都强制自己走一遍这三档测试。树递归同理空树、单节点树、普通树三档都要过。这个方法我在复现这份总结里的每个题时都用能筛出至少三分之一隐藏bug。5.4 while循环里丢逻辑指针后移漏写现象有序链表合并代码写完了同一个测试用例前面输出正确但运行到中间段就断了怀疑是自己数据写错了。原因tail tail-next或者p p-next这类指针后移语句写漏了循环体执行完游标没动陷入死循环或重复处理。解决写完循环体强制检查三件事——有没有改指针指向、有没有后移游标、循环条件变量有没有更新。我一般的自检法是每个while下来扫一眼所有涉及的指针在循环最后是否都推进了。这个习惯比反复调试有用得多。5.5 排序代码里求中点用(lowhigh)/2溢出现象归并排序或二分查找在数组很大时出现诡异错误本地测小数据没问题考试数据量大就崩溃。原因low high可能超过int上限虽然考研真题很难给你这么大的数组但标准代码要求严谨。解决写成low (high - low) / 2这在原理上等价但不会溢出。从这份总结里的归并排序模板起步就统一用这个写法形成肌肉记忆。6. 三遍刷题法把36页总结变成考场肌肉记忆6.1 三遍刷题法的具体节奏任何一份总结类资源最怕的是翻一遍就觉得“会了”。我复盘过自己的复习过程发现最有用的不是逐题精读而是一个固定的三遍刷题节奏。第一遍按章节顺序每个模板先看思路再看代码然后合上总结默写一遍重点是函数签名和边界条件。第二遍打乱章节顺序随机抽题限时15分钟一题写完只看复杂度分析和易错点提示纠正自己偏移的写法。第三遍只列出题号不看代码在纸上写出完整函数加复杂度说明。每遍中间隔两天第三天做下一遍时你会明显发现哪些题是“假会”——看着眼熟写不出来。这一遍的作用是把假会筛出来。36页的篇幅并不长三遍下来大约需要十天每天两小时比反复看强得多。6.2 考场手写代码的四条验证习惯考场没有编译器写完代码怎么确认能跑我的习惯是四步。第一步查函数签名和返回值跟题目要求一一对应。第二步走查一个正常用例比如链表逆置就拿 1→2→3→NULL 走一遍手动模拟指针变化。第三步走查边界用例空链表、单节点链表各来一遍。第四步检查复杂度在代码旁写出时间和空间复杂度。这套习惯原本是我自己的血泪经验——早期备考时总以为写得差不多就行后来一道归并排序题漏了merge函数直接少了六分。从那以后我每次考前都强制自己用这个流程过一遍所有模板题能拦住九成的手误。这份总结如果你能三遍刷完再带着四个验证习惯进考场算法题这部分就是你的稳定拿分区了希望帮到你。本文还有配套的精品资源点击获取