简介：这份《数据结构与算法分析（Java语言描述）》第三版习题答案，面向正在学习数据结构、算法分析与Java程序设计的学生及自学者，用于对照教材章节核验解题思路、补齐证明与复杂度分析中的薄弱环节。压缩包共1个docx文档，约1.52MB，内容以英文习题解答为主，覆盖递归实现、文件包含处理、数学归纳法、数列求和、模运算与指数定律、大O估计等典型题目。已有2435人学习，适合作为课后练习的参考材料。文档不仅给出结论，还保留推导过程与代码片段，例如processFile的递归调用、ones函数的递归写法，以及利用差分技巧化简级数、借助模运算证明2^100 mod 5等，便于读者理解教材中从数学推理到程序实现的衔接。整体体积轻便，适合按章节检索，也可用于考前梳理递归、求和与复杂度估计等核心知识点。

1. 递归题的“反直觉”开场：Java数据结构与算法分析先考你会不会说清边界

Java数据结构与算法分析这份第三版习题答案里，最容易让人误判的是递归题：代码只有三四行，面试官却能沿着终止条件、规模递减、复杂度三处一路追问到翻车。这场考试和面试真正考的不是背答案，而是你能不能先把输入范围、递归出口、每层做什么说清，再落代码，最后补上时间空间复杂度。拿分顺序通常是“语义—边界—复杂度—代码”，代码写得快反而排在后面。适合正在刷第三版习题、准备课程笔试和Java后端面试的人，先把这类题练成可复述的答题骨架，比从头到尾抄答案更稳。

2. 复杂度与证明：增长阶判定、递归计数、归纳法三段式

2.1 考什么：增长阶判定表与大O答题骨架

复杂度分析是这门课的第一道分水岭。题目往往不给代码，只给一串函数，让你按增长速率排序，或者判断两个复杂度结论是否成立。原文里出现的序列很典型：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。排序时先看数量级，再看同阶里的常数和对数因子。N log N 与 N log(N²) 其实是同一档，因为 log(N²)=2logN，只差常数倍；N log² N 比 N log N 高，但仍低于 N^1.5。

答题时不要一上来写“O(N²)”。先定输入规模 N 代表什么，再选基本操作，例如比较、赋值、循环体里的加法；接着数执行次数，写出求和式；最后去掉低阶项和常数。面试官最爱听的是“我先假设数组长度为 N，基本操作是比较，循环执行 N 次，内层最多 N 次，所以上界是 O(N²)，最坏情况在第几次比较发生”。这句话比只写一个 O 更有说服力。

原文有一类判断题会把“各自是 O(f)”偷换成“乘积仍是 O(f)”。比如 T1(N)=2N、T2(N)=N、f(N)=N，两个函数各自都是 O(N)，但 T1·T2=2N²，不是 O(N)。答题时要先复述命题，再给反例，最后说明“O 的乘法不能这样合并”。这类题不要求你推翻整个结论，只要求你抓住一个反例，把边界说死。

2.2 真题演练：ones递归与文件递归的答题思路

先看一个经典递归题。原文给出的代码是：

public static int ones(int n) { if (n < 2) { return n; // 0 或 1 直接返回 } return n % 2 + ones(n / 2); // 当前最低位 + 高位中 1 的个数 }

这段代码统计的是整数 n 的二进制表示中有多少个 1，不是十进制各位数字之和。很多人看函数名和递归形式就凭感觉答“求个位数”，一开口就偏。答题思路可以分四步：第一，声明输入 n 为非负整数；第二，终止条件是 n<2，此时返回 n；第三，每层取 n%2 作为当前最低位，规模变成 n/2，严格递减；第四，递归深度是二进制位数，时间复杂度 O(log n)，空间复杂度 O(log n)。如果面试官追问迭代写法，可以把递归改成循环，用 count 累加 n&1，再 n>>>=1，空间降到 O(1)。

文件包含递归是另一道容易答散的题。题目要求写 processFile(String fileName)，打开文件、处理内容、关闭文件；如果读到 #include SomeFile，就递归处理被包含文件。答题时不能只写“递归调用”，要把自引用检测说出来。可以用一个 active 集合记录当前调用链上尚未结束的文件，用 done 集合记录已经处理完的文件：

void processFile(String fileName, Set<String> active, Set<String> done) { if (done.contains(fileName)) { return; // 已处理过，避免重复展开 } if (active.contains(fileName)) { throw new IllegalStateException("cyclic include"); } active.add(fileName); // 打开文件，逐行读取；这里省略 I/O 细节 for (String line : readLines(fileName)) { if (line.startsWith("#include ")) { String next = line.substring("#include ".length()).trim(); processFile(next, active, done); // 递归处理被包含文件 } else { processLine(line); // 普通行交给处理逻辑 } } active.remove(fileName); done.add(fileName); }

参数 active 是“当前递归栈”，done 是“已完成缓存”。active 用来发现 A 包含 B、B 又包含 A 的自引用；done 用来避免同一个文件被重复处理。复杂度按总行数加包含边数估算，最坏是 O(总行数+文件数)。答题时先讲清楚这两个集合的作用，再讲关闭文件和异常路径，面试官会认为你真正写过文件处理，而不是只背了递归模板。

2.3 数学归纳与和式：证明题三段式

证明题在习题答案里占比不低，常见形式是“证明某个不等式对所有 N 成立”“求某个和式的闭式”“用模运算算指数”。答题不要只写“显然成立”，要按三段式展开：基础情况、归纳假设、推导结论。以对数不等式为例，先验证小范围成立，再假设 p<X≤2p 时成立，接着取 2p<Y≤4p，把 logY 拆成 1+log(Y/2)，再用假设放缩，最后得到 logY<Y。每一步都要写“用了哪条假设”，否则过程分很容易丢。

和式题先找差分技巧。比如 S=1+2/4+3/16+…，把 S 和 S/4 错位相减，得到 3S/4 的简单和，再解出 S。答题时把“设 S”“乘公比”“相减”“化简”四行写清楚，比直接写答案更稳。模运算题也一样，2^100 mod 5 不要硬算，先找周期：2^4≡1(mod5)，100 是 4 的倍数，所以 2^100≡1(mod5)。答题话术是“我先找模运算的循环节，再把指数化简到周期内”。

递推数列的求和证明常考“前缀和”。设 F_i=F_{i-1}+F_{i-2}，要证前 N 项和等于某一项减常数，归纳时把前 k 项和拆成前 k-1 项和加第 k 项，再用假设替换。易错点是把归纳假设的适用范围写错，或者在推导中直接把结论当前提。考场上的补救办法是：每一步后面括号注明“基础”“假设”“代入”“化简”，让阅卷人看到你的逻辑链。

提示：复杂度题先写“输入规模是什么”，证明题先写“对哪个变量归纳”，这两句话能救回很多过程分。

3. 线性结构：链表交换、有序表交并、洗牌算法的指针与概率

3.1 单链表swapWithNext：指针顺序是评分点

链表交换是典型的“代码短、翻车多”。题目给一个前驱节点 beforeP，要求交换它后面的两个相邻节点。答题时先画三格：beforeP → p → afterP。交换后希望变成 beforeP → afterP → p。代码可以写成：

public static <AnyType> void swapWithNext(Node<AnyType> beforeP) { if (beforeP == null || beforeP.next == null || beforeP.next.next == null) { return; // 少于两个可交换节点，直接返回 } Node<AnyType> p = beforeP.next; // 第一个待交换节点 Node<AnyType> afterP = p.next; // 第二个待交换节点 p.next = afterP.next; // p 接到 afterP 后面 afterP.next = p; // afterP 指回 p beforeP.next = afterP; // 前驱接到新的第一个节点 }

参数 beforeP 必须非空，且它后面至少有两个节点；否则直接返回。指针顺序的核心是“先接后断”：先让 p.next 指向 afterP 的后继，保住后半段链表；再让 afterP.next 指向 p；最后让 beforeP.next 指向 afterP。如果先改 beforeP.next，p 的引用还在，但后续顺序容易乱；如果先改 afterP.next，可能丢掉 afterP 原来的后继。复杂度是 O(1)，只用了几个引用。

面试追问通常会往双链表走。双链表交换时除了 next，还要改 prev：p.next=afterP.next；beforeP.next=afterP；afterP.next=p；p.next.prev=p；p.prev=afterP；afterP.prev=beforeP。答题时先说“单链表只给 p 不给前驱，无法在 O(1) 内交换，因为找不到前一个节点”，再给双链表版本。这个追问考的是你有没有意识到“前驱信息”是链表操作的成本。

3.2 有序表交并集：双指针模板与去重规则

有序表求交集、并集是线性结构里的高频代码题。输入 L1、L2 已经按升序排好，要求把公共元素放进 Intersect，或者把合并结果放进 Result。答题先声明前提：两个表有序、元素可比较、结果容器是否允许重复。原题代码用 ListIterator 双指针推进，核心是比较当前两个元素：

public static <AnyType extends Comparable<? super AnyType>> void intersection(List<AnyType> L1, List<AnyType> L2, List<AnyType> out) { 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) { out.add(a); // 公共元素 a = i1.hasNext() ? i1.next() : null; b = i2.hasNext() ? i2.next() : null; } else if (cmp < 0) { a = i1.hasNext() ? i1.next() : null; // a 太小，推进 L1 } else { b = i2.hasNext() ? i2.next() : null; // b 太小，推进 L2 } } }

交集的时间复杂度是 O(m+n)，空间复杂度看结果容器，额外指针是 O(1)。并集只需在 cmp<0 时把 a 放进结果，cmp>0 时把 b 放进结果，相等时放一个，避免重复。答题时要把“相等时两个指针都推进”说清楚，否则重复元素会卡住。面试官常追问“如果表里有重复元素，交集要不要输出多次”，这时要先确认规则：每个公共值输出一次，还是按出现次数输出。规则不同，指针推进方式不同。

还有一道 printLots 题：给表 L 和位置表 P，按 P 中的位置打印 L 中对应元素。思路是双迭代器，一个扫 L，一个扫 P，记录当前走到 L 的第几个位置。易错点是把位置从 0 开始还是从 1 开始搞混，以及 P 中位置越界时怎么处理。答题时先声明“位置按题目约定从 0 开始，越界返回或抛异常”，再写循环。

3.3 栈队列与随机排列：为什么第三种洗牌更稳

随机排列题在习题里很能拉开差距。原文比较了三种算法：第一种每次随机选一个数，再检查是否用过；第二种在选数时缩小候选范围；第三种先让数组保持原样，再从后往前随机交换。第一种的期望时间大约 O(N log N)，因为随着已选元素增多，重复抽取的概率上升；第二种省掉一部分重复检查，平均仍是 O(N log N) 量级；第三种是线性时间，而且每个排列等概率。答题时要区分“期望时间”和“最坏时间”，不要混着说。

从后往前洗牌的代码可以写成：

void shuffle(int[] a, Random random) { for (int i = a.length - 1; i > 0; i--) { int j = random.nextInt(i + 1); // j 的范围是 0..i int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }

参数 i 从最后一个下标开始，j 在 0 到 i 之间取，保证当前元素与“尚未固定”的某个元素交换。循环不变量是“i 右边的元素已经固定”。如果 j 的范围写成 0..n-1，每个排列不再等概率，这是最常见的概率翻车点。复杂度 O(N)，额外空间 O(1)。面试追问“最坏情况”时，第三种算法的最坏时间也是线性的，因为循环次数固定；第一种算法则可能一直抽到重复元素，最坏情况没有有限上界，但以概率 1 终止。答题时把这两句话分开说，逻辑就稳了。

4. 算法设计：二分边界、矩阵线性查找、快速幂的答题骨架

4.1 二分搜索的边界：low=1、high=2时mid不前进

二分搜索的代码人人会写，边界却年年有人错。原文有一道题专门指出：low=1、high=2 时，mid=(low+high)/2 得到 1，如果目标在右半边，递归调用仍然从 low=1 开始，区间没有缩小，形成死循环。答题时先把循环不变量写出来：目标若存在，一定在 [low, high] 内；每次比较后，新区间必须严格变小。代码可以写成：

public static int binarySearch(int[] a, int target) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) >>> 1; // 无符号右移，避免溢出 if (a[mid] < target) { low = mid + 1; // 目标在右半边，跳过 mid } else if (a[mid] > target) { high = mid - 1; // 目标在左半边，跳过 mid } else { return mid; // 找到 } } return -1; // 未找到 }

参数 a 必须有序，low 和 high 是闭区间。循环条件是 low<=high，退出时区间为空。mid 用 (low+high)>>>1 可以避免 low+high 溢出。答题时先讲“为什么 low=mid+1 而不是 low=mid”，再讲“为什么 high=mid-1”，最后补复杂度 O(log N)。如果面试官问“有重复元素怎么找第一个和最后一个”，就在找到后继续向左或向右收缩，不要直接返回。

递归版二分更容易出边界问题。答题模板是：终止条件写 low>high；取 mid 后，若走右半边，low=mid+1；若走左半边，high=mid-1；任何一边都不能让 mid 原地不动。原文的 low=1、high=2 就是反面例子。把这个反例主动说出来，比等面试官追问更加分。

4.2 有序矩阵查找与最大差：线性扫描怎么证明

有序矩阵查找的题目通常给一个每行升序、每列升序的矩阵，要求判断目标值是否存在。从左上角出发会同时面对两个方向，不好决策；从右上角出发，每次比较都能排除一行或一列。代码可以写成：

boolean find(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int row = 0; int col = matrix[0].length - 1; // 从右上角开始 while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] > target) { col--; // 当前列下面的都更大，排除这一列 } else { row++; // 当前行左边的都更小，排除这一行 } } return false; }

参数 matrix 的行数和列数可以不同，复杂度是 O(m+n)，因为 row 只增加、col 只减少，总共走 m+n 步。答题时要讲“不变量”：当前右上角元素把矩阵分成三块，目标不可能在已排除的区域。易错点是从左下角也能做，但方向要反过来；从左上角做则无法一次排除一行或一列。

最大差题给一个数组，求 a[j]-a[i] 的最大值，其中 i≤j。做法是维护当前遇到的最小值 minSoFar 和最大差 best。遍历到 x 时，先算 x-minSoFar 更新 best，再用 x 更新 minSoFar。顺序不能反：如果先用 x 更新 minSoFar，再算差，可能把当前元素当成买入点又当成卖出点，虽然 i=j 允许差 0，但逻辑上容易乱。复杂度 O(N)，空间 O(1)。答题时把“低点必须在高点之前”这句话说出来，面试官就知道你理解了下标约束。

4.3 快速幂与幂表：O(log N)乘法的推导

快速幂是算法设计里的常客。原文要求计算 X^N，并讨论预处理 X²、X⁴、X⁸ 等幂表，再按 N 的二进制表示相乘。代码可以写成：

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; // base 依次变成 x^2, x^4, x^8... n >>= 1; // 看下一位 } return result; }

参数 n 按非负整数处理，base 保存当前平方幂，result 保存已经乘入的因子。循环次数是二进制位数，时间复杂度 O(log N)。原文还给出乘法次数的精确估计：N>1 时，乘法次数约为 floor(log N)+b(N)-1，其中 b(N) 是二进制中 1 的个数；N=0 或 1 时乘法次数为 0。答题时先写“把指数拆成二进制”，再写“遇到 1 就乘，平方每次翻倍”，最后补乘法次数。易错点是没有处理 n=0、结果溢出、负数指数。n=0 返回 1；结果可能溢出时用 long 或按模运算处理；负数指数通常不在这个模板范围内。

5. 易错题：四个高频失分点与考场补救答法

5.1 递归终止与规模递减写反

错在哪：只写了一个 if(n<2) return n，却没有保证每次递归都朝终止条件走。比如把 ones(n/2) 写成 ones(n-1) 或 ones(n/2+1)，代码看起来像递归，实际可能永远到不了出口。为什么错：递归题评分不只看返回值，还看“规模是否严格变小”。怎么答对：先写终止条件，再写规模递减表达式，最后写本层贡献。以 ones 为例，本层贡献是 n%2，下一层是 n/2，n 每次至少减半，深度 O(log n)。考场上如果不确定，拿 n=0、1、2、3 手动走一遍，把每层参数写在草稿纸上。

5.2 复杂度把循环上界直接相乘

错在哪：看到三层循环就写 O(N³)，看到五层循环就写 O(N⁵)。原文有一道题，最内层 if 语句最多执行 N³ 次，但条件为真的次数只有 O(N²)，真正进入的内层循环次数是 O(N²)，每次花 O(N²)，总复杂度是 O(N⁴)，不是 O(N⁵)。为什么错：循环头的上界不等于循环体的实际执行次数，条件判断会过滤掉大量情况。怎么答对：数“基本操作真正执行了多少次”，不要数 for 语句出现了几层。可以在草稿上写“外层 i 从 1 到 N，内层只在条件成立时进入，成立次数是 i 次，所以总进入次数是平方级”。面试官听到这种计数方式，就知道你不是凭眼睛估。

5.3 链表交换先改前驱指针

错在哪：写 swapWithNext 时先执行 beforeP.next=afterP，再改 p.next 和 afterP.next。单看引用 p 还在，但一旦后续顺序写错，链表后半段就丢了。双链表版本还经常忘记改 p.next.prev 或 afterP.prev。为什么错：链表题没有下标兜底，指针一断就找不回来，评分点就在“改指针的顺序和完整性”。怎么答对：先画三格，标 beforeP、p、afterP；保存 p 和 afterP 两个引用；按“先接后断”写：p.next=afterP.next，afterP.next=p，beforeP.next=afterP；双链表再补 prev。写完立刻检查头尾、空链表、只有一个节点、交换最后两个节点四种情况。

5.4 随机算法最坏情况和期望情况混答

错在哪：被问“这个洗牌算法的时间复杂度”时，直接答 O(N)，不区分算法。第三种从后往前交换的洗牌确实是 O(N) 最坏；第一种随机选未用元素的算法，期望 O(N log N)，但最坏情况没有有限上界，因为可能一直抽到重复元素。为什么错：随机算法的“最坏”与“期望”是两个评价维度，混在一起答会显得概念不清。怎么答对：先分类“这是随机算法”，再分别说“期望时间”和“最坏时间”。第三种算法循环次数固定，最坏也是线性；第一种算法以概率 1 终止，但不能给一个固定的最坏上界。答题时把“以概率 1 终止”这句话补上，逻辑就完整。

5.5 数学证明只写结论不写归纳假设

错在哪：证明题写“由归纳法可知成立”，中间没有基础情况、没有假设、没有推导。为什么错：证明题按步骤给分，结论只占一小部分。怎么答对：固定四行：基础情况验证；假设对某个范围成立；取下一个范围并代入假设；化简得到结论。和式题再加一行“错位相减”或“差分”。模运算题先写周期，再写指数化简。哪怕最后化简卡住，把“我准备对 N 归纳，假设对 k 成立，下面推导 k+1”写出来，也能拿到过程分。考场上的后悔药就是：每道证明题先写这三句，再开始推。

6. 答题卡练法：把第三版习题答案压缩成可复述的步骤

最后一周不要从第一页翻到最后一页，那很容易变成“看答案都懂，合上书不会”。更稳的做法是给每道题做一张四格答题卡：输入与前提、核心不变量、复杂度、边界检查。比如递归题写“n 非负；每层 n/2；O(log n)；n=0、1 手动走”；链表题写“beforeP 后至少两个节点；先接后断；O(1)；空表、尾节点”；二分题写“数组有序；区间严格缩小；O(log N)；low=1、high=2 反例”。这张卡不是给别人看的，是让你在面试白板上先说出这四格，再落代码。

练的时候用“关答案复述”代替“反复看”：先看题目，合上答案，在白板或纸上写四格，再写代码，最后对照答案只改错的地方。错题不要只标“粗心”，要标清是“终止条件错”“指针顺序错”“复杂度计数错”还是“证明跳步”。同一类错出现两次，就把它写成一句提醒贴在桌前。从那以后我每次写递归题都强制先写终止条件和规模递减，再写返回值；每次写链表题都先画三格再动指针。希望帮到你。这份第三版习题答案按章整理，适合在你做完一题后对照关键步骤，不必从头读到尾。

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