Java数据结构与算法习题答案精讲与上机验证

简介《数据结构与算法分析Java语言描述》第三版习题答案文档面向正在学习数据结构、算法分析与Java程序设计的高校学生及自学者可用于课后对照练习、梳理证明思路与复习核心概念。压缩包内共1个docx文件大小约1.52MB内容以章节习题解答为主便于按知识点查阅和整理笔记。目前已有2435人学习下载具备一定的参考热度。文档覆盖递归算法、数学归纳法证明、数列求和、模运算与指数定律、大O符号及对数估计等主题并配有文件递归处理等代码示例可帮助读者理解算法分析中的推导过程、验证课后答案并补充课堂之外的计算复杂度分析思路。1. 一份习题答案解决的是“卡住”而不是“不会”期末前两周最费时间的往往不是写代码而是对着教材习题干瞪眼。这份《数据结构与算法分析Java 语言描述》第三版的习题答案文档内容涵盖递归写法、归纳法证明、大 O 推导、链表操作、栈与队列等章节的参考解答按题号组织遇到某道题怎么都想不通时直接翻到对应位置的答案比重新翻整章教材要省事得多。它适合正在跟进这门课、或准备 Java 数据结构面试的开发者把它当成“第二遍自学”的对照材料而不是只照着抄答案的底本。2. 先搞清这份答案的组织方式题号索引与三类题型的读法2.1 文件结构按章号加题号排列没有额外目录这份文档从第 1 章 Introduction 开始按CHAPTER 1、CHAPTER 2一直排到后面的 Lists, Stacks, and Queues每一章内部按题号顺序写解答例如 1.4、1.5、1.7、1.8、1.9、1.10、1.11、1.12然后是第 2 章的 2.1、2.2……直到 2.34。没有自动生成的目录页所以最稳妥的用法是在阅读器里打开书签或大纲视图按章号跳转而不是从头滚到底。文档里的解答有两种形态阅读时先分清再决定怎么用带完整 Java 代码的题比如 1.5 的ones(int n)、3.1 的printLots、3.2 的链表节点交换、3.4 的求交集、3.5 的求并集这类题要逐行读重点是方法签名和边界条件。纯数学推导的题比如 1.7 的归纳法、1.8 的求和、2.4 的对数极限、2.12 的规模换算这类题要对着自己的草稿一步步比确认哪一步是跳过去的。先做这个分类是因为这两类题的“读法”完全不同代码题对着 IDE 跑一遍最有效证明题光看是没用的必须自己重算一遍才会暴露盲点。2.2 代码类题的读法先看签名再看边界以 1.5 为例原文给的是public static int ones( int n ) { if( n 2 ) return n; return n % 2 ones( n / 2 ); }这段代码的作用是统计n的二进制表示里 1 的个数。逐行看n 2是递归出口此时n只可能是 0 或 1直接返回n本身就是答案n % 2取出最低位是 1 就贡献 1是 0 就贡献 0ones(n / 2)把问题缩小到去掉最低位之后的数。参数只有int n负数在这个实现里是没有处理的传入负数会得到错误结果这是读这段代码时最容易忽略的地方。再看 3.2 的单链表交换原文注释写得很明确传入的是“要交换的两个相邻节点前面的那个节点”public static void swapWithNext( Node beforep ) { Node p, afterp; p beforep.next; afterp p.next; // Both p and afterp assumed not null. p.next afterp.next; beforep.next afterp; afterp.next p; }三行指针操作是有顺序讲究的先把p的 next 指向afterp的后继保住后半段链表再让beforep指向afterp最后让afterp指向p。如果第一步和第三步调换p.next会先被覆盖后半段链表就直接丢了。原文注释里的 “Both p and afterp assumed not null” 是明确的警告这段代码没有做任何空指针检查调用前必须自己保证。双链表版本的差异在于多维护两条反向指针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本身而不是beforep这个容易混。读这类题时建议在纸上画出三个节点的框和四条箭头跟着代码每执行一行就擦掉重画一次比在脑子里空想可靠得多。2.3 证明类题的读法抓住“假设了什么、用在哪一步”1.7(a) 是对数不等式的归纳证明。它的结构是标准的先验证0 X 1和1 X 2两个基础区间然后假设命题对p X 2p成立再去证2p Y 4p。关键的一步是log Y 1 log(Y/2)这里把 Y 折半塞进了归纳假设的区间然后再用Y/2 Y/2 Y/2 Y收尾。读这类题最常犯的错是背结论。正确的做法是遮住答案自己写一遍“基础情况 → 归纳假设 → 归纳步骤”三段卡在哪一步再看答案对应位置。如果发现自己是卡在“为什么想到把 Y 折半”那就说明这个技巧没内化需要在旁边标注遇到2p Y 4p这种区间翻倍的结构优先尝试把上界折半落回已知区间。2.4 的对数阶比较用的是洛必达法则lim log^i N / N反复求导把对数的幂次逐层打掉这是“同一个 N 的高阶对数是低阶对数的低阶无穷”的标准证法。2.3 则用反证法假设N log N更慢两边取对数导出矛盾。这两道题的共同点是证明过程本身就是结论的推导路径跳过推导只记结论换个题面就不会做了。2.4 建议的刷题顺序拿到这份文档后合理的节奏是按章推进而不是按题号刷。第 1 章的题偏数学基础求和、归纳、模运算第 2 章进入复杂度分析第 3 章才开始真正的链表代码。数学基础不牢的话第 2 章的 2.3、2.4、2.12 会非常吃力所以建议阶段覆盖题号目标第一轮1.5、1.8、1.10、1.12把递归写法、求和技巧、模运算过一遍第二轮1.7、1.9、2.3、2.4归纳法与对数阶比较必须手写第三轮2.7、2.12、2.22、2.24复杂度估算与快速幂配合代码验证第四轮3.1–3.6链表操作全部上机跑通第 2 章的 2.7 值得单独提一句题目分析了几段嵌套循环的复杂度其中第 (VI) 段的注释明确指出“把循环大小相乘有时会高估”因为最内层虽然被外层包了 N 的三次方次但真正进入内层的只有 O(N²) 次。这种“循环嵌套层数不等于复杂度阶数”的例子只看结论记不住必须自己数一遍执行次数。3. 把答案跑起来本地复现环境与验证步骤3.1 环境准备JDK 与一个能建多文件的项目这份文档里的代码都是标准 Java没有依赖任何第三方库所以一个能编译运行多文件的最小环境就够。常见做法是 JDK 17 或 JDK 21 加一个 IDE 项目如果你习惯命令行只要保证javac和java可用即可。先验证环境java -version javac -version两条命令输出版本号一致说明 JDK 装对了。如果javac提示找不到命令多半是只装了 JRE 或者 PATH 没配到 JDK 的 bin 目录这种情况在 Windows 上尤其常见。接下来建一个目录把答案里的代码按章拆成独立文件。不建议把所有题塞进一个Main.java因为 3.2 里单链表和双链表各有一个同名方法swapWithNext签名还不一样塞在一起会冲突。推荐的结构是每一题一个类或者一章一个包mkdir -p dsa-answers/ch03 cd dsa-answers3.2 把链表题的骨架补全再跑原文给出的链表操作只贴了方法体没有给出Node类的定义和链表的构造代码。要跑通得自己补一层最小骨架。以 3.2 的单链表为例public class SinglySwap { // 节点定义答案里默认存在实际复现时必须自己写 static class Node { int data; Node next; Node(int data) { this.data data; } } // 与答案一致传入待交换两节点中的前一个节点 public static void swapWithNext(Node beforep) { Node p beforep.next; Node afterp p.next; p.next afterp.next; beforep.next afterp; afterp.next p; } public static void main(String[] args) { Node head new Node(0); // 哑节点简化头插头删 head.next new Node(1); head.next.next new Node(2); head.next.next.next new Node(3); swapWithNext(head); // 交换 1 和 2 for (Node cur head.next; cur ! null; cur cur.next) { System.out.print(cur.data ); // 期望输出 2 1 3 } } }编译运行javac SinglySwap.java java SinglySwap输出的2 1 3就是判定代码抄对了的信号。这里有两个参数层面的注意点beforep不能是null也不能是链表最后一个节点否则p.next取值时直接抛空指针另外我在链表头加了一个哑节点是因为答案里的swapWithNext假设beforep.next一定存在如果要从头节点开始交换没有哑节点就得单独处理头指针的更新反而更绕。双链表版本需要多写prev字段并且初始化和交换后的prev一致性要额外校验建议在交换后从尾部往前再遍历一遍确认反向链路没断static class DNode { int data; DNode prev, next; DNode(int data) { this.data data; } } public static void swapWithNext(DNode p) { DNode 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、p.prev、p.next三者都不为空这段代码对边界完全没有防御。3.3 用快速幂题做一次“答案对照式验证”2.22 和 2.23 讲的是快速幂用X²、X⁴、X⁸……逐次平方再按 N 的二进制位挑选相乘把 O(N) 的乘法次数降到 O(log N)。这道题最适合用来验证“自己写的和答案思路是否一致”因为它有明确的可测行为public class FastPow { // 迭代版快速幂对应 2.23 的数组思路 public static long pow(long x, int n) { long result 1; long base x; while (n 0) { if ((n 1) 1) result * base; // 当前二进制位为 1 则累乘 base * base; // 平方对应 X^2, X^4, X^8... n 1; // 右移考察下一位 } return result; } public static void main(String[] args) { // 用暴力版做对照小规模输入下两者必须一致 for (int n 0; n 20; n) { long fast pow(3, n); long slow 1; for (int i 0; i n; i) slow * 3; if (fast ! slow) throw new AssertionError(mismatch at n n); } System.out.println(all pass); } }参数上要注意long的溢出边界3的 20 次方已经接近 35 亿如果想测更大的 n得换BigInteger否则对照会失败但代码其实是对的。这也是 2.24 那道题在讨论“乘法次数”时默认数值不大的原因。跑出all pass之后再去读 2.24 里floor(log N) b(N) - 1这个乘法次数公式就能对上号了b(N)是二进制里 1 的个数每次遇到 1 做一次乘法平方操作固定做floor(log N)次。3.4 递归题的上机验证把递归树打出来1.5 的ones和 1.4 的processFile都是递归。递归写完后最常见的困惑是“它到底怎么走进去又怎么退出来”光看代码想不明白。一个很实用的调试习惯是在函数入口打印缩进public static int ones(int n, int depth) { System.out.println( .repeat(depth) ones( n )); if (n 2) return n; return n % 2 ones(n / 2, depth 1); }传ones(13, 0)会打印出一条逐步收缩的调用链13 → 6 → 3 → 1一眼就能看出递归深度和出口位置。注意这个加了depth的版本只是调试用跟原文签名不同别把它当成标准答案。调完删掉打印即可。4. 避坑与常见问题这份答案文档最容易踩的五个坑4.1 坑一直接复制代码编译报“找不到符号 Node”现象把 3.2、3.3、3.4 的方法粘进 IDE满屏红线提示Node、ListIterator、AnyType无法解析。原因答案文档只给了核心方法体节点类、迭代器导入、泛型声明这些周边代码是为了节省篇幅省略的它默认读者手上已经有教材配套的代码框架。解决自己补最小可编译单元Node写成静态内部类用到迭代器的加import java.util.*;泛型方法保持AnyType extends Comparable? super AnyType原样。补的时候只补需要的字段不要顺手把整本书的框架都搬进来。4.2 坑二没注意到签名差异单双链表方法调错现象单链表和双链表各有一个swapWithNext单链表版传的是beforep双链表版传的是p把两者混用后链表结构乱掉或者直接空指针。原因两段代码同名不同参文档里没有做合并说明快速翻页时很容易看串。解决复制代码时连同一行注释一起复制注释里的 “beforeP is the cell before” 就是参数语义的说明书。更稳的做法是给自己的复现版本改个名比如swapWithNextSingly和swapWithNextDoubly从源头断掉混用可能。4.3 坑三把 2.7 的复杂度结论当成通用规则记现象看到嵌套三层循环就判 O(N³)回头对照 2.7 的第 (VI) 段发现答案给的是 O(N⁴)或者反过来把某段多层循环判高了。原因2.7 第 (VI) 段的注释说得很直白循环变量乘积只是上界if实际成立的次数只有 O(N²)最内层真正执行的次数远小于乘积。复杂度取决于“实际执行次数”而不是“循环写了几层”。解决判定前先回答一个问题最内层的语句实际会执行多少次。像 2.7 这种带条件判断的嵌套必须先数条件成立次数再去乘内层代价。2.12 的规模换算题也是同一类它算的是“时间乘以常数后输入规模能扩到多大”前提是时间复杂度阶数已经确定。4.4 坑四归纳法证明跳过基础情况现象自己写 1.7、1.11、1.12 的证明时直接从归纳假设往下推被老师或面试官问“N1 时成立吗”答不上来。原因答案文档里基础情况的篇幅很短一句话带过容易被当作不重要的部分略读。但归纳法如果基础情况不成立整个链条都是空的。解决每次写归纳证明强制第一行写基础情况并显式验算。1.12(b) 的立方和证明里N1 时等式两边都是 1这一步只要一行但不写就是扣分点。4.5 坑五负数输入让递归函数静默出错现象把 1.5 的ones拿去统计负数的二进制 1 个数返回结果对不上。原因n % 2和n / 2在 Java 里对负数的行为和直觉不一致-3 % 2是-1不是1递归会往错误的方向收缩。解决在入口加一行判断或者用Integer.bitCount对照测试。如果是为了理解递归而手写至少要在注释里写明“该实现仅适用于非负整数”别让下一个人踩同一个坑。5. 进阶用法把答案变成可回归的本地题库答案的价值不止在“看”更在于把它转成一套能反复跑的自测题库这样复习两轮以上时直接跑测试看哪里还能过、哪里已经忘了比重新翻书快得多。先做一层最小化的测试封装。以第 3 章的链表题为例把每道题的核心行为写成一个断言方法用main统一调度public class Ch03Checklist { static void check(String name, Runnable test) { try { test.run(); System.out.println([PASS] name); } catch (Throwable t) { System.out.println([FAIL] name - t.getMessage()); } } public static void main(String[] args) { check(3.2 单链表相邻交换, () - { // 构造 0-1-2-3交换后应得到 0-2-1-3 // 调用 swapWithNext 后断言数据序列不一致则抛异常 }); check(3.4 有序链表求交集, () - { // 两路归并式求交断言结果列表内容与预期一致 }); check(3.5 有序链表求并集, () - { // 断言元素不重复且全部覆盖 }); } }这样做的关键是把“答案对不对”变成机器可判定的问题。check方法把异常转成[FAIL]不会因为一个用例挂掉就中断后面所有用例跑一次能看到全貌。每一题在 lambda 里只做三件事构造输入、调用被测方法、断言输出。断言用Objects.equals或自己写的比对不要只打印不校验打印出来的结果还得肉眼比就失去了自动化的意义。再往上走一步用 JUnit 5 替换手写的check把每章做成一个测试类测试类覆盖内容断言重点Ch01MathTest1.8 求和、1.10 模幂、1.12 求和公式数值结果精确相等Ch02ComplexityTest2.22/2.23 快速幂、2.24 乘法次数与暴力版逐项对照Ch03ListTest3.1 打印指定位置、3.2 交换、3.4/3.5 交并集链表结构和元素序列一致写测试时有几个参数层面的细节值得注意。第一快速幂的测试上限要卡在long不溢出之前否则会得到“代码对但断言挂”的假失败。第二链表测试要用带哑节点的构造方式这样交换、删除、插入都不用特判头节点测试代码会短很多。第三求交集和求并集的测试要专门覆盖空链表、其中一条为空、两条完全无交集这三种边界答案里的实现是两路归并式遍历空链表是最容易让迭代器越界的地方。我自己的习惯是每复习完一章就在测试类里补两三个用例尤其是那些做错过的题用例要能复现当时的错误。第一遍复习时因为忽略空链表在求并集上翻车后来每次重构链表代码我都会先跑一遍空链表用例再动别的。这种“用错误换来的用例”比从书上抄来的题更值钱。这套题库还能反向使用面试前不看答案先扫一遍测试类名字能想起来每道题的思路就跳过想不起来的再去文档里定位题号。文档负责“查到”题库负责“验证”两者配合比单看答案牢固得多。希望这个思路帮到你。本文还有配套的精品资源点击获取