数据结构与算法笔试考点总结：高频手写代码模板与避坑指南

简介：数据结构与算法是程序员的基石，也是计算机类笔试与面试的必考领域。理解时间复杂度与空间复杂度的本质，掌握链表反转、二叉树遍历、快速排序、二分查找等高频操作的手写实现，是应对有限时间内编码考核的关键。从基础概念出发，梳理常见数据结构的必考动作与算法复杂度推导，形成一套包含二十个手写模板的复习清单，并指出递归爆栈、边界条件等常见陷阱，帮助读者将知识转化为可稳定输出的考场能力。

1. 计算机类笔试里的数据结构与算法知识点总结，为什么值得花一周专门背

先讲一个常见翻车现场：某同学刷了三百道题，上了考场却连一棵二叉树的非递归后序遍历都写不顺，最后只留了递归实现的代码，在“空间复杂度”追问环节直接崩溃。另一类问题刚好相反——能把红黑树的旋转背得滚瓜烂熟，但让他手写一个二分查找，却在while (l < r)和while (l <= r)之间来回改，浪费了本可以去解大题的十分钟。

这两类问题指向同一个事实：计算机类考核中的数据结构与算法，本质上不是在考“你知道多少概念”，而是考“你在有限时间里能否把高频知识点还原成可运行的代码和可解释的结论”。这篇知识点总结不会带你刷上千道题，而是把考点收敛成一张检索表、一组必须手写熟练的代码模板、一份避开常见错误的清单。适合两类人：刚开始系统复习的新手，以及离考核还剩两三周、需要把知识密度压缩到极限的老手。你的目标是学完就能闭上眼睛把链表反转、二叉树层序遍历、快排分区、二分查找这几段核心代码现场写出来——这才叫“掌握”。

下文所有内容都围绕一个主轴：考什么、怎么背、怎么写、坑在哪。从考点梳理开始，再到手写代码，最后落到临考模板。

2. 把考点梳理成一张检索表：考什么、怎么考、怎么答

数据结构与算法的复习最怕“什么都看了，什么都不深”。市面上很多知识点总结按教材目录平铺，顺序表、链表、栈、队列、树、图、排序、查找各占一章，每章又是定义、操作、代码、复杂度一整套。问题在于：考核不会按教材出题，它按“动作”出题。

所谓“动作”，就是某类数据结构在真实工程和笔试里最常用的那几个操作。你会发现线性表翻来覆去就考插入删除和反转，树就考遍历，图就考最短路径和拓扑排序。把动作抽出来，考点立刻少了一半。

2.1 数据结构模块：七类对象的必考动作

下面这张表是复习时的最小检索集，每种数据结构只保留高频动作。旁边标注“必须会手写”或“能口头说清”两个要求，避免你在不重要处消耗过多时间。

排序和查找是跨数据结构的算法，单独放到第 4 章讲。这块复习策略很简单：每个对象先花半小时把定义和复杂度写在一张卡上，再花一小时把“必须手写”的代码敲三遍。第一遍看着写，第二遍合上写，第三遍限时写。三天以后这些代码会变成手指记忆，考场输出速度比现场推演快得多。

2.2 算法模块：复杂度、排序、查找、递归

复杂度是算法题的“入场券”。很多人只记住 O(n) < O(n log n) < O(n²) 这个粗略顺序，但一遇到具体场景就乱。比如哈希表平均 O(1)、最坏 O(n)，为什么还能大量使用？因为设计里装载因子和冲突策略把最坏情况压到几乎不出现。再比如快速排序平均 O(n log n)、最坏 O(n²)，核心考题问你“什么时候退化成 O(n²)”——答案是每次分区都选到极值作为基准，递归深度变成 n。

常见复杂度从小到大可以排成一条链：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。笔试时遇到一个陌生算法，先看它的主体循环层数，再看递归展开的规模，基本能估出数量级。嵌套一层循环通常是 O(n) 到 O(n²)，取决于内层是否随外层线性变化；递归则常涉及 O(log n) 与 O(n log n) 的区别——二分递归是 log n 层，每层线性扫描就是 n log n。

递归本身是算法模块里的隐藏考点。它不单考斐波那契，而是考“递归怎么转迭代”“递归栈溢出怎么办”。这类问题在机考中尤其常见，因为系统栈深度有限。处理套路固定：能写尾递归的写尾递归，不能写的用显式栈模拟。显式栈的自由度更高，面试追问时也更占优势。

2.3 复习顺序：先建立“最小写码集”

多数人复习失败不是因为不努力，而是顺序不对。一上来就啃图的复杂算法，线性表和二叉树还没写熟，结果每个知识点都是半生不熟。我一般建议按这条链推进：线性表 → 栈与队列 → 二叉树 → 排序 → 查找 → 图。

线性和树是基础，排序是它们之上的综合应用，查找和二分又是一把通用钥匙，图则放在最后冲刺。每完成一个阶段，要有可量化的产出：线性表阶段结束，能默写链表反转和有序数组合并；二叉树阶段结束，能默写三种递归遍历和层序遍历；排序阶段结束，能默写快排、归并、堆排中至少两种。这个“最小写码集”大约包含二十段代码，也就是第 6 章要讲的核心模板。

阶段规划建议采用三遍法：第一遍理解结构，第二遍对着代码逐行讲清每行的作用，第三遍合书在白纸上模拟考试写码。三遍之后基本不用再翻教材，直接用题来检验。

3. 线性结构与树图：手写代码的高频考点

理论归理论，考场上最终看的是手写代码。这一章把第 2 章划定的“必须手写”项目展开，给出可直接背诵的代码骨架，并解释每段代码里关键的边界处理。

3.1 链表反转与环检测：三个指针解决的问题

链表反转是出现频率极高的一道题，因为它能同时考察指针操作和对“引用”的理解。递归思路简单但面试追问时容易被空间复杂度问住，迭代法更稳妥。常见做法是用三个指针：pre指向已反转部分的前驱，cur指向当前待反转节点，next暂存下一个节点。

def reverse_list(head): pre = None cur = head while cur: next_node = cur.next # 先保存下一个节点，防止链表断开后丢失 cur.next = pre # 把当前节点的指针指向前一个节点，完成反转 pre = cur # pre 向后移动 cur = next_node # cur 向后移动 return pre # 循环结束时 pre 指向原链表的尾节点，即新链表头

逻辑说明：每次循环只做两件事——把当前节点的next反转，然后把两个指针整体后移。关键在于next_node必须最先保存，否则执行cur.next = pre后，原来的下一个节点就找不到了。

参数说明：函数入参head是原链表头节点，返回值为反转后的新链表头；空链表和单节点链表直接由循环逻辑覆盖，不需要特判。这道题的边界陷阱是返回值，很多人写成返回cur，但循环结束时cur已经是None，正确返回的是pre。

环检测的快慢指针是同一个思路的延伸。慢指针每次走一步，快指针每次走两步，如果链表有环，两者必然相遇。

def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next # 慢指针每次走一步 fast = fast.next.next # 快指针每次走两步 if slow is fast: return True return False

逻辑说明：快慢指针都在环里移动时，快指针相对慢指针每次逼近一步，所以迟早相遇。快指针循环条件要同时判断fast和fast.next，避免空指针异常。

3.2 二叉树遍历：递归背模板，非递归考栈

二叉树遍历是“背了不一定考，但不背一定会卡”的知识点。递归版三兄弟只有一行核心代码的区别，必须形成肌肉记忆；非递归版则是栈的典型应用，常作为“手写代码”的压轴题。

先看递归版先序遍历：

def preorder(root): if root is None: return visit(root) # 先访问根节点 preorder(root.left) # 再递归左子树 preorder(root.right) # 最后递归右子树

逻辑说明：递归版之所以容易写，是因为系统帮我们维护了调用栈。真正在考场上让代码加速的是先序遍历的显式栈版本，因为能直接体现对栈的理解：

def preorder_iter(root): if root is None: return [] stack = [root] result = [] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) # 右子树先入栈，左子树后入栈，保证左子树先弹出 if node.left: stack.append(node.left) return result

逻辑说明：栈是后进先出，要想先访问左子树，就必须让右子树先入栈。这段代码还有一个变体：先只沿左路压栈再依次弹出，配合visited集合就能处理中序和后序。考试时如果能写出这个栈版本，面试官对“非递归理解”的评价通常远高于递归版。

层序遍历则用队列，每轮循环处理一层的节点：

def level_order(root): if root is None: return [] from collections import deque queue = deque([root]) result = [] while queue: level = [] for _ in range(len(queue)): # 每轮循环开始前，queue 中恰好是当前层所有节点 node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

逻辑说明：len(queue)必须在进入for循环前确定，Python 里range(len(queue))在循环开始时就固定了迭代次数，所以能正确切分一层。这个“按层定长”的技巧同时可用在图的 BFS 里，比如求最短步数。

3.3 图的考场策略：邻接表、Dijkstra 与拓扑排序

图这章很多学生复习时投入产出比最低。图的算法面很宽，但考核真正高频的只有三件事：建图方式、BFS/DFS 遍历、拓扑排序与最短路径。

建图首选邻接表，因为它既能表达稀疏图，又方便遍历。

graph = [[] for _ in range(n)] # n 为节点数 for u, v in edges: graph[u].append(v) # 有向边 u -> v

逻辑说明：graph[i]是节点 i 的邻居列表。无向图加双向边即可；带权图把邻居改成(v, weight)元组。邻接矩阵适合稠密图，但笔试和机考题目规模通常用邻接表就够。

拓扑排序最稳的写法是入度表 + BFS，也叫 Kahn 算法：

from collections import deque def topo_sort(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 queue = deque([i for i in range(n) if indeg[i] == 0]) result = [] while queue: u = queue.popleft() result.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v) if len(result) != n: return [] # 存在环，无法完成拓扑排序 return result

逻辑说明：每次都把当前入度为 0 的节点取出，相当于不断剥离没有前置依赖的任务。最终结果长度如果小于节点总数，说明图里有环——这是判断“课程安排是否能完成”这类题的核心结论。

Dijkstra 算法在笔试中更常以“思想分析”出现，比如追问为什么不能处理负权边。手写完整代码量较大，机考时间紧时可退化为用优先队列实现的核心循环。务必记住它的贪心前提：每次选择距离最近且未确定的节点，这个选择一旦确定就不再更新。正因为这个前提，负权边会让已确定的最短路径被后续负权更新推翻，所以必须用 Bellman-Ford。

4. 排序与查找：背结论不如推一遍

排序和查找在知识点总结里占的篇幅通常最多，但真正该背的结论不超过十行。更重要的排序和查找的代码实现，以及它们和复杂度的对应关系。这一章把三个必写算法拆开，说明边界在哪，再用一个对比表收住结论。

4.1 快速排序：分区函数是失分重灾区

快排的平均性能最好，也是各大考核中出镜率最高的手写排序。它的核心不是递归主框架，而是分区函数partition。分区写不对，递归外层再没意义。

def partition(arr, low, high): pivot = arr[high] # 每次取最后一个元素当基准 i = low - 1 # i 指向已处理区段的最后一个元素 for j in range(low, high): if arr[j] <= pivot: # 小于等于基准的放到左边 i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] # 基准归位 return i + 1 # 返回基准最终下标

逻辑说明：循环里j负责扫描待处理区，每当遇到小于等于基准的元素，就把i右移并交换，实际上是在向左半区累积较小区段。循环结束，基准pivot换到i+1位置，此时基准左侧全部小于等于它，右侧全部大于它。

参数说明：low和high是这一轮处理的左右边界；pivot取arr[high]，换别的取法会导致i的初始值和交换逻辑变化，考试时不要中途更换策略。

快排退化到 O(n²) 的本质是每次分区严重失衡。最坏情况发生在基准正好是当前区段的最大或最小值时，此时每次只消除一个元素，递归深度为 n，总比较次数就是 n + (n-1) + ... + 1，也就是 O(n²)。

4.2 归并排序：稳定但吃内存，顺手解决逆序对

归并排序的优点是稳定，缺点是需要额外 O(n) 空间。代码结构非常固定：先递归拆，后合并。

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i = j = 0 res = [] while i < len(left) and j < len(right): if left[i] <= right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res.extend(left[i:]) res.extend(right[j:]) return res

逻辑说明：合并时left[i] <= right[j]用了小于等于，所以相同元素的相对顺序得以保持，这是归并稳定性的来源。临时数组res就是额外空间的去向。

归并排序在考题里还有一个高频变体：计算逆序对数量。合并时如果left[i] > right[j]，说明left中从i到末尾的所有元素都比right[j]大，逆序数直接加上len(left) - i。一次合并统计一轮，所有合并的统计值累加就是答案，时间复杂度保持 O(n log n)。

4.3 二分查找：区间定义是死循环源头

二分查找可能是全篇最容易被“觉得会了”的算法。它代码短，但边界错法花样多。最常见的错误是循环条件与区间定义不匹配。下面给出一种左闭右闭写法，并把返回值收在l上：

def binary_search(nums, target): l, r = 0, len(nums) - 1 # 左闭右闭：区间 [l, r] while l <= r: mid = l + (r - l) // 2 # 用减法代替 (l+r)//2，防止整型溢出 if nums[mid] == target: return mid elif nums[mid] < target: l = mid + 1 else: r = mid - 1 return -1

逻辑说明：这里的关键是每轮缩区间时，都把mid排除在外。因为nums[mid]已经比较过了，不需要再留在区间里。如果写l = mid或r = mid，区间可能永远缩不小，于是死循环。

参数说明：nums必须有序且支持下标访问；target是目标值；返回值为目标下标或 -1。这个模板的变体，比如找左边界、右边界，都是在nums[mid] == target时继续缩半边区间，而不是直接返回。

排序算法的最终结论整理为下表，笔试前直接背它，比临时推导稳：

插入排序的最好 O(n) 对应几乎有序的数据；快排最坏 O(n²) 对应每次分区严重失衡；堆排虽然最坏也是 O(n log n)，但常数较大且不稳定。这三行是面试追问里最喜欢挖的细节。

5. 应试避坑：算法题做错的三类共性原因

这一章写的是复习和模考里反复出现的踩坑记录，每条都按“现象 → 原因 → 解决”展开。这些坑不解决，知识点总结背得再熟，考场上一紧张照样写错。

5.1 复杂度背混：把快排最坏情况记成 O(n log n)

现象：被问到“快排最坏时间复杂度是多少”时脱口而出 O(n log n)，还补了一句“因为是分治法”。追问“什么情况下变坏”时答不上来。

原因：只背了平均复杂度，没从分治递归的角度推导最坏情形。快排的递归表达式是 T(n) = T(左半区) + T(右半区) + O(n)。平衡分区时，每层总比较量是 O(n)，递归树深度是 log n，所以是 O(n log n)；当基准每次都是最小或最大值，左右半区严重失衡，递归深度变成 n，总复杂度变成 O(n²)。

解决：复习时不要背结论，要把递归表达式写一遍。看到任何分治算法先问自己“每一层的工作量是多少、递归深度是多少”。堆排最坏也是 O(n log n) 的原因同理——堆调整操作每次都把问题规模减半，不会出现极端失衡，所以它最坏情况仍然是 O(n log n)。这两组结论放在一起对比记，才不容易混。

5.2 手写递归爆栈：没有考虑深度限制

现象：本地测试递归版快排或归并时一切正常，到了机考环境用较大规模数据一跑，直接抛栈溢出异常，或是在递归后序遍历被追问“空间复杂度”时卡壳。

原因：系统栈帧大小是有限资源，递归深度达到数万层就可能溢出。归并排序递归深度是 log n，大多安全；但链表的递归反转、快排最坏情况下的递归深度都可能是 n，超过阈值就崩。更深一层的问题是，很多考生把“递归能用”等同于“递归能通过考核”，忽略了显式栈和非递归版本的教学意义。

解决：递归代码写完后顺手问自己“最大深度是多少”。超过几千层的，准备一个显式栈版本。比如用栈模拟后序遍历时，可以用(node, visited_flag)元组控制访问状态，压栈时标记是否已访问过。这一招在机考里能直接把递归爆栈翻车概率降到零。

5.3 边界条件写错：空输入、单元素、重复元素

现象：链表反转代码单独看没问题，但一遇到head = None就报属性错误；二分查找在数组只有两个元素时区间收缩不对，返回 -1；快排在所有元素都相等的输入上死循环。

原因：很多代码模板是拿“理想输入”推出来的，没有做边界防御。链表反转循环里直接访问cur.next，如果cur是None自然崩溃；快排分区把所有元素都小于等于基准时，i会一路走到high，如果基准是high则交换后原地归位没问题，但换一种基准写法就可能越界。

解决：给每段核心代码准备“三个测试样例”：空输入、单元素输入、全相同元素输入。写代码前先想清楚这三点，很多边界问题会自然暴露。链表反转在函数开头加if head is None或if head.next is None特判；二分查找让l和r的更新总是至少收缩一个下标；快排则在递归前判断low < high，避免对空区间再分区。这算是最低成本的后悔药，一次写好，节省考场上反复调试的十分钟。

6. 临考前三天：把知识点收成二十个手写模板

知识点总结类复习资料最大的问题不是内容不够，而是内容太散。理想状态是考前三天不再翻教材，只拿一张 A4 纸，按固定顺序把二十个模板手写一遍。写不出来的，就是当天需要重点补的地方。这个习惯我保持了很多年，每次考核前都靠它把焦虑转化成具体的行动量。

二十个模板可以按类别固定下来：链表反转、快慢指针找中间节点、链表删除节点、栈实现队列、队列实现栈、单调栈模板、循环队列、二叉树递归先序、递归中序、递归后序、非递归先序、层序遍历、二叉树最大深度、判断平衡二叉树、快排、归并排序、堆排序的堆调整过程、二分查找、拓扑排序、Dijkstra 核心循环。这些模板覆盖了至少七成高频手写题。

验证方式不是“看一遍觉得会了”，而是限时手写。我会给自己定一个规则：每个模板 10 分钟内写完，写完不要在纸上检查，直接默念逻辑推演三遍。第一遍看这行代码在输入是什么状态，第二遍看循环结束条件是否保证收敛，第三遍看返回值和边界特判。三遍下来如果没问题，这个模板才算过。

如果时间只剩三天，可以进一步压成“三表一码”：复杂度表、稳定性表、栈与队列操作表、二分模板码。这三张表覆盖几乎所有理论选择题，一份二分词解决所有手写题。模板不是死记硬背，而是背“结构骨架”，比如快排记住“分区、递归、基准归位”三个节点，其他细节由节点自然展开。

最后说一个比较私人的习惯：每次手写二分查找之前，我会先在草稿纸上写一行注释“区间 [l, r]，排除 mid”，然后才开始写循环。这行注释看起来多余，却能防止在最紧张的十分钟里思路漂移。类似的小动作可以延伸到链表反转前写“pre/cur/next”，层序遍历前写“当前层长度”。一句话注释，换来稳定输出，值得养成。

算法知识点总结到最后，比天赋更重要的是重复和复盘。二十个模板每天过一遍，每条踩坑记录考前再看一眼，考场上大概率不会再犯同类错误。希望这套方法帮到你，也希望你在真实考场上，能把每个模板写成一气呵成的肌肉记忆。

本文还有配套的精品资源，点击获取