Java数据结构与算法分析：复杂度、递归与链表高频考点

简介：面向《数据结构与算法分析（Java语言描述）》第三版学习者的习题解答文档，适合正在学习Java数据结构、算法分析与程序设计基础课程的学生自查思路，也可供复习递归、数学推理与复杂度分析时对照参考。压缩包共1个docx文件，约1.52MB，内容以教材课后题解答为主，涉及文件I/O与递归处理嵌套包含、整数按位递归求和、数学归纳法证明对数性质、等比与差分法数列求和、模运算与指数定律、大O符号及调和级数估计等典型题目。已有2435人学习，说明其作为课后练习对照材料具有一定参考价值。读者可借助逐题解答梳理解题步骤，理解递归构造、归纳证明和渐近分析的常见套路，并据此排查自己的推导漏洞、补充课堂笔记，提升把数学推理落到Java代码与算法分析中的能力。

1. 从一道三行递归题看这场考试到底考什么

ones(n)这道题的答案只有三行：n 小于 2 就直接返回 n，否则返回n % 2 + ones(n / 2)。很多人抄完就翻页，可阅卷人和面试官真正想听的一句话是——它在数 n 的二进制表示里有几个 1，答不出这句，代码再对也只是背答案。Java 数据结构 与 算法分析 这类考卷的分水岭就在这里：不考你会不会写循环，考你能不能把“能跑”翻译成“能证明”。翻完第三版的习题答案会发现，能拉开差距的题集中在四个地方：递归与复杂度推导、递推求和与归纳证明、链表指针操作、边界条件处理。前两块决定大题能不能拿满分，后两块决定代码题会不会当场翻车。正在啃这本教材习题、准备课程考试或复试机试的人，按这个顺序练最省时间：结论先写，推导跟上，边界最后交代，缺哪一段都会被扣分。

2. 复杂度分析：增长率排序、大 O 反例与嵌套循环计数

2.1 十四个函数排序，先锚定三条基准线

增长率排序是选择题的常客，题目把一串函数丢出来让你从小到大排。死记硬背很容易乱，锚住三条基准线就稳了：常数的位置、N的位置、N log N的位置。

以一组典型排序为例，从小到大是：2/N、37、√N、N、N log log N、N log N、N log(N²)、N log² N、N^1.5、N²、N² log N、N³、2^(N/2)、2^N。

几个必须说得出理由的位置：

37是常数，排在2/N之后，因为2/N随 N 增大趋近于 0，比任何正常数都小。N log N和N log(N²)同阶，因为log(N²) = 2 log N，两者只差常数因子 2。N log² N排在N^1.5前面，比较的是log² N和N^0.5，后者增长更快。2^(N/2)和2^N之间差的是开方级的底数，指数级内部同样要分先后。

这类题最容易错的地方是把“写法不同的同阶函数”排成两档，只要看到log(N^k)、k log N、log N + log k这类变形，先合并再说。

还有一类用取对数比较两个函数的题：判断N log N与某个带log² N的指数型函数谁长得慢。标准套路是两边同时取对数，把乘除化成加减，再用洛必达式的求导比较把高阶项压下去。取对数这一步不损失增长率信息，因为对数函数单调递增，f = O(g)与log f = O(log g)在正函数范围内等价。

2.2 三个反例告诉你：大 O 只是上界，不是“差不多”

习题里有连续三小问，专门打“大 O 可以随便约掉常数”这个错觉。设T1(N) = 2N，T2(N) = N，f(N) = N，此时T1(N) = O(f(N))与T2(N) = O(f(N))同时成立，但推不出T1(N) = O(T2(N))这条看似显然的结论反过来用——题目的陷阱在于让人以为两个函数都是 f 的大 O，就自动同阶。

再换一组：T1(N) = N²，T2(N) = N，f(N) = N²。依然有T1 = O(f)、T2 = O(f)，但T2和T1差距是数量级。结论很直接：大 O 给的是上界，两个函数共享同一个上界，不意味着它们互相是对方的上界。

面试官问“这两个复杂度是不是一样”，他想听的是“同阶需要互相满足 O 关系，即T1 = O(T2)且T2 = O(T1)，也就是 Θ 记号”。只答“都是 O(N)”会被追一句“那能互相界定吗”，答不上来就露怯了。

2.3 嵌套循环：别拿层数当指数

一段三层循环的代码，粗看是O(N³)，实际可能是O(N⁴)甚至O(N⁵)。下面这段是高频原题：

// 外层 i 到 N，中层 j 到 i*i，内层 k 到 j long sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= i * i; j++) for (int k = 0; k < j; k++) sum++;

三层循环，但每层的上界都依赖外层变量。j最大能到i²，也就是N²；k最大能到j，同样量级N²。乘起来是N · N² · N² = N⁵，答案O(N⁵)。

真正的坑在下面这段加了if的版本：

// if 语句本身执行 O(N^3) 次，但成立次数远少于执行次数 long sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= i * i; j++) if (j % i == 0) // 对每个 i，只有 i 个 j 满足 for (int k = 0; k < j; k++) sum++;

if的判断被执行了O(N³)次，这点没错。但成立的条件是j % i == 0，对每个固定的i，在1..i²范围内满足条件的j恰好有i个，把i从 1 累加到 N，总数是O(N²)。每次成立时内层跑j次，j最多N²，因此总代价O(N²) · O(N²) = O(N⁴)。

提示：把各层循环上界直接相乘，得到的往往是高估。判断语句、条件分支、提前退出都会把实际次数压下来，必须回到“某条语句被执行了多少次”上重新数。

这段代码的参数含义值得多说一句：i控制外层规模，j的上界写成i * i是出题人故意制造的“非线性上界”，k的上界绑定j是为了让内层代价随外层变化。改一行就换一个答案——如果把j <= i * i改成j <= i，同样的结构立刻降到O(N³)甚至O(N²)，这也是命题人喜欢在这类题上做文章的原因。

2.4 运行时间换算：时间放大多少倍，规模能涨多少

还有一类计算题给出基准运行时间和复杂度，问输入规模放大后可处理的数据量。做法是把复杂度当成规模到时间的映射，时间放大倍数记为 K，反解规模。

以基准规模 100、时间放大 12000 倍为例，四种复杂度的结果如下：

判断“时间变几倍属于哪种复杂度”的题更简单：时间变 5 倍对应线性，变 25 倍对应平方（5²），变 125 倍对应立方（5³）。中间那个“略多于 5 倍”的选项通常就是O(N log N)，因为对数因子带来的增量不大，但确实存在，能不能选对全看你有没有把log N这一项当回事。

3. 递推与求和：差分技巧、归纳证明与放缩估计

3.1 递归函数先讲清楚“它算的是什么”

递归题最常见的失分不是写错，是说不清语义。ones(n)求的是二进制中 1 的个数，不是十进制各位数字之和，不少人在口头描述时就错在这一句上。写成代码只有三行：

// 返回 n 的二进制表示中 1 的个数 public static int ones(int n) { if (n < 2) return n; // 0 和 1 是递归出口 return n % 2 + ones(n / 2); // 取最低位，剩下部分右移一位继续 }

参数只有一个n，出口条件是n < 2，递归方向是n / 2，每层规模减半，递归深度是O(log N)，总时间也是O(log N)。这三句话是面试时的标准回答结构：语义、出口、规模变化。

另一道文件处理题考同样的思路，但难度在于“递归调用自身”这个动作要带状态：

// 处理文件；遇到 #include SomeFile 时递归处理被包含文件 void processFile(String fileName) { List<String> active = new ArrayList<>(); // 尚未返回的文件名 process(fileName, active); } private void process(String fileName, List<String> active) { if (active.contains(fileName)) { // 检测自引用包含 throw new IllegalStateException("self-referential include: " + fileName); } active.add(fileName); open(fileName); for (String line : readLines(fileName)) { if (line.startsWith("#include ")) { process(line.substring(9).trim(), active); // 递归进入被包含文件 } else { handle(line); } } active.remove(fileName); // 返回前移出活动栈 close(fileName); }

关键在active这个列表：它在递归进入前加入当前文件，返回前移除，语义是“调用栈上还没结束的文件集合”。判断自引用包含，就是看新文件名是否已在集合里。这个结构比单纯递归多了一维状态，考试时如果只写递归不写这个集合，等于漏掉了题目的一半。面试官追问“循环包含 A 包含 B、B 又包含 A 怎么发现”，答案就落在这个集合上。

3.2 差分求和：把 S 和 4S 对着减

等比乘等差形式的求和，标准手法是构造一个倍数关系再相减。以S = Σ i / 4^i（i 从 1 开始）为例，把4S写出来：

S = 1/4 + 2/16 + 3/64 + 4/256 + …4S = 1 + 2/4 + 3/16 + 4/64 + …

两式相减，同分母项逐项抵消后剩下3S = 1 + 1/4 + 1/16 + 1/64 + …，右边是公比 1/4 的等比级数，和为 4/3。于是S = 4/9。

同一套手法再做一次平方版本：S = Σ i² / 4^i，3S = 1 + 3/4 + 5/16 + 7/64 + …，拆成2Σ i/4^i + Σ 1/4^i，前一项是2 × 4/9 = 8/9，后一项是4/3 = 12/9，合起来20/9，因此S = 20/27。

再往上做一次，四次方版本会得到形如S_N依赖S_{N-1} … S_0的递推关系，题目本身也承认“解这个递推非常困难”。考场上遇到这类题，写出递推关系通常就是满分点，硬解反而浪费时间。

注意：相减时最容易漏掉首项或把下标起点搞错。构造 4S 时乘的是公比的倒数，S 从 i = 1 起还是从 i = 0 起，会直接改变首项是 1/4 还是 1，答题时先把起点写在旁边再动笔。

3.3 归纳证明：基础情况、假设区间、递推一步

归纳法证明题有三处必须交代清楚，缺一处就会被扣分。

以log X ≤ X（X > 0）的证明为例，题目用的是分段归纳：先验证0 < X ≤ 1，此时log X ≤ 0 < X；再验证1 < X ≤ 2，此时log X ≤ 1 < X；然后假设对p < X ≤ 2p成立，推2p < Y ≤ 4p的情形，用log Y = 1 + log(Y/2) < 1 + Y/2 < Y。三段式的关键是假设区间和证明区间要首尾衔接，2p是上一段的终点，也是下一段的起点。

斐波那契求和的归纳是另一种常见形态：证明Σ F_i = F_{N+2} - 2。基础情况验证 N = 1、N = 2；假设对1..k成立；在 N = k+1 时把和拆成Σ_{1}^{k} F_i + F_{k+1}，代入假设得F_{k+2} - 2 + F_{k+1}，再用斐波那契定义合并成F_{k+3} - 2，正好是 N = k+1 的形式。

代数恒等式的证明更看重变形方向。Σ (2i - 1) = N²只需拆成2Σ i - Σ 1 = N(N+1) - N = N²。而Σ i³ = [N(N+1)/2]²的归纳证明需要一次凑配：把(N+1)³提出来，凑成(N+1)² [N² + 4(N+1)] / 4，再化回[(N+1)(N+2)/2]²。这一步在纸上是三行，在考场上是十分钟，练的时候一定要亲手推一遍，看懂和自己写出来差距很大。

3.4 放缩与计数：调和级数约等于 ln 2，快速幂只要 log 次乘法

有一类题问Σ_{i=⌊N/2⌋}^{N} 1/i的量级。做法是把求和拆成两段调和级数之差，H_N - H_{⌊N/2⌋-1}，再用积分放缩ln N - ln(N/2) = ln 2。结论是它约等于常数 ln 2，与 N 无关。这个结论在分析分治算法、随机算法期望时反复出现，属于必须背下来的常数级结果。

另一类计数题问幂运算的乘法次数。计算X^62不需要 61 次乘法，按平方递推只需 8 次：算出X²、X⁴、X⁸，再组合出X^10、X^20、X^40、X^60，最后X^60 · X²得X^62。

这个结论可以写成通式：当 N > 1 时，乘法次数等于⌊log N⌋ + b(N) - 1，其中b(N)是 N 的二进制表示中 1 的个数。N = 62 时，⌊log 62⌋ = 5，b(62) = 5（111110），代入得 5 + 5 - 1 = 9，减去一次可以复用的首项即 8 次。这个公式面试时能直接报出来，比现场数要快得多，也更显得你真的推过。

4. 表、栈与队列：指针顺序、双游标合并与环形计数

4.1 交换相邻节点：三根指针的赋值顺序决定成败

单链表交换相邻两个节点，题目要求只改指针不改数据。核心是“先接后断”，顺序错一步整条链就断：

// beforep 是要交换的两个相邻节点中前一个节点的前驱 public static void swapWithNext(Node beforep) { Node p = beforep.next; // 第一个待交换节点 Node afterp = p.next; // 第二个待交换节点，假定两者均非空 p.next = afterp.next; // 第一步：p 越过 afterp 接上后续链 beforep.next = afterp; // 第二步：前驱改指 afterp afterp.next = p; // 第三步：afterp 回指 p，形成新顺序 }

三步的顺序不能换。第一步必须先把p.next存下来，否则第二步改写beforep.next之后，p后面的链就找不回来了。这是血泪经验里最经典的一条：链表题先想“哪根指针的信息会丢”，把会丢的那根先保存或先用掉。

双向链表版本多两处回指，同样三步，只是每步之后要补prev：

// p 与 afterp 为待交换的两个相邻节点 public static void swapWithNext(Node p) { Node beforep = p.prev; Node afterp = p.next; p.next = afterp.next; // p 的 next 指向 afterp 之后的节点 beforep.next = afterp; // 前驱指向 afterp afterp.next = p; // afterp 指向 p p.next.prev = p; // 补回指：p 的新后继回指 p p.prev = afterp; // p 的前驱改为 afterp afterp.prev = beforep; // afterp 的前驱改为 beforep }

答题时如果只写单链表版本，面试官通常会追问“双向链表要多改几根指针”，答案是四根：beforep.next、p.next、afterp.next，以及被p.next覆盖后需要补回的prev链。数据域完全不动，这一句要说出来。

4.2 有序表求交求并：双迭代器的三种分支

两个有序表求交集和并集，标准解法是双游标归并，一次扫描搞定，代价 O(N)。三分支的结构是固定的：相等时输出，小的那侧前进，另一端等待。

// 求两个有序表的交集，结果按升序写入 Intersect public static <AnyType extends Comparable<? super AnyType>> void intersection(List<AnyType> L1, List<AnyType> L2, List<AnyType> Intersect) { ListIterator<AnyType> it1 = L1.listIterator(); ListIterator<AnyType> it2 = L2.listIterator(); AnyType a = it1.hasNext() ? it1.next() : null; AnyType b = it2.hasNext() ? it2.next() : null; while (a != null && b != null) { int cmp = a.compareTo(b); if (cmp == 0) { // 相等：收进结果，两边同时前进 Intersect.add(a); a = it1.hasNext() ? it1.next() : null; b = it2.hasNext() ? it2.next() : null; } else if (cmp < 0) { // a 小：a 侧前进，等 b 追上来 a = it1.hasNext() ? it1.next() : null; } else { // b 小：b 侧前进 b = it2.hasNext() ? it2.next() : null; } } }

求并集只改一处：不相等时把较小的那个也写进结果，相等时写一次。参数含义是L1、L2为输入有序表，Intersect或Result为输出表，三个表都是List接口，迭代器用ListIterator是为了支持有序遍历和插入。

易错点集中在两处。第一处是相等分支里只让一侧前进，会造成死循环；第二处是表的末尾处理，hasNext()为假时赋null当作哨兵，靠while条件里的null判断收尾，如果漏掉这一步，循环结束时可能少比对最后一组元素。改写时可以把哨兵换成显式的boolean标志，代码更长但更稳。

4.3 约瑟夫环：M mod N 与反向走 N - M

约瑟夫问题要求每次数到第 M 个人出列。朴素做法是每次都从头遍历 M 步，代价 O(N·M)。两个观察能把常数压下去：

如果 M 远大于当前剩余人数 N，走 M 步等于走M mod N步，多转的整圈是无用功。如果 M 大于 N/2，正向走 M 步等价于反向走N - M步。把这两条用到极致，最坏复杂度是O(N · min(M, N))，M 很大时收益非常明显。

答题时先写朴素循环，再说这两条优化，比直接甩优化代码更得分，因为面试官想看的是你知不知道自己省了什么。写实现时注意移除元素后当前下标要回退一位（用迭代器则不用），这是实际动手时最常翻车的地方。

4.4 按位置打印：游标只前进的前提

给定一个数据表和一个位置表，要求按位置表里的下标打印对应元素。解法是复用同一个游标：

// 按 P 中给出的位置，依次打印 L 中对应位置的元素 public static <AnyType> void printLots(List<AnyType> L, List<Integer> P) { Iterator<AnyType> iterL = L.iterator(); Iterator<Integer> iterP = P.iterator(); AnyType itemL = null; int start = 0; // 游标已经走过的位置数 while (iterL.hasNext() && iterP.hasNext()) { int itemP = iterP.next(); while (start < itemP && iterL.hasNext()) { start++; itemL = iterL.next(); // 游标只前进，不回头 } System.out.println(itemL); } }

复用游标能把代价从 O(|P|·|L|) 降到 O(|L| + |P|)，前提是位置表本身升序。如果 P 里的位置是乱序的，游标已经走过的地方就回不去，这个优化直接失效，只能退化成每次从头扫。答题时补一句“输入保证位置表递增，否则需要改为按下标随机访问”，比闷头写代码更容易拿高分。

5. 易错点：五类高频失分题，错在哪、为什么错、怎么答对

5.1 二分递归不收敛：low = 1、high = 2 时 mid = 1

错在哪：写二分的递归版本时，取mid = (low + high) / 2，当low = 1、high = 2时算得mid = 1，两个子问题里有一个回复到[1, 2]自身，递归永远不进步，栈直接爆。

为什么错：整数除法是向下取整，区间长度只剩 2 时中点会贴到左边界，左右子问题没有严格缩小。

怎么答对：把区间收窄成[low, mid]与[mid + 1, high]，保证两个子区间都严格小于原区间；或者直接用循环版本，边界写成low <= high配合low = mid + 1、high = mid - 1。面试时主动指出“这里如果写[low, mid - 1]和[mid, high]，取整方向必须改成向上取整”，是加分句。

5.2 随机置换的等概率假设：6 不整除 27

错在哪：洗牌算法里把“每次随机取0..n-1与当前位交换”当成必然等概率。

为什么错：以 n = 3 为例，三次交换各自有 3 种取值，总共 27 条等概率路径，而排列只有 6 种。27 不被 6 整除，必然有些排列被多算、有些被少算。这是一个纯计数论证，不需要写代码就能证伪。

怎么答对：把随机范围收窄成0..i（当前已处理部分），每条路径与唯一排列一一对应，概率正好是1/n!。答题时用 n = 3 这个反例最省时间，一句话说完“27 不能被 6 整除”。

5.3 平均与最坏混着说：以概率 1 终止不等于有界

错在哪：分析随机化算法时把“期望时间 O(N)”直接说成“最坏时间 O(N)”。

为什么错：有一类洗牌或采样算法，任意给定时刻都可能还没终止，因此最坏情况执行时间无上界；但它以概率 1 终止，期望是有限的。两个结论不能互换。

怎么答对：分三句话说——期望时间是多少、以多大把握终止、最坏情况能不能给出界。第三类算法（边遍历边交换那种）的最坏情况是线性的，因为它的执行步数根本不依赖随机数的具体取值，这个对比正好说明“随机”不等于“没有最坏界”。

5.4 低阶项被写进答案：N log N和N log(N²)被当成两档

错在哪：把log(N²)当成比log N高一阶的量，排序或化简时分开讨论。

为什么错：log(N²) = 2 log N，只差常数因子，在渐近意义下同阶。同理log^k N对任意固定 k 都是o(N)，用一次求导比较就能压下去，不存在“对数阶内部还能跟 N 比高低”的说法。

怎么答对：所有对数先化成同底同形式再比。看到log(N^k)、k log N、log N + log log N，一律先合并常数，剩下的才是真正的增长率差异。

5.5 归纳证明跳步：假设区间和结论区间不衔接

错在哪：证log X ≤ X时只验证X = 1和X = 2两个点，就直接宣布对所有 X 成立。

为什么错：归纳要求假设覆盖一个区间，并在下一段严格推进。只验证离散点，无法覆盖2 < X ≤ 4这段连续区间。

怎么答对：写成三段——基础区间验证、假设p < X ≤ 2p、证明2p < Y ≤ 4p，每段的端点都要接得上。斐波那契那题同理，基础情况要验 N = 1 和 N = 2 两个，只写一个会被判不完整。

6. 答题技巧：从“写出代码”到“写出论证”的四步走法

真正拉开分数的不是会不会写，而是写完之后有没有把话说圆。把每道题当成一次小型答辩，按下面四步走，漏一步就补一步。

举一个完整的例子。问Σ(2i - 1)从 1 到 N 等于多少。先给结论 N²，再给推导2Σi - Σ1 = N(N+1) - N，最后补一句“该式对 N = 0 时按空和记作 0，同样成立”，四句话拿满分。如果只写一个 N²，遇上严格阅卷就是半分。

代码题的模板反过来：先说清楚参数和返回值的含义，再写代码，代码块之后补三段说明——关键变量的作用、边界条件的处理、时间复杂度的来源。链表交换那道题，代码只有六行，解释却能写三行：beforep是前驱，p和afterp是待交换的两个相邻节点，三步赋值的顺序由“哪根指针的信息会先丢”决定。这三行解释，往往比代码本身更能体现水平。

押题方向也给一个粗判据：复杂度排序、嵌套循环计数、递归语义、链表指针顺序、二分边界这五类，几乎每套卷子都会命中两道以上。考前最后一遍不要重读全书，把这五类的错题本过一遍，每类挑一道完整写出四步，比刷十道新题有用。

我自己踩过最狠的一次，是把一道嵌套循环题的答案从O(N⁵)改成了O(N⁴)，理由是“三层循环怎么可能到五次方”。交卷后才发现内层上界是j，而j最大到i²，乘起来确实是五次方。从那以后我每次写复杂度结论前，都强制走一遍“逐条语句数执行次数、再取最大项”的流程，不管直觉多笃定。希望帮到你。

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