数据结构与算法分析Java版习题答案详解：从链表到图的备考攻略

简介：《数据结构与算法分析（Java语言描述）》（第三版）的配套习题答案文档，面向正在学习数据结构、Java 版算法分析与计算理论基础的本科学生及自学者。全文共 1 个 docx 文件，压缩包约 1.52MB，便于直接阅读、检索和打印。内容紧密围绕教材第一章至后续核心章节展开，覆盖文件递归处理（processFile）、整数各位数字之和的递归实现、数学归纳法证明对数性质、利用差分法推导数列求和、模运算与指数定律（如 2^100 mod 5）、大 O 符号估计算法复杂度等经典题目。每一题均配有英文原题、推导步骤或代码片段，有助于读者将抽象的数据结构与算法分析概念转化为可执行的解题思路，同时加深对算法时间复杂度和递归构造的理解。该资源已有 2430 人学习下载，可作为课后巩固、期末复习或考研复试算法部分的补充参考资料。

1. 为什么建议你认真对待《数据结构与算法分析（Java语言描述）》习题答案：备考者的共同卡点

备考者常常陷入同一种困境：链表删除代码纸面上完全成立，一运行就空指针；Dijkstra 算法手推没问题，写成代码却在边界条件反复翻车。这类卡顿的根源往往不是算法没看明白，而是缺少一个稳定的“答案对照”环节。《数据结构与算法分析（Java语言描述）》第三版的习题答案文档，把各章练习的参考解法按章节归拢到一起，能够帮你在一道题上快速判断：自己的思路偏在哪一步、答案代码为什么这样组织、考试会从哪个角度考察同一个知识点。它并不替你写代码，它给你一张可以反复比对、验证和提炼模板的基准。

沿着“这是什么→怎么用→坑在哪→怎么更进一步”的顺序，下面逐章展开。适合正在期末复习、准备面试，或工作中需要补数据结构短板的开发者。

2. 考点地图：从第三版教材结构到习题类型的映射

2.1 章节与考点的对应关系

拿到一份答案文档，大多数人都会直接翻到某一章，觉得当前章节对应的批量题目就是我做的题。但我建议先花二十分钟把整本答案的覆盖面扫一遍，建立起“章－知识点－题型”的映射。第三版正文大致这样分布：前三章打基础（Java语法回顾、算法分析、表栈队列），第4到第9章是数据结构主体（树、散列、堆、排序、并查集、图），最后两章是提高部分（算法设计技术、摊还分析）。答案文档中的题目也依循这个顺序铺开，所以你在使用过程中会自然地体会到：第三章的题目练的是编码基本功，第四章之后更多考察“懂数据结构特性后怎样组合使用”。

我把各章的常见考点整理成下面这张表，便于你边看答案边检查自己还有哪一块是空的：

这张表不是教材目录的照搬，也不是答案文档的目录，而是我认为在实际复习里最值得逐格检查的清单。你在哪一行心里没底，就专门去答案文档里找对应章节的题来做一两个，比全书通刷效率高得多。

2.2 三种答案形式：“会做”与“会背”的分水岭

另一个容易被忽视的点是，答案文档里并不全是输出一段代码让你跑，它有三种差别很大的题型，而复习方法对应地不一样。

第一种是不需要运行的推导题，集中在第1、2、11章。比如“证明某个递推式的解是O(N log N)”或者“证明对某个数据结构的一系列操作，其摊还代价上界是多少”。这类答案往往用公式和自然语言完成推导，你没法通过跑测试来判断对错。对待它的正确动作只有一条：合上答案，自己在纸上重推一遍，直到每一步都讲得过通。别背，因为背推导过程在变式题面前毫无抵抗力。

第二种是完整代码题，第3、4、6、7、9章的大多数题目属于这一类。答案通常直接给出可读的Java方法或类，有时候为了体现两种思路还会给两个版本。复习这类题的标准动作是：自己先写一版，然后对照答案，重点看循环条件、边界判断和返回值设计这三个位置。算法题考的就是这几个位置的小差异，其他部分只是把数据结构写出来而已。

第三种是设计题，代表在第10章“算法设计技术”，题目会描述一个应用场景，比如“输入一组硬币面值和金额，找最少硬币数”，答案先给解法思路、再给出代码或伪代码。这种题不是背一个模板就能过的，关键是训练“把场景翻译成状态”的能力。看答案时重点看它怎样把“金额”变成dp数组的下标、怎样定义初值，这两点一旦想通，题目就过去了。

2.3 老式 Java 代码与现代环境的落差

第三个需要提前建立认知的点是版本落差。这一版教材核心写作年代较早，答案代码风格在如今看来已经颇有“年代感”：集合类上使用Vector而不是ArrayList，遍历时用Enumeration而不用迭代器，泛型有时省略类型参数直接写List，方法里也不做null检查。这并不是答案的质量问题，而是当时的Java生态还没有演化到今天这个程度。

所以阅读答案文档代码时，先不要急着把它“现代化”。先把它当作静态的算法骨架来读，抓住四个关键元素：输入、数据结构、循环/递归、返回。读明白之后再在编辑器里手写一遍，顺手替换成当前惯用的语法，比如用List<String>替换裸List，用增强for循环替换索引遍历。把“先懂算法、再改工程”的顺序稳定下来，你既学到了答案里的思路，也不会被过时的代码风格带偏。

3. 使用答案文档的正确流程：比对、验证与内化三步

3.1 第一步：先建题号索引，不急着抄代码

第一次拿到这份答案文档，最容易犯的错就是把它当搜索工具：做一道题，搜一道题，关掉文档，再做下一道。这种做法会让做题体验越来越碎，最终脑子里只剩一堆代码碎片，知识结构反而越来越模糊。

我习惯在真正开始使用之前，先花一两个小时建一个非常简单的索引表：

这个表格本身不需要任何工具，一个文本文件或一张纸都行。它带来的变化是：每次从头翻开答案时，你不用靠记忆去回忆自己做到哪了，而是直接看表上哪些题标着“需要复习”。这个方法很土，但对题量大的阶段非常有效。它是把答案文档从“一次性查询工具”变成“复习数据库”的关键一步。表建好之后的第二轮复习，你会感受到明显的效率区别：你不再反复看已经会了的内容，之前卡壳的点会及时出现在视线里。

3.2 第二步：自我实现与答案差异比对

索引表之后最核心的动作，是“先写自己的答案，再看参考答案”。这个顺序一旦颠倒，效果就会大打折扣——先看答案再写实现，你会误以为自己掌握了，实际上只是顺着记住了一条路径。

以第3章常见的链表反转练习为例。我先自己写出迭代版：

public class LinkedListReverser { public ListNode reverse(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode next = current.next; // 保存下个节点 current.next = prev; // 指针调转 prev = current; // prev前进 current = next; // current前进 } return prev; } }

写完之后再打开答案文档，如果答案给的是递归版：

public ListNode reverseRecursive(ListNode head) { if (head == null || head.next == null) { return head; // 空链表或单节点直接返回 } ListNode newHead = reverseRecursive(head.next); // 反转后续链表 head.next.next = head; // 让后一个节点指回自己 head.next = null; // 断开旧链路，避免成环 return newHead; }

这时差异比对就不是“哪份对哪份错”了，而是三条观察：第一，迭代版多一个局部变量next，作用是缓存即将被覆盖的引用；第二，递归版不用额外变量，但长链表会栈溢出；第三，两者都要处理null输入。把这个观察记录下来，比背两份代码更有价值，因为它让你知道“在什么条件下选哪种写法”。

3.3 第三步：补上运行验证，把代码从“纸面”变成“运行中”

答案文档里很多代码不会自带测试入口，需要自己写一个可运行的调用来验证。这一步不能省，因为只有跑起来，你才会发现纸面上看不出的问题：循环少一次、比较运算符方向写反、递归出口太早返回，这些都是纸上读代码隐藏的问题。

我通常会给每一类题建一个极简的测试文件。以刚才的反转为例：

public class VerifyReverse { public static void main(String[] args) { // 构造一个 1->2->3->4->5 的链表 ListNode head = buildList(1, 2, 3, 4, 5); // 执行反转 ListNode result = new LinkedListReverser().reverse(head); // 按顺序打印，验证是否为 5 4 3 2 1 printList(result); } private static ListNode buildList(int... values) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; for (int v : values) { cur.next = new ListNode(v); cur = cur.next; } return dummy.next; } private static void printList(ListNode head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } System.out.println(); } }

这段测试代码的关注点在于：输入数据的构造没有硬编码在算法方法里，而是独立成buildList和printList两个辅助函数。这样你把答案里的算法方法替换进来时，改动成本非常低，可以直接用同一份测试反复验证不同方案。经过一次这样的运行验证，你会清晰地记住“为什么答案里要写prev=current和current=next这两行”，而不是把代码当作需要记忆的字符串。

3.4 对推导型答案的整理方式：结构化笔记

对不需要运行的推导题，验证手段不是测试，而是“结构化的重述”。比如第11章摊还分析里的一个典型答案，通常会先设置一个势能函数，再证明每次真实代价加势能变化后得到上界。如果你直接把这段证明抄进笔记，考试时仍然不会有帮助；更好的做法是提取成三个问题：已知条件是什么？核心观察是什么？推导主线是什么？

拿“用势能法分析二叉堆插入”的题目举例。标准答案的思路是：把势能函数定义为堆中节点总数；插入真实代价是上滤次数加一；势能变化是增加一个节点；均摊代价等于真实代价加势能变化。结构化之后，你会得到一个非常干净的模板：“设势能Φ = 堆节点数，则每次插入均摊成本为常数”。记住这个模板，比记住一页推导过程可靠得多。

所以对推导题，我的建议是：不在原文上画线，而是把它改写成三行笔记，越短越好，因为考试的临场发挥只认提炼过的结论。

4. 从答案里提炼套路：五个高频考点的通用解法

4.1 链表类题目：先保存引用，再改指针

链表答案里出现频率最高的核心手法，是“先保存引用，再改指向”。面试中你跟面试官聊链表反转、两两交换、找环，最后都会落到这一点上。答案里常见的代码如下：

public boolean hasCycle(ListNode head) { ListNode slow = head; // 慢指针 ListNode fast = head; // 快指针 while (fast != null && fast.next != null) { slow = slow.next; // 慢指针走一步 fast = fast.next.next; // 快指针走两步 if (slow == fast) { // 相遇则说明存在环 return true; } } return false; }

这段代码最容易出错的地方是while条件里的两个非空判断顺序：必须同时保证fast和fast.next都不为空，循环体里才敢执行fast.next.next。如果你只判断fast不为空，那么fast.next可能为null，下一步取.next.next就会空指针。答案里往往只写代码不提这个坑，但你在理解答案后重写一遍时，这个边界会立刻暴露出来。

4.2 树类题目：操作之后别忘了恢复平衡

第4章的答案，尤其是AVL部分，核心思想只有一句：一切旋转都是为了恢复平衡因子。删除一个节点导致某个子树高度减少，从而破坏祖先的平衡因子，答案里就会用左旋或右旋去修正。与其背四种旋转的名字，不如掌握统一的判断步骤：先算出当前节点左右子树的高度差，若为2或-2，再根据孩子的高度方向决定旋转方向。

这类逻辑在答案里会体现为代码，但没关系，我需要的框架是：

private TreeNode rotate(TreeNode root) { int bf = height(root.left) - height(root.right); // 平衡因子 if (bf > 1) { // 左子树太高，需要右旋 if (height(root.left.left) < height(root.left.right)) { root.left = rotateLeft(root.left); // LR情况：先左旋再右旋 } return rotateRight(root); } if (bf < -1) { // 右子树太高，需要左旋 if (height(root.right.right) < height(root.right.left)) { root.right = rotateRight(root.right); // RL情况：先右旋再左旋 } return rotateLeft(root); } return root; }

看答案时重点不是知道这代码对不对，而是看出它用一个balance factor分支覆盖了LL、LR、RL、RR四种情况。这是树类答案里最值得提炼的套路：用“失衡方向”来决定旋转，而不是用记忆去背旋转的名字。

4.3 堆操作：上滤、下滤与数组下标

堆的答案几乎全是数组实现，因为堆是一棵完全二叉树，用数组存天然紧凑。最重要的参数是数组下标从0还是1开始，这决定父节点坐标是(k-1)/2还是k/2。这个下标起点问题经常让人觉得有点玄学，但实际只是一个约定问题。

风险在这里：你如果从答案文档里抄了一份下标从1开始的堆实现，然后改了一行代码拿去做面试题，里面所有和索引有关的计算都会错位。正确做法是，把答案里的堆都改成下标0实现的这版模板，如果你更习惯0：

private void siftUp(int k) { while (k > 0 && heap[k] < heap[(k - 1) / 2]) { // 与父节点比较 swap(k, (k - 1) / 2); k = (k - 1) / 2; // 上滤：更新到父节点的位置 } }

把上滤/下滤各写一遍，然后手绘一个堆的结构，标出每个节点在数组中的下标，你就能彻底摆脱“答案这段循环条件为什么要减一”式的困惑。数据结构题考到最后，拼的就是这种对下标的把握。

4.4 排序：快速排序的分区与枢轴选择

排序章节中，最常出现在答案和笔试题里的就是快速排序。标准的分区写法一般有两种风格：挖坑法和左右交换法。先看挖坑法：

private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; // 一般直接取区间第一个元素作为枢轴 int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) j--; // 右侧找比 pivot 小的 arr[i] = arr[j]; while (i < j && arr[i] <= pivot) i++; // 左侧找比 pivot 大的 arr[j] = arr[i]; } arr[i] = pivot; return i; }

这个实现里隐藏着两个大问题。第一，如果整个数组已经有序，那么每次partition的pivot都是最小元素，分割极度不均匀，递归深度变成O(n)，总复杂度退化成O(n²)。第二，分区的比较符号用了等号，这意味着所有等于pivot的元素都会被轮换到右侧，这本身不影响正确性，但会改变相同元素之间的原始相对顺序，也就是不稳定。

不同的面试场合考点不同：如果是让你手写快排，你只需保证功能正确；如果问到复杂度为什么退化和怎么优化，你一定要答出随机选pivot、三数取中、小区间用插入排序这几种策略。答案里多数只给基础版，如果你能把这三个优化也补上，这部分就算吃透了。

4.5 图：visited 标记的时机区分 DFS 与 BFS

图算法的单测并不像树那么容易写，但是答案里的主线其实非常清晰。DFS和BFS的唯一本质区别就是：DFS是在进入递归前标记visited，BFS是在入队那一刻标记visited。很多人觉得这区别微乎其微，实际上错一次就能看到完全不同的遍历序列。

一个标准的DFS骨架：

void dfs(List<Integer>[] adj, boolean[] visited, int start) { visited[start] = true; // 进递归前就标记，防止重复访问 for (int neighbor : adj[start]) { if (!visited[neighbor]) { dfs(adj, visited, neighbor); } } }

在答案里，BFS的另一种标记时机是用队列：

void bfs(List<Integer>[] adj, boolean[] visited, int start) { Queue<Integer> queue = new LinkedList<>(); queue.offer(start); visited[start] = true; // 入队时标记，避免同一节点多次入队 while (!queue.isEmpty()) { int cur = queue.poll(); for (int neighbor : adj[cur]) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } }

区别就写在注释里：BFS的visited更新要放到入队前，而不是出队后。如果你把标记放到出队时，队列里会挤满重复元素，复杂度和正确性都会出问题。答案多半只给你核心循环，不会讲这么细，但把这两段代码放在一起对比着看一遍，比你单独背任何一个都要有效。

5. 避坑指南：使用这份答案时最常踩的五个坑

5.1 现象一：代码贴进IDE后编译报错

原因：答案基于老JDK书写，使用了新版本中已经过时的类，比如Vector，或者省略了泛型参数。现代IDE对新旧语法混用的兼容性不好，会直接报类型安全或编译错误。

解决：不要急着改代码逻辑。先把编译错误分类：如果是“找不到类”或“参数列表不一致”，大概率是API淘汰，替换成现在的集合类即可；如果是“类型不匹配”，大概率是泛型裸类型的问题，补上类型参数就行。把代码改到能编译之后，再去关注逻辑层面的东西。

5.2 现象二：运行结果和期望不一致

原因：答案文档在抄录过程中可能有笔误，或者教材在改版时对题目做了微调，答案没有同步跟上。也有人为因素：你可能把题号对应错了，做的是第3章的题却翻到了第4章答案。

解决：先用一组最小测试数据，不超过5个元素，手动算出正确结果，再断言看实际输出。比如链表反转，输入1-2-3，期望3-2-1，实际输出不同就逐步打印中间态，定位到第一个异常位置。如果测试数据足够小且结果仍对不上，那就是答案本身的问题，这时该根据你自己的理解来写正确实现，不要盲信文档。

5.3 现象三：复杂度分析和答案对不上

原因：大概率在数循环次数时，把外层和内层循环简单相乘，忽略了类似“子问题减半”或“数据量递减”的细节。另一常见情形是答案分析的是平均复杂度，而你默认它说的是最坏复杂度。

解决：把递归表达式T(n)=aT(n/b)+O(n)写出来再套主定理；如果是循环代码，逐行标注每条语句执行次数。不要跳步，推导题最忌讳的就是凭感觉。

5.4 现象四：递归实现一测试就爆栈

原因：教科书和答案代码默认演示数据规模很小，而你的测试数据通常远大于演示规模，导致递归深度过深。

解决：把递归改为显式栈的迭代实现，重点保持“入栈顺序”和“访问时机”两个不变量的正确。改完后同样用刚才的小数据先验证，再慢慢增大数据规模，这样可以确认迭代实现没有改变遍历或搜索语义。

5.5 现象五：答案代码逻辑正确，但很难复用

原因：答案方法通常不带泛型、不处理null、不检查空集合，这些在工程视角下都是不可接受的缺陷。若直接把答案代码搬进项目，后续维护会非常痛苦。

解决：在理解了算法之后，用现代工程风格重写一遍：加泛型、加null检查、把输入参数与返回值都用接口类型声明。重写不出bug，才能真正证明你看懂了答案的代码而不只是会粘贴。

6. 超越答案：把参考解法改造成个人代码资产

6.1 给每类题增加自我测试与性能记录

答案文档的最基本使用是“做一道对一道”，但真正让这些题目成为资产的做法，是给每一类题的解法加上自己的测试和运行记录。测试可以只是最普通的main方法，但运行时间、输入规模、输出结果——这几个数字一旦被记录，你就在提示自己：这类题的复杂度上限在哪里，遇到更大数据时震荡会出现在哪。

6.2 改变参数与边界条件，看看实现是否会碎

每当我消化一个答案，我会做三个小实验：把输入长度变为0；把输入元素全部相等；把输入顺序倒过来。这三个实验不一定出现在答案里，但能精准暴露一个实现是否稳健。链表反转遇到空链表会怎样？快速排序遇到全等元素会不会无限递归？堆删除遇到空堆会不会抛异常？答案文档常忽略这些边界，而你在实验中亲手照顾到它们，才是把“参考答案”变成“自己答案”的关键一步。

我一直保留一个习惯：读完一道题答案后，一天之内动手重写一遍，并且在重写时故意改动一个参数，比如把pivot取法换掉、把visited标记位置换掉，看代码会怎样变化。这个实验每次都让我更理解答案里哪些地方是必要约束、哪些只是当时作者的顺手选择。数据结构与算法的功力，并不来自于知道答案，而来自于知道答案的“为什么非得这样”。希望这篇文章能帮你把一份习题答案文档，真正变成自己知识体系里的一块稳定基石。希望帮到你。

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