简介这份文档是《数据结构与算法分析Java语言描述》第三版的配套习题答案面向正在学习数据结构与算法课程的高校学生、考研备考者以及需要巩固Java编程基础的开发者帮助解决课后习题无从下手、答案难以验证的问题。资源包内含1个docx文件大小约1.52MB内容以文字与代码片段为主覆盖递归、数学归纳法、文件处理、数列求和、模运算、大O符号与对数估计等核心知识点。例如processFile的递归文件包含处理、ones函数求个位数之和、对数性质的归纳证明、等比数列差分求和技巧以及2^100模5的指数定律应用均配有完整推导与代码示例。目前已有2429人学习下载适合作为课后对照、考前复习与算法思维训练的自查材料也可用于理解算法复杂度分析的数学基础。1. 从一份第三版习题答案说起Java 数据结构与算法分析的落地价值很多人学《数据结构与算法分析Java 语言描述》第三版时卡住的不是概念而是课后那几十道证明题和代码题——递归怎么写、大 O 怎么推、链表怎么换指针光看正文觉得懂了一动手就翻车。这份习题答案文档覆盖了第 1 到第 3 章的核心题目从文件递归处理、二进制位计数到数学归纳法证明对数不等式、数列求和、模运算再到链表节点交换、有序链表求交集与并集全部给出了可对照的代码和推导过程。它适合正在跟这本教材自学的开发者、准备数据结构相关考核的从业者以及需要快速核对课后题思路的人。下面我按“这份答案里有什么 → 怎么对照复现 → 哪些地方容易踩坑”的顺序拆一遍。2. 递归与数学推理题从 processFile 到 ones 函数的对照复现2.1 文件递归处理processFile 的设计逻辑与自引用检测第 1 章 1.4 题要求写一个processFile(String fileName)过程打开文件、执行处理、关闭文件如果读到#include SomeFile这样的行就递归调用processFile(SomeFile)。答案里还补了一个关键细节用一张“尚未返回的调用列表”来检测自引用包含避免无限递归。这个思路在真实项目里对应的是配置文件嵌套解析、模板 include 展开等场景。我一般会这样落地import java.io.*; import java.util.*; public class FileProcessor { // 记录当前调用链上尚未处理完的文件用于检测循环 include private SetString activeFiles new HashSet(); public void processFile(String fileName) throws IOException { // 如果文件已在当前调用链中说明出现自引用直接报错 if (activeFiles.contains(fileName)) { throw new IllegalStateException(Self-referential include: fileName); } activeFiles.add(fileName); try (BufferedReader br new BufferedReader(new FileReader(fileName))) { String line; while ((line br.readLine()) ! null) { if (line.startsWith(#include )) { String included line.substring(#include .length()).trim(); processFile(included); // 递归处理被包含文件 } else { // 这里放实际的业务处理逻辑 System.out.println(line); } } } finally { activeFiles.remove(fileName); // 退出时移除保证同层可重复包含 } } }逻辑说明activeFiles用Set保存当前递归路径上的文件名进入时检查、加入退出时移除。参数上唯一需要改的是#include的解析规则——如果目标格式是#include xxx带引号substring之后还要去掉首尾引号。常见做法是把解析逻辑抽成独立方法方便替换成正则。2.2 ones 函数二进制位计数的递归写法与边界1.5 题的ones(int n)用递归统计 n 的二进制表示中 1 的个数public static int ones(int n) { if (n 2) return n; // 0 或 1 直接返回 return n % 2 ones(n / 2); // 当前最低位 剩余位的计数 }这个写法等价于每次取最低位、右移一位。参数上要注意n 为负数时n % 2在 Java 里可能得到 -1所以实际工程中通常先做n Math.abs(n)或直接用Integer.bitCount(n)。答案给的是教学版复现时建议补上负数处理否则测试用例一跑就暴露。2.3 数学归纳法与数列求和1.7 到 1.12 的推导怎么核对1.7(a) 用归纳法证明 log X XX 0分三段0 X ≤ 1、1 X ≤ 2、2p Y ≤ 4p。核对时重点看第二步到第三步的过渡——它用了log Y 1 log(Y/2) 1 Y/2 Y/2 Y/2 Y这里的放缩是整道题的关键。1.8 的数列求和用了“错位相减”技巧比如 (b) 中 S 1 2/4 3/16 …两边乘 4 再相减得到 3S 4/3所以 S 4/9。1.12(b) 证明 Σi³ [N(N1)/2]² 时把 (N1)³ 拆进归纳假设最后配成完全平方。这些推导在文档里是纯文本公式排版可能错位。我建议对照时自己用纸笔重推一遍尤其是 1.8(c) 和 1.12(b) 的中间步骤文档里的分数和指数容易看串行。3. 算法分析题大 O 排序、运行时间估算与随机置换3.1 增长率排序2.1 题的完整序列与易混点2.1 题要求把一组函数按增长率排序答案给出的顺序是2/N, 37, √N, N, N log log N, N log N, N log(N²), N log²N, N¹·⁵, N², N² log N, N³, 2^(N/2), 2^N。其中特别标注了 N log N 和 N log(N²) 同阶因为 log(N²) 2 log N只差常数因子。核对时容易出错的是 N log²N 和 N¹·⁵ 的先后——log²N 增长慢于 N⁰·⁵所以 N log²N 排在 N¹·⁵ 前面。这个排序在面试里也常被问到建议把每个函数的增长速度记成“对数 多项式 指数”三层来记。3.2 运行时间估算2.9 题的数量级换算2.9 题给了一组具体数字算法 1 在 N10000 时约 38 分钟N100000 时约 26 天在 N100 万时算法 1 到 4 分别约 72 年、4 小时、0.7 秒、0.03 秒。这些数字的前提是“机器有足够内存放下整个数组”。复现时如果内存不够算法 3 和 4 会因为换页而急剧变慢这也是答案里专门提醒的一点。3.3 随机置换2.8 题三种算法的正确性与复杂度2.8 题讨论了三种生成随机置换的算法。第一种每次随机取数、检查是否用过期望尝试次数是 N/(N-i)总时间 O(N log N)第二种省掉内层检查平均 O(N log N)第三种是 Floyd 算法线性时间。答案特别指出如果把第三种算法的第二行改成swapReferences(a[i], a[randint(0, n-1)])就不再是等概率置换——因为 N3 时 27 种等可能交换无法均匀分给 6 种排列。这个坑我在写洗牌逻辑时踩过看起来只是随机范围从[0, i]改成[0, n-1]实际上破坏了等概率性。复现时建议用 N3 跑一万次统计频率能直观看到偏差。4. 链表操作题swapWithNext、交集与并集的代码复现4.1 单链表与双链表的节点交换3.2 题给出了单链表和双链表的swapWithNext。单链表版本// beforep 是要交换的两个相邻节点的前驱 public static void swapWithNext(Node beforep) { Node p, afterp; p beforep.next; afterp p.next; // 假定 p 和 afterp 都不为 null p.next afterp.next; beforep.next afterp; afterp.next p; }双链表版本多了prev指针的维护public static void swapWithNext(Node p) { Node beforep, afterp; beforep p.prev; afterp p.next; p.next afterp.next; beforep.next afterp; afterp.next p; p.next.prev p; p.prev afterp; afterp.prev beforep; }参数说明单链表版本传的是前驱节点双链表版本传的是要交换的第一个节点本身。复现时最容易翻车的是双链表里p.next.prev p这一句——如果afterp.next为 null即 afterp 是尾节点这行会抛空指针。答案里写了“错误检查省略”实际用时必须补上if (afterp.next ! null)。4.2 有序链表求交集与并集双指针同步扫描3.4 和 3.5 题分别用ListIterator实现两个有序链表的交集和并集。核心逻辑是双指针同步扫描比较当前两个元素相等时交集加入结果、并集也加入不等时较小的一方加入并集、指针后移。交集版本在相等时两个指针都后移并集版本在不等时只移动较小的一侧。复现时要注意ListIterator的hasNext()和next()配合——答案里用iterL1.hasNext() ? iterL1.next() : null来避免越界这个写法在链表长度不等时能正确终止循环。如果换成数组下标逻辑一样但边界条件要重新推一遍。4.3 Josephus 问题的优化M mod N 与方向选择3.6 题讨论 Josephus 问题答案给了两个优化一是 M 距离等于 M mod N 距离当 M 大于当前剩余人数时二是向前 M 距离等于向后 (M-N) 距离当 M 超过一半时。这两个优化把最坏时间复杂度从 O(NM) 降到 O(N·min(M, N))。复现时建议先用朴素版跑小数据验证结果再换优化版对比性能。5. 避坑与排查对照习题答案时最容易翻车的五个点5.1 现象processFile 递归跑着跑着栈溢出原因自引用检测只检查了直接包含没有覆盖 A 包含 B、B 又包含 A 的间接循环。 解决activeFiles必须在进入时加入、退出时移除且检查发生在递归调用之前而不是在打开文件之后。5.2 现象ones 函数对负数返回错误结果原因Java 中-3 % 2等于 -1累加后结果偏移。 解决入口处取绝对值或改用Integer.bitCount(n)如果必须手写用n 1代替n % 2。5.3 现象双链表 swapWithNext 在尾节点处抛空指针原因p.next.prev p在p.next为 null 时触发 NPE。 解决交换前判断afterp.next ! null或在链表实现里加哨兵尾节点保证next永不为 null。5.4 现象大 O 排序把 N log²N 排在 N¹·⁵ 后面原因误以为 log²N 增长快于 N⁰·⁵。 解决取 N10⁶ 代入log²N ≈ 400N⁰·⁵ ≈ 1000所以 N log²N 更小、排前面。5.5 现象随机置换统计频率不均匀原因洗牌时随机范围用了[0, n-1]而不是[0, i]。 解决Floyd 算法或 Fisher-Yates 的正确写法是每次从[0, i]取随机数保证每一步等概率。6. 进阶用法把习题答案变成可运行的测试用例这份答案最大的价值不是“看”而是“跑”。我习惯把每道代码题抽成一个独立类配一组 JUnit 测试用边界值反推答案是否正确。比如ones函数测试用例至少覆盖0、1、2、3、7、8、Integer.MAX_VALUE、负数。链表交换则构造长度为 0、1、2、3 的链表分别测头、中、尾三种位置。下面是一个把 3.4 交集逻辑转成测试的示例import org.junit.Test; import java.util.*; import static org.junit.Assert.*; public class ListIntersectionTest { Test public void testIntersection() { ListInteger L1 Arrays.asList(1, 3, 5, 7, 9); ListInteger L2 Arrays.asList(3, 4, 5, 8, 9); ListInteger result new ArrayList(); // 调用答案中的 intersection 方法 intersection(L1, L2, result); assertEquals(Arrays.asList(3, 5, 9), result); } Test public void testEmptyInput() { ListInteger result new ArrayList(); intersection(Collections.emptyList(), Arrays.asList(1, 2), result); assertTrue(result.isEmpty()); } }参数说明intersection要求两个输入链表已排序否则双指针逻辑不成立。测试里特意加了空链表用例因为答案代码在iterL1.hasNext() iterL2.hasNext()为 false 时直接跳过初始化后续循环条件用itemL1 ! null判断空输入能正确返回空结果。另一个进阶用法是把 2.8 的随机置换算法写成基准测试用 JMH 对比三种实现在 N1000、10000、100000 下的吞吐量。我一般会固定随机种子跑五轮取中位数避免 JIT 预热带来的波动。这样能把“答案说 O(N log N)”变成“实测数据确实接近线性对数”。从那以后我每次对照习题答案都强制先把代码抽出来跑一遍边界用例再回头看推导——纸上的归纳法证明和机器上的空指针往往是同一道题的两面。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/9 11:38:18 · 阅读 1.2k Java数据结构与算法分析第三版习题答案：递归、大O与链表操作复现
简介这份文档是《数据结构与算法分析Java语言描述》第三版的配套习题答案面向正在学习数据结构与算法课程的高校学生、考研备考者以及需要巩固Java编程基础的开发者帮助解决课后习题无从下手、答案难以验证的问题。资源包内含1个docx文件大小约1.52MB内容以文字与代码片段为主覆盖递归、数学归纳法、文件处理、数列求和、模运算、大O符号与对数估计等核心知识点。例如processFile的递归文件包含处理、ones函数求个位数之和、对数性质的归纳证明、等比数列差分求和技巧以及2^100模5的指数定律应用均配有完整推导与代码示例。目前已有2429人学习下载适合作为课后对照、考前复习与算法思维训练的自查材料也可用于理解算法复杂度分析的数学基础。1. 从一份第三版习题答案说起Java 数据结构与算法分析的落地价值很多人学《数据结构与算法分析Java 语言描述》第三版时卡住的不是概念而是课后那几十道证明题和代码题——递归怎么写、大 O 怎么推、链表怎么换指针光看正文觉得懂了一动手就翻车。这份习题答案文档覆盖了第 1 到第 3 章的核心题目从文件递归处理、二进制位计数到数学归纳法证明对数不等式、数列求和、模运算再到链表节点交换、有序链表求交集与并集全部给出了可对照的代码和推导过程。它适合正在跟这本教材自学的开发者、准备数据结构相关考核的从业者以及需要快速核对课后题思路的人。下面我按“这份答案里有什么 → 怎么对照复现 → 哪些地方容易踩坑”的顺序拆一遍。2. 递归与数学推理题从 processFile 到 ones 函数的对照复现2.1 文件递归处理processFile 的设计逻辑与自引用检测第 1 章 1.4 题要求写一个processFile(String fileName)过程打开文件、执行处理、关闭文件如果读到#include SomeFile这样的行就递归调用processFile(SomeFile)。答案里还补了一个关键细节用一张“尚未返回的调用列表”来检测自引用包含避免无限递归。这个思路在真实项目里对应的是配置文件嵌套解析、模板 include 展开等场景。我一般会这样落地import java.io.*; import java.util.*; public class FileProcessor { // 记录当前调用链上尚未处理完的文件用于检测循环 include private SetString activeFiles new HashSet(); public void processFile(String fileName) throws IOException { // 如果文件已在当前调用链中说明出现自引用直接报错 if (activeFiles.contains(fileName)) { throw new IllegalStateException(Self-referential include: fileName); } activeFiles.add(fileName); try (BufferedReader br new BufferedReader(new FileReader(fileName))) { String line; while ((line br.readLine()) ! null) { if (line.startsWith(#include )) { String included line.substring(#include .length()).trim(); processFile(included); // 递归处理被包含文件 } else { // 这里放实际的业务处理逻辑 System.out.println(line); } } } finally { activeFiles.remove(fileName); // 退出时移除保证同层可重复包含 } } }逻辑说明activeFiles用Set保存当前递归路径上的文件名进入时检查、加入退出时移除。参数上唯一需要改的是#include的解析规则——如果目标格式是#include xxx带引号substring之后还要去掉首尾引号。常见做法是把解析逻辑抽成独立方法方便替换成正则。2.2 ones 函数二进制位计数的递归写法与边界1.5 题的ones(int n)用递归统计 n 的二进制表示中 1 的个数public static int ones(int n) { if (n 2) return n; // 0 或 1 直接返回 return n % 2 ones(n / 2); // 当前最低位 剩余位的计数 }这个写法等价于每次取最低位、右移一位。参数上要注意n 为负数时n % 2在 Java 里可能得到 -1所以实际工程中通常先做n Math.abs(n)或直接用Integer.bitCount(n)。答案给的是教学版复现时建议补上负数处理否则测试用例一跑就暴露。2.3 数学归纳法与数列求和1.7 到 1.12 的推导怎么核对1.7(a) 用归纳法证明 log X XX 0分三段0 X ≤ 1、1 X ≤ 2、2p Y ≤ 4p。核对时重点看第二步到第三步的过渡——它用了log Y 1 log(Y/2) 1 Y/2 Y/2 Y/2 Y这里的放缩是整道题的关键。1.8 的数列求和用了“错位相减”技巧比如 (b) 中 S 1 2/4 3/16 …两边乘 4 再相减得到 3S 4/3所以 S 4/9。1.12(b) 证明 Σi³ [N(N1)/2]² 时把 (N1)³ 拆进归纳假设最后配成完全平方。这些推导在文档里是纯文本公式排版可能错位。我建议对照时自己用纸笔重推一遍尤其是 1.8(c) 和 1.12(b) 的中间步骤文档里的分数和指数容易看串行。3. 算法分析题大 O 排序、运行时间估算与随机置换3.1 增长率排序2.1 题的完整序列与易混点2.1 题要求把一组函数按增长率排序答案给出的顺序是2/N, 37, √N, N, N log log N, N log N, N log(N²), N log²N, N¹·⁵, N², N² log N, N³, 2^(N/2), 2^N。其中特别标注了 N log N 和 N log(N²) 同阶因为 log(N²) 2 log N只差常数因子。核对时容易出错的是 N log²N 和 N¹·⁵ 的先后——log²N 增长慢于 N⁰·⁵所以 N log²N 排在 N¹·⁵ 前面。这个排序在面试里也常被问到建议把每个函数的增长速度记成“对数 多项式 指数”三层来记。3.2 运行时间估算2.9 题的数量级换算2.9 题给了一组具体数字算法 1 在 N10000 时约 38 分钟N100000 时约 26 天在 N100 万时算法 1 到 4 分别约 72 年、4 小时、0.7 秒、0.03 秒。这些数字的前提是“机器有足够内存放下整个数组”。复现时如果内存不够算法 3 和 4 会因为换页而急剧变慢这也是答案里专门提醒的一点。3.3 随机置换2.8 题三种算法的正确性与复杂度2.8 题讨论了三种生成随机置换的算法。第一种每次随机取数、检查是否用过期望尝试次数是 N/(N-i)总时间 O(N log N)第二种省掉内层检查平均 O(N log N)第三种是 Floyd 算法线性时间。答案特别指出如果把第三种算法的第二行改成swapReferences(a[i], a[randint(0, n-1)])就不再是等概率置换——因为 N3 时 27 种等可能交换无法均匀分给 6 种排列。这个坑我在写洗牌逻辑时踩过看起来只是随机范围从[0, i]改成[0, n-1]实际上破坏了等概率性。复现时建议用 N3 跑一万次统计频率能直观看到偏差。4. 链表操作题swapWithNext、交集与并集的代码复现4.1 单链表与双链表的节点交换3.2 题给出了单链表和双链表的swapWithNext。单链表版本// beforep 是要交换的两个相邻节点的前驱 public static void swapWithNext(Node beforep) { Node p, afterp; p beforep.next; afterp p.next; // 假定 p 和 afterp 都不为 null p.next afterp.next; beforep.next afterp; afterp.next p; }双链表版本多了prev指针的维护public static void swapWithNext(Node p) { Node beforep, afterp; beforep p.prev; afterp p.next; p.next afterp.next; beforep.next afterp; afterp.next p; p.next.prev p; p.prev afterp; afterp.prev beforep; }参数说明单链表版本传的是前驱节点双链表版本传的是要交换的第一个节点本身。复现时最容易翻车的是双链表里p.next.prev p这一句——如果afterp.next为 null即 afterp 是尾节点这行会抛空指针。答案里写了“错误检查省略”实际用时必须补上if (afterp.next ! null)。4.2 有序链表求交集与并集双指针同步扫描3.4 和 3.5 题分别用ListIterator实现两个有序链表的交集和并集。核心逻辑是双指针同步扫描比较当前两个元素相等时交集加入结果、并集也加入不等时较小的一方加入并集、指针后移。交集版本在相等时两个指针都后移并集版本在不等时只移动较小的一侧。复现时要注意ListIterator的hasNext()和next()配合——答案里用iterL1.hasNext() ? iterL1.next() : null来避免越界这个写法在链表长度不等时能正确终止循环。如果换成数组下标逻辑一样但边界条件要重新推一遍。4.3 Josephus 问题的优化M mod N 与方向选择3.6 题讨论 Josephus 问题答案给了两个优化一是 M 距离等于 M mod N 距离当 M 大于当前剩余人数时二是向前 M 距离等于向后 (M-N) 距离当 M 超过一半时。这两个优化把最坏时间复杂度从 O(NM) 降到 O(N·min(M, N))。复现时建议先用朴素版跑小数据验证结果再换优化版对比性能。5. 避坑与排查对照习题答案时最容易翻车的五个点5.1 现象processFile 递归跑着跑着栈溢出原因自引用检测只检查了直接包含没有覆盖 A 包含 B、B 又包含 A 的间接循环。 解决activeFiles必须在进入时加入、退出时移除且检查发生在递归调用之前而不是在打开文件之后。5.2 现象ones 函数对负数返回错误结果原因Java 中-3 % 2等于 -1累加后结果偏移。 解决入口处取绝对值或改用Integer.bitCount(n)如果必须手写用n 1代替n % 2。5.3 现象双链表 swapWithNext 在尾节点处抛空指针原因p.next.prev p在p.next为 null 时触发 NPE。 解决交换前判断afterp.next ! null或在链表实现里加哨兵尾节点保证next永不为 null。5.4 现象大 O 排序把 N log²N 排在 N¹·⁵ 后面原因误以为 log²N 增长快于 N⁰·⁵。 解决取 N10⁶ 代入log²N ≈ 400N⁰·⁵ ≈ 1000所以 N log²N 更小、排前面。5.5 现象随机置换统计频率不均匀原因洗牌时随机范围用了[0, n-1]而不是[0, i]。 解决Floyd 算法或 Fisher-Yates 的正确写法是每次从[0, i]取随机数保证每一步等概率。6. 进阶用法把习题答案变成可运行的测试用例这份答案最大的价值不是“看”而是“跑”。我习惯把每道代码题抽成一个独立类配一组 JUnit 测试用边界值反推答案是否正确。比如ones函数测试用例至少覆盖0、1、2、3、7、8、Integer.MAX_VALUE、负数。链表交换则构造长度为 0、1、2、3 的链表分别测头、中、尾三种位置。下面是一个把 3.4 交集逻辑转成测试的示例import org.junit.Test; import java.util.*; import static org.junit.Assert.*; public class ListIntersectionTest { Test public void testIntersection() { ListInteger L1 Arrays.asList(1, 3, 5, 7, 9); ListInteger L2 Arrays.asList(3, 4, 5, 8, 9); ListInteger result new ArrayList(); // 调用答案中的 intersection 方法 intersection(L1, L2, result); assertEquals(Arrays.asList(3, 5, 9), result); } Test public void testEmptyInput() { ListInteger result new ArrayList(); intersection(Collections.emptyList(), Arrays.asList(1, 2), result); assertTrue(result.isEmpty()); } }参数说明intersection要求两个输入链表已排序否则双指针逻辑不成立。测试里特意加了空链表用例因为答案代码在iterL1.hasNext() iterL2.hasNext()为 false 时直接跳过初始化后续循环条件用itemL1 ! null判断空输入能正确返回空结果。另一个进阶用法是把 2.8 的随机置换算法写成基准测试用 JMH 对比三种实现在 N1000、10000、100000 下的吞吐量。我一般会固定随机种子跑五轮取中位数避免 JIT 预热带来的波动。这样能把“答案说 O(N log N)”变成“实测数据确实接近线性对数”。从那以后我每次对照习题答案都强制先把代码抽出来跑一遍边界用例再回头看推导——纸上的归纳法证明和机器上的空指针往往是同一道题的两面。希望帮到你。本文还有配套的精品资源点击获取