Java数据结构与算法分析习题答案：递归、复杂度与链表二分答题骨架-北京尧图网络

简介这份《数据结构与算法分析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。表达式增长阶常见误判2/N、37O(1)把 2/N 当成比 1 大√N、NO(√N)、O(N)忽略根号与线性的差距N log N、N log(N²)同为 O(N log N)把 log(N²) 当成新阶N log² NO(N log² N)与 N log N 混为一谈N^1.5、N²多项式不同阶只看指数不看底数2^(N/2)、2^N指数级以为只差常数倍答题时不要一上来写“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·T22N²不是 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 为非负整数第二终止条件是 n2此时返回 n第三每层取 n%2 作为当前最低位规模变成 n/2严格递减第四递归深度是二进制位数时间复杂度 O(log n)空间复杂度 O(log n)。如果面试官追问迭代写法可以把递归改成循环用 count 累加 n1再 n1空间降到 O(1)。文件包含递归是另一道容易答散的题。题目要求写 processFile(String fileName)打开文件、处理内容、关闭文件如果读到 #include SomeFile就递归处理被包含文件。答题时不能只写“递归调用”要把自引用检测说出来。可以用一个 active 集合记录当前调用链上尚未结束的文件用 done 集合记录已经处理完的文件void processFile(String fileName, SetString active, SetString 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 成立”“求某个和式的闭式”“用模运算算指数”。答题不要只写“显然成立”要按三段式展开基础情况、归纳假设、推导结论。以对数不等式为例先验证小范围成立再假设 pX≤2p 时成立接着取 2pY≤4p把 logY 拆成 1log(Y/2)再用假设放缩最后得到 logYY。每一步都要写“用了哪条假设”否则过程分很容易丢。和式题先找差分技巧。比如 S12/43/16…把 S 和 S/4 错位相减得到 3S/4 的简单和再解出 S。答题时把“设 S”“乘公比”“相减”“化简”四行写清楚比直接写答案更稳。模运算题也一样2^100 mod 5 不要硬算先找周期2^4≡1(mod5)100 是 4 的倍数所以 2^100≡1(mod5)。答题话术是“我先找模运算的循环节再把指数化简到周期内”。递推数列的求和证明常考“前缀和”。设 F_iF_{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(NodeAnyType beforeP) { if (beforeP null || beforeP.next null || beforeP.next.next null) { return; // 少于两个可交换节点直接返回 } NodeAnyType p beforeP.next; // 第一个待交换节点 NodeAnyType 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.nextp 的引用还在但后续顺序容易乱如果先改 afterP.next可能丢掉 afterP 原来的后继。复杂度是 O(1)只用了几个引用。面试追问通常会往双链表走。双链表交换时除了 next还要改 prevp.nextafterP.nextbeforeP.nextafterPafterP.nextpp.next.prevpp.prevafterPafterP.prevbeforeP。答题时先说“单链表只给 p 不给前驱无法在 O(1) 内交换因为找不到前一个节点”再给双链表版本。这个追问考的是你有没有意识到“前驱信息”是链表操作的成本。3.2 有序表交并集双指针模板与去重规则有序表求交集、并集是线性结构里的高频代码题。输入 L1、L2 已经按升序排好要求把公共元素放进 Intersect或者把合并结果放进 Result。答题先声明前提两个表有序、元素可比较、结果容器是否允许重复。原题代码用 ListIterator 双指针推进核心是比较当前两个元素public static AnyType extends Comparable? super AnyType void intersection(ListAnyType L1, ListAnyType L2, ListAnyType out) { ListIteratorAnyType i1 L1.listIterator(); ListIteratorAnyType 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(mn)空间复杂度看结果容器额外指针是 O(1)。并集只需在 cmp0 时把 a 放进结果cmp0 时把 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 二分搜索的边界low1、high2时mid不前进二分搜索的代码人人会写边界却年年有人错。原文有一道题专门指出low1、high2 时mid(lowhigh)/2 得到 1如果目标在右半边递归调用仍然从 low1 开始区间没有缩小形成死循环。答题时先把循环不变量写出来目标若存在一定在 [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 是闭区间。循环条件是 lowhigh退出时区间为空。mid 用 (lowhigh)1 可以避免 lowhigh 溢出。答题时先讲“为什么 lowmid1 而不是 lowmid”再讲“为什么 highmid-1”最后补复杂度 O(log N)。如果面试官问“有重复元素怎么找第一个和最后一个”就在找到后继续向左或向右收缩不要直接返回。递归版二分更容易出边界问题。答题模板是终止条件写 lowhigh取 mid 后若走右半边lowmid1若走左半边highmid-1任何一边都不能让 mid 原地不动。原文的 low1、high2 就是反面例子。把这个反例主动说出来比等面试官追问更加分。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(mn)因为 row 只增加、col 只减少总共走 mn 步。答题时要讲“不变量”当前右上角元素把矩阵分成三块目标不可能在已排除的区域。易错点是从左下角也能做但方向要反过来从左上角做则无法一次排除一行或一列。最大差题给一个数组求 a[j]-a[i] 的最大值其中 i≤j。做法是维护当前遇到的最小值 minSoFar 和最大差 best。遍历到 x 时先算 x-minSoFar 更新 best再用 x 更新 minSoFar。顺序不能反如果先用 x 更新 minSoFar再算差可能把当前元素当成买入点又当成卖出点虽然 ij 允许差 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)。原文还给出乘法次数的精确估计N1 时乘法次数约为 floor(log N)b(N)-1其中 b(N) 是二进制中 1 的个数N0 或 1 时乘法次数为 0。答题时先写“把指数拆成二进制”再写“遇到 1 就乘平方每次翻倍”最后补乘法次数。易错点是没有处理 n0、结果溢出、负数指数。n0 返回 1结果可能溢出时用 long 或按模运算处理负数指数通常不在这个模板范围内。5. 易错题四个高频失分点与考场补救答法5.1 递归终止与规模递减写反错在哪只写了一个 if(n2) return n却没有保证每次递归都朝终止条件走。比如把 ones(n/2) 写成 ones(n-1) 或 ones(n/21)代码看起来像递归实际可能永远到不了出口。为什么错递归题评分不只看返回值还看“规模是否严格变小”。怎么答对先写终止条件再写规模递减表达式最后写本层贡献。以 ones 为例本层贡献是 n%2下一层是 n/2n 每次至少减半深度 O(log n)。考场上如果不确定拿 n0、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.nextafterP再改 p.next 和 afterP.next。单看引用 p 还在但一旦后续顺序写错链表后半段就丢了。双链表版本还经常忘记改 p.next.prev 或 afterP.prev。为什么错链表题没有下标兜底指针一断就找不回来评分点就在“改指针的顺序和完整性”。怎么答对先画三格标 beforeP、p、afterP保存 p 和 afterP 两个引用按“先接后断”写p.nextafterP.nextafterP.nextpbeforeP.nextafterP双链表再补 prev。写完立刻检查头尾、空链表、只有一个节点、交换最后两个节点四种情况。5.4 随机算法最坏情况和期望情况混答错在哪被问“这个洗牌算法的时间复杂度”时直接答 O(N)不区分算法。第三种从后往前交换的洗牌确实是 O(N) 最坏第一种随机选未用元素的算法期望 O(N log N)但最坏情况没有有限上界因为可能一直抽到重复元素。为什么错随机算法的“最坏”与“期望”是两个评价维度混在一起答会显得概念不清。怎么答对先分类“这是随机算法”再分别说“期望时间”和“最坏时间”。第三种算法循环次数固定最坏也是线性第一种算法以概率 1 终止但不能给一个固定的最坏上界。答题时把“以概率 1 终止”这句话补上逻辑就完整。5.5 数学证明只写结论不写归纳假设错在哪证明题写“由归纳法可知成立”中间没有基础情况、没有假设、没有推导。为什么错证明题按步骤给分结论只占一小部分。怎么答对固定四行基础情况验证假设对某个范围成立取下一个范围并代入假设化简得到结论。和式题再加一行“错位相减”或“差分”。模运算题先写周期再写指数化简。哪怕最后化简卡住把“我准备对 N 归纳假设对 k 成立下面推导 k1”写出来也能拿到过程分。考场上的后悔药就是每道证明题先写这三句再开始推。6. 答题卡练法把第三版习题答案压缩成可复述的步骤最后一周不要从第一页翻到最后一页那很容易变成“看答案都懂合上书不会”。更稳的做法是给每道题做一张四格答题卡输入与前提、核心不变量、复杂度、边界检查。比如递归题写“n 非负每层 n/2O(log n)n0、1 手动走”链表题写“beforeP 后至少两个节点先接后断O(1)空表、尾节点”二分题写“数组有序区间严格缩小O(log N)low1、high2 反例”。这张卡不是给别人看的是让你在面试白板上先说出这四格再落代码。题型答题骨架检查项递归终止条件→规模递减→本层贡献→复杂度n0、1、2 手动展开链表画三节点→保存引用→先接后断→改 prev空表、单节点、尾节点二分有序前提→循环不变量→mid 跳过→返回区间是否严格变小随机算法期望时间→最坏时间→终止概率是否等概率、是否可能不终止证明题基础→假设→代入→结论每步注明用了哪条假设练的时候用“关答案复述”代替“反复看”先看题目合上答案在白板或纸上写四格再写代码最后对照答案只改错的地方。错题不要只标“粗心”要标清是“终止条件错”“指针顺序错”“复杂度计数错”还是“证明跳步”。同一类错出现两次就把它写成一句提醒贴在桌前。从那以后我每次写递归题都强制先写终止条件和规模递减再写返回值每次写链表题都先画三格再动指针。希望帮到你。这份第三版习题答案按章整理适合在你做完一题后对照关键步骤不必从头读到尾。本文还有配套的精品资源点击获取

Java数据结构与算法分析习题答案：递归、复杂度与链表二分答题骨架

相关推荐

SpringBoot考研互助平台开发实践与架构解析

PostgreSQL 15 shared_buffers参数优化指南

Oracle APEX 4.2.5 开发实战：环境搭建与表单动态交互

更多资讯

C语言DOS游戏开发实战：Turbo C图形编程与现代移植

运维自救：Linux一键修复与安装脚本全解析

Hyperframes高密度帧处理：分块流水线与顺序保证实战

接盘十二年遗留系统：尽调、止血与渐进式改造

年入过亿的遗留系统如何接手？技术债治理与渐进改造实战

MySQL备份与恢复全攻略：从基础到企业级实践

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？