简介：《数据结构与算法分析（Java语言描述）》（第三版）习题答案文档，面向使用该教材学习数据结构与算法分析的学生及自学者，用于课后练习核对、概念复盘与解题思路梳理。压缩包仅含1个docx文件，大小约1.52MB，便于在电脑或平板上直接查阅。内容围绕递归、数学推理、文件处理与计算复杂度分析展开，涉及processFile的递归文件包含处理、ones递归求位和、数学归纳法证明对数性质、等比与差分求和、递推式求解、2^100模5的指数运算，以及大O记号和对数估计等典型题目。已有2435人学习，适合在复习阶段对照答案理解推导过程，也可作为算法基础训练和考试查漏补缺的参考。

1. 什么是数据结构与算法分析：为什么每个写 Java 的人迟早要碰它

很多人第一次听到「数据结构与算法分析」这八个字，脑子里浮现的是一堆链表指针和大 O 符号，觉得这是考试才用得上的东西。其实它回答的是一个特别朴素的问题：同样是处理一万条数据，为什么有的代码几毫秒跑完，有的要让你盯着屏幕等上几分钟？打个比方，数据结构是你收拾房间的方式——东西放哪个抽屉、怎么叠放；算法分析就是你判断这套收拾方式在房间变大之后还灵不灵。Java 只是那把螺丝刀，真正决定效率的，是你选了什么样的结构、有没有估过它的代价。这份第三版习题答案之所以值得翻，是因为它把「怎么想」写在了「答案是什么」旁边，而不是只丢给你一个结果。

2. 为什么算法分析里全是递归和数学：从一道求二进制 1 的题说起

2.1 递归不是炫技，是把大问题缩小的手艺

翻这份答案的人，十有八九在第一页就被一串递归函数和归纳法证明拦住了，心里冒出的第一个疑问是：我就想学个数据结构，凭什么先证明对数不等式？先别急着跳过，递归在这门课里不是拿来炫技的，它是最基本的「拆问题」手法。

教材开篇有一道题，要求写一个函数，数出一个整数在二进制表示里有多少个 1。答案只有三行：

// 统计整数 n 的二进制表示里有多少个 1 public static int ones( int n ) { if( n < 2 ) return n; // 0 或 1，直接返回 return n % 2 + ones( n / 2 ); // 最低位 + 剩余高位里的 1 }

参数n是非负整数。n % 2取出最低位是 0 还是 1，n / 2把数字整体右移一位，剩下的高位再交给下一次调用去数。三行代码干的事，说白了就是：把「数一万位」拆成「数一位 + 数剩下的九千九百九十九位」。每一层只处理最小的一块，其余全甩给下一次调用——这就是递归的核心，它不是在绕圈子，而是在缩小问题的规模。

同一章还有一道文件处理的题更能说明问题。题目要求写一个processFile(String fileName)，打开文件、处理内容、关闭文件；一旦读到形如#include SomeFile的行，就递归调用processFile(SomeFile)去处理被包含的文件。这里藏着一个经典的翻车点：如果 A 文件包含 B，B 又反过来包含 A，递归就会无限下去。原文的解法是维护一张「尚未处理完的文件列表」，每次发起新调用前先查表，发现已经在处理中就拒绝。这是血泪经验换来的教训——递归没有终止条件，程序就会直接栈溢出。

2.2 数学归纳法和求和公式：算法分析的地基

很多人以为归纳法证明是数学课的事，跟写代码没关系。其实关系大了：你分析一个递归算法的耗时，最后得到的是一个递推式，而证明这个递推式等于某个闭式结果，最顺手的工具就是归纳法。

原文里有一道题用归纳法证明一个关于对数的性质：先验证小范围成立，再假设某个区间内成立，由此推出下一个区间也成立。这套「基础情况 + 假设 + 推一步」的套路，就是归纳法的标准动作。你在分析T(N) = 2T(N/2) + N这类递推式时，脑海里的推演过程跟它是一模一样的。

另一道题用「错位相减」求级数，比如把S = 1 + 2/4 + 3/16 + …这类式子的两边乘一个系数再相减，最后算出 4/3、4/9、20/27 这样的结果。为什么算法分析要会这个？因为大量递归算法的总代价就是一个级数，比如N + N/2 + N/4 + …加起来约等于2N，你不把级数收拢，就说不清它到底是线性还是平方。

还有一道题算2^100 mod 5，利用2^4 ≡ 1 (mod 5)，把 100 拆成 4 的倍数，一步就出结果。模运算的周期性在哈希表取下标、循环数组、随机数生成里天天出现。这些数学不是装饰品，它们是让你把「跑多少次」算成一个公式的扳手。

2.3 大 O 记号：为什么它只关心增长趋势

原文有一道题估计从N/2到N的调和级数之和，用积分近似得到大约ln 2。这类估算就是大 O 思维的雏形：不追求精确到个位，只追求在 N 很大时抓住主要矛盾。

大 O 的正式定义是：存在常数 c 和 N0，当 N 大于 N0 时，T(N) ≤ c·f(N)。翻译成人话——它不关心你的机器多快、常数项多大，只关心 N 变大时谁涨得更凶。打个比方，两辆车，一辆时速 100，一辆时速 80，短途你看不出差别，但开一整天，先到的肯定是那辆快的。大 O 说的就是「开一整天之后谁先到」。

正因为只看趋势，所以N^2 + 100N里那个100N会被直接扔掉，3N log N前面的 3 也会被扔掉。这是「抓大放小」，不是偷懒。但也要留个心眼：大 O 是上界，不等于实际运行时间，数据量小的时候，常数项反而可能唱主角。这一点会在第 5 章专门展开。

3. 算法复杂度到底怎么估：增长率、循环和那几个翻车点

3.1 增长率排序：从 N 到 2^N 的阶梯

教材第二章有一道看起来很吓人的题，给了一串函数让你按增长速度排序：2/N、37、√N、N、N log log N、N log N、N log(N^2)、N log^2 N、N^1.5、N^2、N^2 log N、N^3、2^(N/2)、2^N。

排序的逻辑其实就一条阶梯：常数 < 亚线性（√N）< 线性 < 线性对数 < 多项式 < 指数。真正容易看走眼的是中间那几项。原文特别点出，N log N和N log(N^2)是同一个量级，因为log(N^2) = 2 log N，那个 2 在大 O 里被吃掉了。初学者常常把括号里的平方当成「更高级」，其实没有。

这张表不需要背，但要能对着代码说出它在哪一档。看到一个双层循环，心里就该冒出「平方」两个字；看到「每次砍一半」，就该冒出「对数」。

3.2 嵌套循环的复杂度怎么数

把循环层数直接相乘，是初学者最常踩的坑。教材里有一段三层循环，外层i从 0 到 N，中层j最大到i^2也就是N^2，内层k最大到j又是N^2，乘起来是O(N^5)，这个结论没问题。

但紧接着的另一段代码就没这么简单了：

for (int i = 0; i < n; i++) for (int j = 0; j < i * i; j++) if (j % i == 0) // 这个条件只有 i 次成立 for (int k = 0; k < j; k++) sum++;

如果机械地把三层循环相乘，你会得到O(N^3)甚至更高。原文的分析是：if语句确实会被执行N^3次左右，但条件真正成立的次数只有O(N^2)次（对每个i恰好成立i次），所以最内层只跑了O(N^2)次，每次O(j^2) = O(N^2)，总共O(N^4)。原文专门用一句话提醒：把循环上界相乘，有时会给出高估。这是「看代码不能只看壳」的典型例子——一个if就可能把复杂度砍掉一个量级。

3.3 递推式与分治：T(N)=T(N/2)+O(N) 背后的东西

除了数循环，另一大类复杂度来自递推。教材里反复出现的模式是：把问题分成两半，每半递归处理，再花线性时间把结果合并。写成式子就是T(N) = T(N/2) + O(N)。它的直觉解法是：每次合并花O(N)，一共分log N层，乘起来就是O(N log N)。二分查找是它的简化版，T(N) = T(N/2) + O(1)，因为合并只花常数时间，结果就是O(log N)。

原文还有一道题讨论「时间增加 5 倍，输入能扩大多少」。对线性算法，输入能扩 5 倍；对平方算法，输入只能扩√5倍左右；对立方算法，只能扩5^(1/3)倍。这就是为什么同样是优化，算法复杂度低一档，能处理的数据量会差出好几个数量级。

快速幂是另一个漂亮例子。要算X^62，笨办法是乘 61 次；原文的思路是先算出X^2、X^4、X^8、X^10、X^20、X^40、X^60、X^62，用指数的二进制拆分把乘法次数压到O(log N)：

// 快速幂：计算 base^exp，时间复杂度 O(log exp) long fastPow(long base, int exp) { long result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= base; // 当前二进制位为 1，乘进来 base *= base; // 底数平方 exp >>= 1; // 指数右移一位 } return result; }

exp & 1判断最低位是否为 1，exp >>= 1把指数右移一位，base *= base让底数随着位权平方。每循环一次，指数少一半，所以循环次数是对数级的。原文还进一步讨论了乘法次数的精细计数，结论是大约log N + b(N) - 1次，其中b(N)是二进制里 1 的个数。这种从「能跑」到「精确算代价」的递进，正是算法分析这门课的价值。

4. 表、栈、队列：线性结构在 Java 里的操作细节

4.1 链表的指针操作：swapWithNext 为什么容易写错

链表题是这份答案里最容易让人怀疑人生的部分。原文有一道题，要求交换单链表里相邻的两个结点。答案是这样的：

// 交换 beforep 后面相邻的两个结点；假设 p 和 afterp 都不为 null public static void swapWithNext( Node beforep ) { Node p, afterp; p = beforep.next; afterp = p.next; p.next = afterp.next; // 先让 p 跳过 afterp beforep.next = afterp; // beforep 指向 afterp afterp.next = p; // afterp 再指回 p }

这三行赋值的顺序绝对不能反。第一步p.next = afterp.next必须在afterp.next = p之前，否则afterp.next先被覆盖，后面就拿不到原来的后继了。这是典型的指针翻车点，单步调试都不一定一眼看出来，得在纸上画三个方框、连三根线才踏实。

双链表版本又多出几条prev要维护：

// p 和 afterp 是要交换的两个相邻结点 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; // 补上被交换结点的 prev 指针 p.prev = afterp; afterp.prev = beforep; }

打个比方，单链表像单行道，改一个方向就行；双链表像双向车道，改了一边，另一边也得跟着改，少改一条就撞车。双链表的 bug 难查，就是因为断掉的往往不是你正在看的那条链。

4.2 交集与并集的归并式写法

原文有两道经典题：求两个有序表的交集和并集。核心套路是双指针归并——两个表各拿一个迭代器，比较当前元素，小的那个往前走，相等就收进结果。

// L1、L2 均为有序表，求交集放进 Intersect public static <AnyType extends Comparable<? super AnyType>> void intersection(List<AnyType> L1, List<AnyType> L2, List<AnyType> Intersect) { ListIterator<AnyType> i1 = L1.listIterator(); ListIterator<AnyType> i2 = L2.listIterator(); AnyType a = i1.hasNext() ? i1.next() : null; AnyType b = i2.hasNext() ? i2.next() : null; while (a != null && b != null) { int cmp = a.compareTo(b); if (cmp == 0) { // 相等，收进结果 Intersect.add(a); a = i1.hasNext() ? i1.next() : null; b = i2.hasNext() ? i2.next() : null; } else if (cmp < 0) { // a 小，a 往后走 a = i1.hasNext() ? i1.next() : null; } else { // b 小，b 往后走 b = i2.hasNext() ? i2.next() : null; } } }

前提是两个表必须有序，否则「小的往前走」这个逻辑就不成立。时间复杂度是O(M+N)，每个元素最多访问一次。并集只需在相等时只收一个、不相等时两边都收。这里用ListIterator而不是按下标get(i)，是有讲究的：链表按下标访问是O(N)，用迭代器往前走是O(1)。数据结构决定了你该用什么样的操作方式，这就是最直接的体现。

4.3 迭代器的边界条件

原文里查找元素的contains实现，把「边界」两个字的分量写得明明白白：

// 在带头尾哨兵的双链表中查找 x public boolean contains( AnyType x ) { Node<AnyType> p = beginMarker.next; while (p != endMarker && !p.data.equals(x)) { p = p.next; } return p != endMarker; }

两个终止条件缺一不可。只写!p.data.equals(x)，走到表尾哨兵时data可能是null，直接空指针；只写p != endMarker，就永远停不下来。教材里另一道打印指定位置元素的题，用两个迭代器同步前进，内层还要用计数器start对齐位置，并且必须检查iterL.hasNext()，因为待查的位置可能超过链表长度。

约瑟夫环那道题则是「边界 + 取模」的组合练习：每次数 M 个删除一个，优化点是把 M 对当前人数取模，避免绕圈多次；当 M 超过一半时，还可以把正向的 M 等价成反向的M - N。这些技巧单独看都不难，难的是把它们同时用对。

5. 常见误区：这些概念最容易搞混的地方

5.1 大 O 小就等于跑得快

易混点：看到O(log N)就认定它一定比O(N)快。 为什么混：大 O 忽略了常数因子和低阶项，而实际运行时间恰恰被这两样东西影响。 怎么区分：大 O 描述的是 N 趋于无穷时的趋势，N 很小时它没有发言权。数据量只有几十条的时候，一个O(N)的简单循环，很可能比一个O(log N)但常数巨大的复杂结构更快。原文在增长率排序里明确说N log N和N log(N^2)同阶，就是在提醒：常数不进大 O，但常数在真实机器上是要花时间的。

5.2 递归一定比迭代慢

易混点：把「递归有函数调用开销」直接等同于「凡递归都不好」。 为什么混：教材里的递归代码往往又短又优雅，但栈溢出和重复计算也是真实存在的坑。 怎么区分：看问题的结构。像统计二进制 1 的那种递归，每层规模减半、没有重复子问题，写起来清楚，代价也不高；而朴素的斐波那契递归会指数级重复计算同一个子问题，那就必须改成迭代或者加记忆化。原文在处理文件包含时专门维护一张「未处理完的文件列表」来防止递归死循环，这说明递归的风险不在「递归」本身，而在「你有没有给它一个可靠的终止条件」。

5.3 最坏情况就是平均情况

易混点：分析复杂度时只算最坏，或者只算平均，把两者当成一回事。 为什么混：教材为了保险，常常直接给一个最坏上界，久而久之就让人以为只有这一种。 怎么区分：原文讨论三种洗牌算法时，第一种的期望时间是O(N log N)，但最坏情况无法给出有限上界，因为理论上它可能一直随机到重复的数；第三种算法的最坏情况也是线性的，因为它不依赖随机数的运气。选算法时要问自己：这个场景能不能容忍「偶尔但可能很糟」？面向真实用户的产品，最坏情况往往才是底线。

5.4 数据结构就是算法

易混点：把这两个词当成同义词，觉得学一个就等于学了另一个。 为什么混：教材名字把它们连在一起，题目也是混着出的。 怎么区分：数据结构管「怎么存」，数组、链表、栈、队列都是存法；算法管「怎么算」，排序、查找、递归都是算法。存法会反过来限制算法能怎么走：有序数组能二分，链表就不能随机访问。原文求交集时坚持用迭代器而不是下标，就是「数据结构约束算法写法」的活例子。

5.5 复杂度里的 N 永远等于元素个数

易混点：看到 N 就默认它是数组长度或数据条数。 为什么混：大多数入门例子确实如此，形成了思维定式。 怎么区分：N 是「问题规模」的度量，具体指什么要看问题本身。原文有一道判素题，输入是一个整数，如果拿数值本身当 N，试除到√N看着还行；但真正的规模应该用位数 B 来衡量，因为一个 20 位的数翻倍到 40 位，试除代价会从√N级别跳到指数级。原文明确说 B 比 N 更能代表输入大小。这条最容易被忽略，也最容易在面试里被追问。

6. 什么时候该翻这份答案、什么时候别翻：一份习题答案的边界

这份第三版习题答案不是一个「从头读到尾」的教程，它更像一本对照手册。用对了地方，它能帮你把卡住的思路打通；用错了地方，它会变成一本让你产生「我都会了」错觉的答案集。

适合翻的场景很具体：某道题想了半小时还是没思路，看一眼它的切入角度，然后合上答案自己重写一遍；自己分析出的复杂度不确定，拿它的上界对照一下，看是不是漏掉了某个循环；复习时想快速过一遍链表指针、归并、递推这些高频考点，把它当提纲用。不适合的场景同样具体：直接抄结果交作业，抄完脑子里什么都没留下；把答案里的结论当成唯一标准，不去想它为什么这么估；用它代替系统学习，跳过了自己推导的那一步。

举个具体例子。某开发者在做课程设计时写双链表的结点交换，next改对了，prev漏了一条，运行起来前向遍历正常、反向遍历直接乱掉，查了两个小时没找着。后来翻到这份答案，注释里明明白白写着「双链表每条 next 都要配一条 prev」。他说那一刻不是学会了什么新知识，而是意识到自己画图时只画了单向的箭头。这种错误，答案本身救不了你，但答案旁边的注释能提醒你去补那张图。

从那以后我每次写链表指针操作，都先在纸上画出三个方框、连好所有线，确认每条链都有来有回，再动手敲键盘。这个习惯比任何一份答案都值钱。希望帮到你。

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