Java数据结构与算法分析复习：递归、复杂度与链表栈队列

简介：《数据结构与算法分析（Java语言描述）》（第三版）习题答案文档，面向正在学习数据结构、算法分析与Java程序设计的高校学生及自学者，用于对照教材习题梳理解题思路、巩固递归与复杂度分析等核心概念。压缩包共1个文件，为docx格式，大小约1.52MB，单文档集中收录多道习题的解答与推导过程。内容覆盖递归实现个位数求和、文件包含关系的递归处理、数学归纳法证明对数性质、等比与差分技巧数列求和、模运算与指数定律，以及大O符号和对数估计等知识点，并涉及Fibonacci数列相关归纳证明，便于读者按章节查漏补缺、理解证明步骤与算法构造。目前已有2435人学习，适合作为课程复习和习题订正的参考材料。

1. Java 数据结构与算法分析的复习起点：这份第三版习题答案到底覆盖了什么

很多人翻开这份《数据结构与算法分析（Java 语言描述）》第三版的习题答案，第一反应是从第 1 题抄到最后一题，抄完却说不清自己复习了哪几块。按知识模块重新排列，整份答案其实只有三条主线：第一条是递归与数学准备（文件递归处理、二进制位计数、归纳法证明、数列求和、模运算），它决定了你能不能看懂后面的推导；第二条是算法分析（增长率排序、大 O 判断、循环嵌套估算、期望分析、快速幂），这是全书最容易失分也最容易出彩的部分；第三条是表、栈与队列（链表指针改写、有序表交并、约瑟夫环）。三条线各自独立又层层递进，复习时按线走，比按题号刷效率高得多。

2. 递归与数学准备：归纳证明、求和差分与模运算的复习重点

这一章的内容看上去像“附录数学”，实际是全书的进场基础。递归写不利索，后面树和图的遍历就只能背代码；归纳法不熟，算法正确性证明那部分基本靠运气。把这三节吃透，后面两章才有落脚点。

2.1 递归写法的三个必备部件

以文件中递归处理#include的那道题为例，一个processFile(String fileName)要做的事是：打开文件、逐行扫描、遇到#include SomeFile就递归调用processFile(SomeFile)、最后关闭文件。这段逻辑本身不难，难点在于自引用包含——A 包含 B、B 又包含 A，递归就停不下来。答案给出的做法是维护一张“尚未返回的文件清单”，每次发起新调用前先查表，命中就跳过。这就是递归的第一个必备部件：可判定的终止条件，而且这个条件往往不是“参数等于某个数”，而是“当前状态是否已在栈上”。

第二个部件是基准情形。二进制位计数那道题只有四行：

public static int ones( int n ) { if( n < 2 ) return n; // 基准：0 和 1 的二进制里刚好各有一位，直接返回自身 return n % 2 + ones( n / 2 ); // 当前最低位 + 高位部分中 1 的个数 }

参数n必须是非负整数。负数在 Java 里做%和/的符号行为与数学定义不一致，直接套这段代码会得到莫名其妙的结果，这是实际写代码时最常见的翻车点。第三个部件是规模递减：n / 2每次至少缩小一半，所以递归深度是 O(log N)，不会撑爆栈；而processFile的“规模”是文件依赖图，递减性要靠查表保证，不能想当然。

把这两个例子放一起看，会发现递归的通用模板是“先写终止条件，再写规模如何变小，最后写当前层做什么”。顺序颠倒过来写，十有八九会漏掉某条分支的基准情形。

2.2 归纳法证明的固定套路

教材里对数不等式的证明是很多人第一次卡住的地方：要证 log X ≤ X。答案的处理方式是分段：先验证 0 < X ≤ 1（此时 log X 非正，显然成立）和 1 < X ≤ 2（此时 log X ≤ 1 ≤ X），然后假设命题在 p < X ≤ 2p 上成立，去推 2p < Y ≤ 4p 的情形，利用 log Y = 1 + log(Y/2) < 1 + Y/2 < Y 收尾。

这里最反直觉的是：归纳变量是区间，不是整数。平时做的归纳都是“n 成立推 n+1 成立”，突然变成“一个区间成立推下一个区间成立”，很多人第一步就不知道假设该写什么。稳妥的写法是把区间端点显式写出来，假设部分写成“对任意满足 p < X ≤ 2p 的 X，命题成立”，这样推导时才能合法地把 Y/2 代入假设。

同一套模板还能处理 Fibonacci 恒等式：证明 ΣF(i) = F(N+2) − 2 时，把求和拆成“前 k 项 + 第 k+1 项”，前 k 项用归纳假设替换成 F(k+2) − 2，再加上 F(k+1)，利用 F(k+3) = F(k+2) + F(k+1) 正好凑成目标形式。Fibonacci 与黄金比的那一问则用到 φ + 1 = φ²，等价变形出 φ⁻¹ + φ⁻² = 1，这个恒等式是把两项合并成一项的关键。平方和、立方和的证明同理，立方和最终要凑成 [N(N+1)/2]²，中间那次提取公因式 (N+1)²/4 是整套推导里最容易抄错的一步。

2.3 求和与差分技巧：从 4/3 到 20/27

这一组题表面是算数，实质在训练一种固定手法：把 S 乘以公比再相减。以 S = 1 + 2/4 + 3/16 + 4/64 + … 为例，先算出 Σ1/4^i = 4/3，再对 S 本身做差分，得到 3S = 4/3，于是 S = 4/9。第三问 S = 1 + 4/4 + 9/16 + 16/64 + … 做同样的差分后，右边会裂成 2Σi/4^i + Σ1/4^i 两部分，前者正是上一问的 4/9，后者是 4/3，于是 3S = 2×(4/9) + 4/3 = 20/9，S = 20/27。答案里那句“一般情形 S_N 的递推很难解”不是敷衍，而是提醒：这套差分只能逐级往下剥，剥到 S_0 为止，级数越高计算量越大。

调和级数那一问更容易被跳过：Σ(1/i) 从 ⌊N/2⌋+1 到 N，约等于 ln N − ln(N/2) = ln 2。它的价值在于给出“一段区间内调和级数近似为区间长度比的对数”这个直觉，后面分析素数筛、并查集路径压缩的均摊代价时都会反复用到。模运算那一问则是标准的降幂：2⁴ = 16 ≡ 1 (mod 5)，100 = 4×25，所以 2¹⁰⁰ ≡ 1 (mod 5)，一步到位。

这几道题的共同特征是：结论简单，过程才是考点。复习时不要只记结果，要把“为什么可以这样变形”写下来，考场上方方面面的变形都是从这几步衍生出去的。

3. 算法分析：增长率排序、大 O 判断与循环估算的复习重点

算法分析这一章是全书的分数密集区，也是概念最容易混的地方。它的知识结构其实很规整：先建立一张增长率排序表作为坐标系，再练三类别判断题型（比较、反例、极限），最后落到具体代码上做循环估算和期望分析。

3.1 增长率排序表：怎么一次记对

教材给出的那串函数是复习的坐标系，把它整理成表比死记顺序有效得多：

这张表里有两个高频陷阱。第一，N log N 与 N log(N²) 是同一阶，因为 log(N²) = 2 log N，只差常数因子。第二，N log²N 与 N^1.5 的先后关系要算一下才知道：比较 log²N 和 N^0.5，两边取对数得 2 log log N 与 0.5 log N，前者显然是后者的低阶，所以 N log²N 更小。凡是拿不准的两项，都可以用“取对数再比”这一招，比背顺序可靠。

3.2 大 O 判断的三类反例与极限工具

这一组判断题的套路值得单独记：给 T₁(N)、T₂(N) 和 f(N)，问“T₁ = O(f) 且 T₂ = O(f) 能否推出 T₁ + T₂ = O(f)”之类。答案给出的三个反例是：T₁ = 2N、T₂ = N、f = N（用于说明常数因子不能随便丢）；T₁ = N²、T₂ = N、f = N²（用于说明“各自的界”推不出“和或差的界”）。这类题的核心是：大 O 描述的是上界，上界之间不能随意做减法，因为两个函数可能一个很大一个很小，差值的量级由大的那个决定，但题目问的往往不是这个。

比较两个函数增长的题，标准工具是取对数后做极限。比如要判断 N log N 与 N^ε 谁增长慢，假设 N^ε 更慢，两边取对数会导出 ε log N 比 log log N 慢，再令 L = log N，就变成 ε^L 与 log L 的比较，而 log²L = o(L) 是已知结论，矛盾，所以 N log N 更慢。同底不同幂的 log^k N 之间用一次极限法则即可：log^i N / N 的极限为 0，归纳下去就得到 k₁ < k₂ 时 log^k₁ N = o(log^k₂ N)。

还有一类是“极限不存在”的反例：f(N) 在 N 为偶数时取 1、奇数时取 N，g(N) 反过来，那么 f/g 在 0 和无穷之间来回震荡，比值没有极限，此时 O 和 Ω 都不成立。这类题提醒的是：大 O 的定义只要求存在常数和起点，不要求比值收敛，所以不能一看“两个函数交替大小”就下结论。

3.3 循环嵌套估算与那道 O(N⁴) 的坑

五段嵌套循环是这一章的经典练习。前四段的结论分别是 O(N)、O(N²)、O(N³)、O(N²)，真正有价值的是后两段。

// 第五段：三层循环，但上界逐层放大 for( int i = 0; i < n; i++ ) for( int j = 0; j < i * i; j++ ) for( int k = 0; k < j; k++ ) sum++; // j 最大到 N²，k 最大到 j，即 N²，总量约 N · N² · N² = N⁵

// 第六段：if 里的代码执行次数远少于判断次数 for( int i = 0; i < n; i++ ) for( int j = 0; j < i; j++ ) if( a[i] + a[j] == 0 ) // 判断本身执行 O(N²) 次 for( int k = 0; k < n; k++ ) for( int l = 0; l < n; l++ ) sum++; // 但真进去只有 O(N²) 次，每次 O(N²)，合计 O(N⁴)

两段的差别是这一节的核心：第五段直接乘循环边界就能得到 O(N⁵)；第六段如果也照乘，会得到 O(N^5) 的过高估计，正确做法是分别统计“判断执行多少次”和“判断为真多少次”。答案里那句“乘循环大小偶尔会给出过高估计”，说的就是这种情形。判断代码块的复杂度时，先问一句“最内层是真的执行了这么多次，还是只是被检查了这么多次”，能避免绝大多数误判。

配套的还有运行时间推算：算法 1 在 N = 10000 时约 38 分钟，N = 100000 时约 26 天。这类换算的通用规则是：时间放大倍数等于规模放大倍数的复杂度次方。线性算法放大 5 倍，平方算法放大 25 倍，立方算法放大 125 倍；反过来，给定时间预算求可处理规模，就是开相应次方。答案中“12000 倍规模”“约 425000”“约 10954”“约 2289”这几个数字，就是这条规则在 O(N)、O(N log N)、O(N²)、O(N³) 上的具体应用。

3.4 期望分析与三种随机置换算法

随机置换这一组题是全书里少见的“概率 + 复杂度”混合题，三种算法分别是：每次随机取一个数、查重后再放入（O(N²)）；每次从剩余元素中随机选一个（O(N log N)）；以及一种原地交换的洗牌法，从后往前对每个位置与它之前（含自身）的随机位置交换，复杂度 O(N)。

第三种算法正确性的证明是这组题的重点：它每次把第 i 个位置与 0..i 中随机一个位置交换，等价于“先随机决定最后一个元素是谁，再递归处理前 i−1 个”，用归纳法可以证明每种排列等概率。而如果把交换范围改成 0..n−1（即与整个数组任意位置交换），等概率性就被破坏——N = 3 时有 27 种等可能的随机数组合，而排列只有 6 种，27 不能被 6 整除，所以不可能均分。这个“27 与 6 不能整除”的论证极其漂亮，也极其容易被忽略，是本章最值得抄进笔记的一句话。

期望次数的推导同样值得记：第一种算法在填第 i 个位置时，已有 i 个数字被占用，单次尝试成功的概率是 (N−i)/N，所以期望尝试次数是 N/(N−i)，累加后总代价约 O(N²)；第二种算法每次尝试省掉了 O(i) 的查重，期望代价降到 O(N log N)。至于最坏情况，前两种算法理论上可能永远抽不到需要的数，所以最坏运行时间无界，但它们以概率 1 终止；第三种算法的最坏情况是线性的，因为它的运行时间与随机数取值无关。

3.5 快速幂、主元素与几个线性小题

快速幂那一问给出的路径是：要算 X⁶²，先算 X²、X⁴、X⁸、X¹⁰、X²⁰、X⁴⁰、X⁶⁰，再拼出 X⁶²。更通用的结论是：乘法次数为 ⌊log N⌋ + b(N) − 1，其中 b(N) 是 N 的二进制中 1 的个数。这个式子的含义是：从 X 开始，每次平方算一次乘法（共 ⌊log N⌋ 次），再对二进制中除最高位以外的每个 1 各乘一次（共 b(N) − 1 次）。实现上不需要递归，用一个数组保存 X^(2^k)，边扫描 N 的二进制位边累乘即可。

主元素问题（数量超过一半的元素）的递归解法是：若前 N−1 个元素中存在主元素，最后一个元素改变不了它；否则最后一个元素可能是主元素。于是 N 为奇数时可以先忽略最后一个，递归处理前 N−1 个，若没有候选再把最后一个作为候选，运行时间满足 T(N) = T(N/2) + O(N)，解出 O(N)。最大差值问题则是典型的“扫描时维护历史最低点”，一次遍历解决，初始答案设为 0（允许 i = j），遇到更低的点就更新低点，遇到更大的差值就更新答案。

二分查找那一问的坑很值得单独标出来：当 low = 1、high = 2 时，mid = 1，如果递归调用仍然是 (low, mid) 或 (mid, high)，区间没有缩小，程序就死循环了。这类“边界不前进”的 bug 在实际代码里非常常见，凡是写二分，都要检查 mid 的取整方向与区间收缩方向是否匹配。

4. 表、栈与队列：链表指针改写与集合运算的复习重点

这一章的题看上去是“写几个方法”，实际考的是两件事：对指针（引用）操作顺序的敏感度，以及对有序结构双指针归并这一通用模板的掌握程度。前者决定你写的链表会不会断，后者决定你遇到交、并、差、去重这类题时能不能直接套。

4.1 printLots：双迭代器的同步推进

题目要求按列表 P 中给出的位置，从列表 L 中取出对应元素。答案的做法是两个迭代器：iterP每次取一个位置itemP，iterL从头开始一路推进到该位置，取到元素后输出，再进入下一轮。这里的关键不是代码本身，而是“L 的迭代器不能回退”这一个约束——正因为单向链表只能前进，iterL必须在上一次的基础上继续推进，而不是每轮都从表头重新开始。

public static <AnyType> void printLots( List<AnyType> L, List<Integer> P ) { Iterator<AnyType> iterL = L.iterator(); Iterator<Integer> iterP = P.iterator(); AnyType itemL = null; Integer itemP = 0; int start = 0; // 记录 iterL 已经走过的位置数 while( iterL.hasNext() && iterP.hasNext() ) { itemP = iterP.next(); while( start < itemP && iterL.hasNext() ) { // 推进到目标位置 start++; itemL = iterL.next(); } System.out.println( itemL ); } }

参数P中的位置必须递增，否则这段逻辑取到的会是“上一次位置之后最近的元素”，而不是目标位置。答案没有做这项检查，属于省略错误处理的写法；实际代码里要么在入口处校验递增性，要么改成每次重新创建 L 的迭代器（代价是 O(|P|·|L|)）。这类“答案为了清晰省掉校验”的地方，在复习时要主动补上，否则考试写完整代码会被扣分。

4.2 swapWithNext：单链表与双链表的差异

交换相邻两个节点，是链表题里最能体现“操作顺序”的题型。单链表的写法是：

// beforeP 指向待交换两节点之前的那一个节点 public static void swapWithNext( Node beforeP ) { Node p, afterP; p = beforeP.next; // 第一个待交换节点 afterP = p.next; // 第二个待交换节点 p.next = afterP.next; // 让 p 跳过 afterP，先接上后面的链，防止丢失 beforeP.next = afterP; // 前驱接上 afterP afterP.next = p; // afterP 接回 p }

顺序不能改。如果先把beforeP.next改成afterP，再试图取afterP.next（此时已经指向 p 后面的链），逻辑上也能写通，但一旦中间需要访问p.next指向的原第三个节点，就会发现链已经被改过。稳妥的习惯是：先保存所有还要用到的引用，再从后往前改指针。

双链表的写法多出两次反向指针赋值：

// p 与 afterP 是待交换的两个节点，需同时维护 prev 与 next 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 修回来 p.prev = afterP; // p 的前驱改为 afterP afterP.prev = beforeP; // afterP 的前驱改为原前驱 }

这里最常漏的是p.next.prev = p这一句：单链表写法里根本不存在反向指针，思维惯性一带，双链表就会漏改，结果正向遍历正确、反向遍历直接指回旧位置。检查办法很简单：改完之后从表头正向走一遍、从表尾反向走一遍，两条路径的节点序列应当完全对称。

4.3 intersection 与 union：有序表归并的同一个模板

求交集和求并集的代码几乎一样，差别只在“相等时加谁、不等时加谁”。模板是：两个迭代器各取一个当前元素，比较大小，小的一方前进并把元素加入结果（并集）或直接丢弃（交集），相等时双方都前进并加入结果。

public static <AnyType extends Comparable<? super AnyType>> void union( List<AnyType> L1, List<AnyType> L2, List<AnyType> Result ) { ListIterator<AnyType> iterL1 = L1.listIterator(); ListIterator<AnyType> iterL2 = L2.listIterator(); AnyType itemL1 = null, itemL2 = null; if( iterL1.hasNext() && iterL2.hasNext() ) { itemL1 = iterL1.next(); itemL2 = iterL2.next(); } while( itemL1 != null && itemL2 != null ) { int compareResult = itemL1.compareTo( itemL2 ); if( compareResult == 0 ) { // 相等：只放一份，两边同时前进 Result.add( itemL1 ); itemL1 = iterL1.hasNext() ? iterL1.next() : null; itemL2 = iterL2.hasNext() ? iterL2.next() : null; } else if( compareResult < 0 ) { // L1 更小：放 L1，L1 前进 Result.add( itemL1 ); itemL1 = iterL1.hasNext() ? iterL1.next() : null; } else { // L2 更小：放 L2，L2 前进 Result.add( itemL2 ); itemL2 = iterL2.hasNext() ? iterL2.next() : null; } } }

求交集时，把两个else if分支里的Result.add(...)删掉，只保留迭代器前进即可。泛型参数写成<AnyType extends Comparable<? super AnyType>>而不是单纯的<AnyType extends Comparable<AnyType>>，是为了让父类实现了比较接口的子类也能传进来，这个细节在实际项目里很常见。另一个隐含前提是两个输入表已经有序——如果无序，这套 O(|L1|+|L2|) 的归并逻辑直接失效，必须先排序。

4.4 Josephus 的取模优化

约瑟夫环那道题的基础解法是“遍历链表，每数到第 M 个删除一个”，复杂度 O(N·M)。答案给出的两条优化都围绕“少走冤枉路”：第一，走 M 步和走 M mod N 步等价，因为绕整圈会回到原点，当 M 远大于当前剩余人数 N 时能省掉大量绕圈；第二，正向走 M 步等价于反向走 M−N 步，当 M 超过 N/2 时改走反向更省。

实现上，第一种优化用单向循环链表即可，每轮用M % size决定前进步数；第二种优化需要双向循环链表，根据 M 与 N/2 的大小关系选择前进方向。答案给出的最坏复杂度是 O(N·min(M, N))，实际带优化后往往远快于这个上界。这一题的复习价值不在于默写代码，而在于体会“把线性步数对环长取模”这个通用技巧——凡是循环结构上的定位问题，都可以先问一句“能不能取模”。

5. 易错点清单：递归边界、大 O 误判与链表断链

这一章把前面几节里最容易被忽略的地方集中列出来。每一条都按“错在哪、为什么会漏、怎么补”三段写，复习时对着自己的错题本核一遍。

易漏点一：递归的终止条件只覆盖了“正常输入”。为什么会漏：写递归时脑子里想的是 n = 5、n = 10 这类常规值，基准情形写完就觉得万事大吉。怎么补：把边界值列成一张小表逐个过——n = 0、n = 1、n 为负、n 取最大整数。二进制位计数那道题里n < 2同时覆盖了 0 和 1，这是正确写法；如果写成n == 1就会在 n = 0 时无限递归。文件递归那道题同理，只判断“文件能打开”不够，还要判断“这个文件是否已在调用栈上”。

易漏点二：用循环层数代替复杂度分析。为什么会漏：三层嵌套看着就像 O(N³)，这个直觉在大部分情况下成立，于是形成了思维定式。怎么补：遇到带if的循环，单独统计“条件判断次数”和“条件为真次数”，二者往往差一个量级。第六段循环就是典型：判断执行 O(N²) 次，为真的只有 O(N²) 次中的一部分（对每个 i 恰好 i 次），真正进内层的是 O(N²) 次，每次 O(N²)，合计 O(N⁴)，而不是照乘出来的 O(N⁵)。

易漏点三：把 N log N 和 N log(N²) 当成两阶，或者把 N log²N 排在 N^1.5 后面。为什么会漏：对数运算的性质隔久了就记混，看到括号里多个平方就以为大了一阶。怎么补：记两条——log(N²) = 2 log N 只是常数倍；比较含对数的两项时两边取对数，把乘法结构变成加法结构，谁大谁小一目了然。

易漏点四：链表交换时先改前驱指针，导致后半段链丢失。为什么会漏：单链表写顺手了，双链表照搬，只改next不改prev；或者反过来，先动beforeP.next再想访问原来的后继。怎么补：固定顺序“先存引用，再从后往前改指针”，改完做双向遍历自检。这一类错误在纸面上看不出问题，一跑就崩，属于典型的“血泪经验”。

易漏点五：二分查找的区间不收缩。为什么会漏：递归写法里 mid 的取整方向与区间划分方向没有对齐，low = 1、high = 2 时 mid 落在 low 上，一侧区间原地不动。怎么补：写完二分先手算两个元素的用例，确认每次递归后区间长度严格变小；习惯上把 mid 写成low + (high - low) / 2，并在递归调用处明确“mid 归哪一边”，两边都检查一遍。

6. 复习清单：三轮刷题顺序与自查表

把这份答案用出效果，关键不在刷得多，而在每轮的目标不同。我自己踩过的最大的坑是：第一轮就把所有题从头做到尾，做完只剩“好像都见过”的模糊印象，过两周再问细节全忘。后来改成三轮，效率才稳下来。

第一轮的目标是建地图，只做每章的前几道和带“证明”“分析”字样的题，其余题只读题面不写代码，用一张纸记下“这题考的是哪个知识点”。这一轮控制在两周内，宁可留白也不要卡死在某一道题上。第二轮按模块横向打穿：递归与数学准备一整天，算法分析两天，表栈队列一天，每个模块只挑三类题——最典型的、自己最没把握的、答案写得最简略的。第三轮只碰错题和易错点清单，配合下面的自查表逐项打勾。

配套的做法是给自己定一条硬规矩：任何一道涉及指针或边界的题，写完必须手算两个元素的用例。这个习惯来自一次教训——某次模拟测验里链表交换题我自信满满地交了卷，结果双链表的反向指针漏了一行，正向遍历完全正常，反向一跑就死循环，排查了半小时才发现问题出在没做双向自检。从那以后我每次改链表指针都强制走一遍“正向走一遍、反向走一遍”的流程，再没在这类题上翻过车。

复习到后期，判断自己是否真的掌握，有个简单标准：能不能不看答案，把某一章的题按知识点重新分类，并说出每类题的通用解法。做得到，说明地图已经在脑子里；做不到，就回到对应章节把那一节的模板再抄一遍。希望这份梳理帮到你。

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