简介面向《数据结构与算法分析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) 2NT2(N) Nf(N) N此时T1(N) O(f(N))与T2(N) O(f(N))同时成立但推不出T1(N) O(T2(N))这条看似显然的结论反过来用——题目的陷阱在于让人以为两个函数都是 f 的大 O就自动同阶。再换一组T1(N) N²T2(N) Nf(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 倍为例四种复杂度的结果如下复杂度反解方式可处理规模O(N)规模乘 120001,200,000O(N log N)近似按 N 线性外推后再修正约 425,000O(N²)规模乘 √1200010,954O(N³)规模乘 12000 的三次方根2,289判断“时间变几倍属于哪种复杂度”的题更简单时间变 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) { ListString active new ArrayList(); // 尚未返回的文件名 process(fileName, active); } private void process(String fileName, ListString 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^ii 从 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^i3S 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 ≤ XX 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_{N2} - 2。基础情况验证 N 1、N 2假设对1..k成立在 N k1 时把和拆成Σ_{1}^{k} F_i F_{k1}代入假设得F_{k2} - 2 F_{k1}再用斐波那契定义合并成F_{k3} - 2正好是 N k1 的形式。代数恒等式的证明更看重变形方向。Σ (2i - 1) N²只需拆成2Σ i - Σ 1 N(N1) - N N²。而Σ i³ [N(N1)/2]²的归纳证明需要一次凑配把(N1)³提出来凑成(N1)² [N² 4(N1)] / 4再化回[(N1)(N2)/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⌋ 5b(62) 5111110代入得 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(ListAnyType L1, ListAnyType L2, ListAnyType Intersect) { ListIteratorAnyType it1 L1.listIterator(); ListIteratorAnyType 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(ListAnyType L, ListInteger P) { IteratorAnyType iterL L.iterator(); IteratorInteger 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(N1) - N最后补一句“该式对 N 0 时按空和记作 0同样成立”四句话拿满分。如果只写一个 N²遇上严格阅卷就是半分。代码题的模板反过来先说清楚参数和返回值的含义再写代码代码块之后补三段说明——关键变量的作用、边界条件的处理、时间复杂度的来源。链表交换那道题代码只有六行解释却能写三行beforep是前驱p和afterp是待交换的两个相邻节点三步赋值的顺序由“哪根指针的信息会先丢”决定。这三行解释往往比代码本身更能体现水平。押题方向也给一个粗判据复杂度排序、嵌套循环计数、递归语义、链表指针顺序、二分边界这五类几乎每套卷子都会命中两道以上。考前最后一遍不要重读全书把这五类的错题本过一遍每类挑一道完整写出四步比刷十道新题有用。我自己踩过最狠的一次是把一道嵌套循环题的答案从O(N⁵)改成了O(N⁴)理由是“三层循环怎么可能到五次方”。交卷后才发现内层上界是j而j最大到i²乘起来确实是五次方。从那以后我每次写复杂度结论前都强制走一遍“逐条语句数执行次数、再取最大项”的流程不管直觉多笃定。希望帮到你。本文还有配套的精品资源点击获取
