Relax1000 数据结构 · 第1章 绪论 · 解析

题号查询 · 同章题目

第1章 绪论

本章 26 题；解析册印刷页 2–9。

速对答案（原书）： A B A B C D D D D C C B B D B C B D A B B A A D A B

Q1

速对表原值： A

详细解析标注： A

数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种不同的选择：而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要素，缺一不可。

返回题目

Q2

速对表原值： B

详细解析标注： B

用排除法。由于元素间有次序关系，故排除选项 D 集合，而元素可能存在多个前驱或后继结点，故排除选项 C。该数据结构虽是层次关系，但可能不存在树根，故选项 A 的树型结构不合要求。本题的答案是选项 B，图形结构。

返回题目

Q3

速对表原值： A

详细解析标注： A

I 错误，数据元素是数据结构的基本单位，数据项是构成数据结构的最小单位，不可再分。比如 int 类型数据元素，一个数据元素是一个数据项；而结构体包含若干数据项，此时结构体是数据元素，多个成员是数据项。II 正确，抽象数据结构（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义。III、IV 正确，循环队列和线索二叉树都属于物理结构。

注意：数据项是数据结构中讨论的最小单位，但是有的数据项是结构体是可以再分的，这种称为组合项。(这里不用过分纠结)假设一个运动员包含 6 个数据项:姓名、俱乐部名称、出生日期、参加日期、职务、业绩。其中，出生日期这个数据项又分为3 个数据项:年、月、日，那么出生日期这个数据项称为组合项。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q4

速对表原值： B

详细解析标注： B

同一逻辑结构中，数据元素的数据项个数和每个数据项的类型都要一致。

返回题目

Q5

速对表原值： C

详细解析标注： C

问题规模是 n。〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2表示〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 ⋅ 〔公式/符号见原页版面片段〕2，对所有足够大的 n 成立。即执行时间的上界是〔公式/符号见原页版面片段〕2，系数和低阶部分可以忽略。补充：

• 〔公式/符号见原页版面片段〕 ：上界，即〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 ，最多这么慢

• 〔公式/符号见原页版面片段〕 ：下界，即〔公式/符号见原页版面片段〕 ≥ 〔公式/符号见原页版面片段〕 ，至少这么慢

• 〔公式/符号见原页版面片段〕 ：确界，即〔公式/符号见原页版面片段〕1〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ，上下界都为 f(n)

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

审计旁注（非原文）：作废

题干只给出 O(n²)，表示渐近上界，不能推出执行时间必与 n² 成正比；四个选项都不严格。王道回源：result.md [block: b_17_5]。

Q6

速对表原值： D

详细解析标注： D

逻辑结构分为以下几类：

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q7

速对表原值： D

详细解析标注： D

四大基本物理结构有：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。有序表是逻辑结构中的线性结构。

返回题目

Q8

速对表原值： D

详细解析标注： D

数据类型的定义：一个值的集合和定义在这个值集上的一组操作的总称。各字母含义：D 是数据对象，表示相同性质的数据元素的集合；R 是数据之间存在的关系；P 是数据基本操作。抽象数据类型(Abstract Data Type，ADT)一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括 3 个部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。ADT 是概念上描述问题，DT 是在软件实现上描述问题。

返回题目

Q9

速对表原值： D

详细解析标注： D

因为 x，y 是固定的常数，所以时间复杂度是常数级别的。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q10

速对表原值： C

详细解析标注： C

外面两个 for 循环，执行循环次数分别是 n, n；每次循环执行一次 while 循环，一次 while 循 环 的 时 间 开 销 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕5〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ， 所 以 整 个 时 间 复 杂 度 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 ∗ 〔公式/符号见原页版面片段〕 ∗ 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q11

速对表原值： C

详细解析标注： C

对于 sum第一次：sum = 0 + 1 = 1第二次：sum = 1 + 2 = 3第三次：sum = 3 + 3 = 6第四次：sum = 6 + 4 = 10 ……直到 sum > n 时停止。这段代码本质上是构造前 k 个自然数的和：1 + 2 + 3 + ⋯ + 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕+1 2。设执行完循环后 sum>nsum > nsum>n，即：〔公式/符号见原页版面片段〕+1 2 > 〔公式/符号见原页版面片段〕我们粗略估算数量级关系：〔公式/符号见原页版面片段〕2 2 > 〔公式/符号见原页版面片段〕 ⇒ 〔公式/符号见原页版面片段〕2 > 2〔公式/符号见原页版面片段〕 ⇒ 〔公式/符号见原页版面片段〕 > 2〔公式/符号见原页版面片段〕，因此循环次数〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕 ，答案选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q12

速对表原值： B

详细解析标注： B

外层循环：i 从 1 到 n-2（包含），所以执行次数为 n−2 次（近似为 O(n)）。内层循环：对每个 i，j 从 n 递减到 i，即执行 n - i + 1 次。我们要求的是语句 S 被执行的总次数：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕−2 〔公式/符号见原页版面片段〕 + 1 − 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕=3 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕+3 〔公式/符号见原页版面片段〕−2 2，答案选 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q13

速对表原值： B

详细解析标注： B

外层循环：i 从 1 到 n，共执行 n 次；内层循环：对每个 i，j 从 i 到 n，共执行 n−i+1 次（当 i≤n 时）我们要计算语句 count ++ 总共执行了多少次：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕=1 ⌊〔公式/符号见原页版面片段〕/2⌋ 〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕 + 1 ，令〔公式/符号见原页版面片段〕 = ⌊〔公式/符号见原页版面片段〕/2⌋，有〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕 + 1 =〔公式/符号见原页版面片段〕+〔公式/符号见原页版面片段〕−〔公式/符号见原页版面片段〕+1 2 =〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕−〔公式/符号见原页版面片段〕+1 2 = 〔公式/符号见原页版面片段〕2，答案选 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q14

速对表原值： D

详细解析标注： D

该算法为矩阵乘法，所有语句频度之和，是矩阵阶数 n 的函数，用 f(n)表示之。换句话说，上例算法的执行时间与 f(n)成正比：〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕3 + 3〔公式/符号见原页版面片段〕2 + 2〔公式/符号见原页版面片段〕 + 1，即时间复杂度是〔公式/符号见原页版面片段〕3。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q15

速对表原值： B

详细解析标注： B

〔公式/符号见原页版面片段〕={1,3,5，⋯,2〔公式/符号见原页版面片段〕+1} (2〔公式/符号见原页版面片段〕+1<=〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕=1,2,4,⋯,2〔公式/符号见原页版面片段〕 (2〔公式/符号见原页版面片段〕<=〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 1 =〔公式/符号见原页版面片段〕={1,3,5，⋯,2〔公式/符号见原页版面片段〕+1} (2〔公式/符号见原页版面片段〕+1<=〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕=1,2,4,⋯,2〔公式/符号见原页版面片段〕 (2〔公式/符号见原页版面片段〕<=〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕={1,3,5，⋯,2〔公式/符号见原页版面片段〕+1} (2〔公式/符号见原页版面片段〕+1<=〔公式/符号见原页版面片段〕) (1 + 2 + 4 + ⋯ + 2〔公式/符号见原页版面片段〕) =〔公式/符号见原页版面片段〕={1,3,5，⋯,2〔公式/符号见原页版面片段〕+1} (2〔公式/符号见原页版面片段〕+1<=〔公式/符号见原页版面片段〕) 2〔公式/符号见原页版面片段〕+1 − 1(2〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕) =〔公式/符号见原页版面片段〕={1,3,5，⋯,2〔公式/符号见原页版面片段〕+1} (2〔公式/符号见原页版面片段〕+1<=〔公式/符号见原页版面片段〕) (2〔公式/符号见原页版面片段〕 − 1) =〔公式/符号见原页版面片段〕≈〔公式/符号见原页版面片段〕/2(2〔公式/符号见原页版面片段〕 − 1)(〔公式/符号见原页版面片段〕/2) = 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2)

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q16

速对表原值： C

详细解析标注： C

考虑到内部循环每次执行〔公式/符号见原页版面片段〕次操作。总的执行次数就是〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕，即 O(nlogn)调和级数〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕近似 O(nlogn)证明如下：证 明 下 界 ： 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕=2 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 + 1 ≥ 2 〔公式/符号见原页版面片段〕+1 1 〔公式/符号见原页版面片段〕 + 1 = ln 〔公式/符号见原页版面片段〕 + 1 − ln 2 + 1 = ln 〔公式/符号见原页版面片段〕+1 2 + 1 =ln 〔公式/符号见原页版面片段〕 + 1 ⇒ 〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕证明上界： 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 ≤ 1 + 1 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 = 1 + ln〔公式/符号见原页版面片段〕 ⇒ 〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕 log〔公式/符号见原页版面片段〕综合以上，ln 〔公式/符号见原页版面片段〕 + 1 ≤ 〔公式/符号见原页版面片段〕 ≤ 1 + ln〔公式/符号见原页版面片段〕 ⇒ 〔公式/符号见原页版面片段〕 ∈ 〔公式/符号见原页版面片段〕 log〔公式/符号见原页版面片段〕

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q17

速对表原值： B

详细解析标注： B

〔公式/符号见原页版面片段〕={1,2,4，⋯,2〔公式/符号见原页版面片段〕} 1 〔公式/符号见原页版面片段〕=1 1 〔公式/符号见原页版面片段〕=1 1 1 =〔公式/符号见原页版面片段〕={1,2,4,⋯，2〔公式/符号见原页版面片段〕} 〔公式/符号见原页版面片段〕=1 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕={1,2,4,⋯,2〔公式/符号见原页版面片段〕} 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕 + 1) 2 =1 2 〔公式/符号见原页版面片段〕={1,2,4,⋯,2〔公式/符号见原页版面片段〕} 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕 =1 2 (1 + 4 + 42 + ⋯ + 4〔公式/符号见原页版面片段〕) + 1 2 (1 + 2 + ⋯ + 2〔公式/符号见原页版面片段〕) =1 2 (1 − 4〔公式/符号见原页版面片段〕+1 1 − 4) + 1 2 1 − 2〔公式/符号见原页版面片段〕+1 1 − 2 =4〔公式/符号见原页版面片段〕+1 − 1 6 + 2〔公式/符号见原页版面片段〕+1 − 1 2 →2〔公式/符号见原页版面片段〕∼〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2)

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q18

速对表原值： D

详细解析标注： D

根据递推关系得 T(n)=T(n-1)+T(n-2)+O(1)，可以用递归树展开的方式，树高为 O（n），时间复杂度是递归树的结点个数，显然这是一个指数级时间复杂度。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q19

速对表原值： A

详细解析标注： A

此题也可考察盘子移动次数，难度会更高。设 n 个盘子的汉诺塔问题移动次数为S(n)，推导如下：

①n=1，只需要将这个盘子从源塔移动到目标塔，S(1) = 1；

②分析代码：

• hanoi(n-1, from_rod, aux_rod, to_rod); //将上面的 n-1 个盘子从起始柱子通过目标柱子移动到辅助柱子这个递归的移动次数为 S(n-1)

• 将最大的盘子（第 n 个）从起始柱子移动到目标柱子由

①可知，移动 1 次即可

• hanoi(n-1, aux_rod, to_rod, from_rod);//将那 n-1 个盘子从辅助柱子通过起始柱子移动到目标柱子这个递归的移动次数也为 S(n-1)

③ 〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕 − 1 + 1 → 〔公式/符号见原页版面片段〕 + 1 = 2 〔公式/符号见原页版面片段〕 − 1 + 1 = 22 〔公式/符号见原页版面片段〕 − 2 + 1 = ... = 2〔公式/符号见原页版面片段〕−1 〔公式/符号见原页版面片段〕 1 + 1 = 2〔公式/符号见原页版面片段〕 → 〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕 − 1综上，盘子的移动次数为2〔公式/符号见原页版面片段〕 − 1，即时间复杂度为〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕，答案选 A。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q20

速对表原值： B

详细解析标注： B

此题目的算法的意思是计算出二叉树的最大深度，通过简单地遍历一遍二叉树内的所有结点即可求出结果。此算法的时间复杂度是 O(n)。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q21

速对表原值： B

详细解析标注： B

递归关系式为 T(n)=T(n−1)+O(1)，为什么这里是 O（1）不是 O（n），因为 * n是单个乘法操作，时间消耗为常数。展开递归：T(n)=T(n−1)+O(1)=(T(n−2)+O(1))+O(1)=(T(n−3)+O(1))+ O(1)+O(1)=...=T(1)+O(n)。因为 T(1) = O(1)，最终得：T(n)=O(n)

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q22

速对表原值： A

详细解析标注： A

【方法一】递归树法。展开第一层，我们画出根节点下面的三个子节点。其中，〔公式/符号见原页版面片段〕2表示根节点这一层分解和合并的代价，也就是递归式中 〔公式/符号见原页版面片段〕2表示的部分。这样就得到了一棵完整的递归树。每层数据规模缩小为之前的四分之一，直到叶子结点数据规模为1，因此总层数为。上图最右侧计算了每层所有结点的总代价，计算方式很简单，就是单个结点的代价乘以该层的结点数量。其中，最后一层单个结点的代价为常数，结点数量为 3〔公式/符号见原页版面片段〕4〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕43，总代价我们记做。接下来，我们只需要把所有结点的代价加起来，就可以得到递归式的解。〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2 + 3 16 〔公式/符号见原页版面片段〕2 + 3 16 2 〔公式/符号见原页版面片段〕2 + ⋯ + 3 16 〔公式/符号见原页版面片段〕4〔公式/符号见原页版面片段〕−1 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕43 =〔公式/符号见原页版面片段〕=0 〔公式/符号见原页版面片段〕4〔公式/符号见原页版面片段〕−1 3 16 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕43 < 〔公式/符号见原页版面片段〕=0 ∞ 3 16 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕43 =1 1 − 3/16 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕43 =16 13 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕43 = 〔公式/符号见原页版面片段〕2【方法二】主定理（直接记结论）递归表达式形如：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕

• 〔公式/符号见原页版面片段〕 > 〔公式/符号见原页版面片段〕 ，则〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕

• 〔公式/符号见原页版面片段〕 < 〔公式/符号见原页版面片段〕 ，且对于某个常数c<1和所有足够大的n有〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 ，则可以推导出〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕 .

• 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 ，则〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕例题

①：〔公式/符号见原页版面片段〕 = 9〔公式/符号见原页版面片段〕 3 + 〔公式/符号见原页版面片段〕对于这个递归式，我们有〔公式/符号见原页版面片段〕 = 9、〔公式/符号见原页版面片段〕 = 3、〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕，此时〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕39 = 〔公式/符号见原页版面片段〕2。由于〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 渐进小于〔公式/符号见原页版面片段〕2，所以可以应用于主定理的第一种情况，从而得到解〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2 .例题

②：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕/3 + 1对于该式，有〔公式/符号见原页版面片段〕 = 1、〔公式/符号见原页版面片段〕 = 3/2、〔公式/符号见原页版面片段〕 = 1，此时〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕3 21 = 〔公式/符号见原页版面片段〕0 = 1，恰好与〔公式/符号见原页版面片段〕 相等，所以可以应用于主定理的第二种情况，从而得到解〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。例题

③：〔公式/符号见原页版面片段〕 = 3〔公式/符号见原页版面片段〕 4 + 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕对于该式，有〔公式/符号见原页版面片段〕 = 3、〔公式/符号见原页版面片段〕 = 4、〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕，此时〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕43 = 〔公式/符号见原页版面片段〕0.793。显然〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕渐进大于〔公式/符号见原页版面片段〕0.793，应考虑主定理的第三种情况。但需要检查是否满足附加条件：对于某个常数 c<1 和所有足够大的 n 有〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 。带入〔公式/符号见原页版面片段〕、〔公式/符号见原页版面片段〕和〔公式/符号见原页版面片段〕 ，得3 〔公式/符号见原页版面片段〕 4 lg 〔公式/符号见原页版面片段〕 4 ≤ 〔公式/符号见原页版面片段〕 3 4 (〔公式/符号见原页版面片段〕 − 2) ≤ 〔公式/符号见原页版面片段〕 3 4 − 〔公式/符号见原页版面片段〕 ≤ 3 2 〔公式/符号见原页版面片段〕 ≥ 3 4时，该式恒成立，附加条件满足，可以应用主定理的第三种情况，从而得到解〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕例题

④：〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕 2 + 〔公式/符号见原页版面片段〕对于该式，有〔公式/符号见原页版面片段〕 = 2、〔公式/符号见原页版面片段〕 = 2、〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕，此时〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕22 = 〔公式/符号见原页版面片段〕。显然，〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕渐进大于 n，应考虑主定理的第三种情况。将其带入附加条件，得2 〔公式/符号见原页版面片段〕 2 lg 〔公式/符号见原页版面片段〕 2 ≤ 〔公式/符号见原页版面片段〕 − 1 ≤ 〔公式/符号见原页版面片段〕 1 − 〔公式/符号见原页版面片段〕 ≤ 1

• 当〔公式/符号见原页版面片段〕 ≥ 1 时，该式恒成立。但附加条件要求 c<1，因此该式不能使用主方法的第三种情况。也就是说，并非所有形如〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 的递归式都可以应用主方法求解，情况二和情况三之间是存在空隙的。这种情况我们就只能采用递归树的方法求解了，同学们可以试一下，求出来的结果为〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 .

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q23

速对表原值： A

详细解析标注： A

【方法一】代入法〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕 2 + 〔公式/符号见原页版面片段〕 = 2（2〔公式/符号见原页版面片段〕 4 + 〔公式/符号见原页版面片段〕 2 ） + 〔公式/符号见原页版面片段〕 = 4〔公式/符号见原页版面片段〕 4 + 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 = 4〔公式/符号见原页版面片段〕 4 + 2〔公式/符号见原页版面片段〕 = 4 2〔公式/符号见原页版面片段〕 8 + 〔公式/符号见原页版面片段〕 4 + 2〔公式/符号见原页版面片段〕 = 8〔公式/符号见原页版面片段〕 8 + 3〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕适合代入法的例子：12 年真题阶乘C int fact(int n) { if (n <= 1) return 1; else return n * fact(n - 1); } 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕) =〔公式/符号见原页版面片段〕(1) 〔公式/符号见原页版面片段〕 ≤ 1 〔公式/符号见原页版面片段〕(1) + 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕 − 1) 〔公式/符号见原页版面片段〕 > 1 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 − 1 = 〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 − 1 = 2〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 − 2 = ... = 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 1 = 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 1 + 〔公式/符号见原页版面片段〕 1 = 〔公式/符号见原页版面片段〕 1 = 〔公式/符号见原页版面片段〕【方法二】递归树法。根据递归式，其中 2〔公式/符号见原页版面片段〕（〔公式/符号见原页版面片段〕/2）是每次递归都会产生 2 个子递归，规模变为原来的 1/2，且每次参数为 n 的递归中，for 循环累计求和的开销是〔公式/符号见原页版面片段〕 。那么我们可以画出一棵递归树：递归树的高度为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕，每层的工作量如下：

• 第 0 层（根层）：执行 〔公式/符号见原页版面片段〕

• 第 1 层：执行 2 × 〔公式/符号见原页版面片段〕 2 = 〔公式/符号见原页版面片段〕

• 第 2 层：执行 4 × 〔公式/符号见原页版面片段〕 4 = 〔公式/符号见原页版面片段〕

• 第 3 层：执行 8 × 〔公式/符号见原页版面片段〕 8 = 〔公式/符号见原页版面片段〕

• ...每一层的工作量都是 〔公式/符号见原页版面片段〕 ，递归树有log2〔公式/符号见原页版面片段〕层。【方法三】主定理（记结论）递归表达式形如：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕

• 〔公式/符号见原页版面片段〕 > 〔公式/符号见原页版面片段〕 ，则〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕

• 〔公式/符号见原页版面片段〕 < 〔公式/符号见原页版面片段〕 ，且对于某个常数 c<1 和所有足够大的 n 有〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 ，则可以推导出〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕

• 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 ，则〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕回到这题：〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕 2 + 〔公式/符号见原页版面片段〕 = 2, 〔公式/符号见原页版面片段〕 = 2, 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 , 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 , 满足第三种情况，答案为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q24

速对表原值： D

详细解析标注： D

观察程序发现，语句“A[j]与 A[j+1]对换;”执行频率较高，且该语句并不影响双重 for 循环判断语句，但会影响 if 的判断语句。当 A 数组的所有元素都逆序时，语句“A[j]与 A[j+1]对换;”会一直执行，此时为最坏情况。该语句在最坏情况下的频度是〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2)，选 D。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q25

速对表原值： A

详细解析标注： A

可以写出算法的递归表达式是 S(n) = 2×S(n/2) + 1；可以画出该递归式对应的递归树，如下图所示：在最坏情况下，递归会一直分解到 m 等于 n，每次递归将区间一分为二，因此递归深度为O(logn)，选择 A。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q26

速对表原值： B

详细解析标注： B

算法的空间复杂度为 O(1)，表示执行该算法所需的辅助空间大小相比输入数据的规模来说是一个常量，而不表示该算法执行时不需要任何空间或辅助空间。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目