第1章绪论

2027 王道 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第1章绪论¶

本章帮助整体认识数据结构，重点是算法时间复杂度和空间复杂度的分析方法。⚠️ 统考中无论算法设计题还是选择题，通常都要求分析时间复杂度（有时也含空间复杂度）。

回源 · PDF 第 13 页 · b_13_5

【知识树】第1章骨架¶

基本概念：数据、数据元素、数据项、数据对象、数据类型、数据结构
三要素
逻辑结构：集合 / 线性 / 树形 / 图状
存储结构：顺序 / 链式 / 索引 / 散列
数据的运算：定义（对逻辑结构）+ 实现（对存储结构）
算法
五个特性、四个设计目标
时间复杂度：语句频度、大 O、最好/最坏/平均、加法与乘法规则
空间复杂度：只算辅助空间、原地工作

回源 · PDF 第 13 页 · b_13_3；PDF 第 13 页 · b_13_4

1.1 数据结构的基本概念¶

数据元素和数据项是什么关系？¶

数据：信息的载体，是计算机程序加工的原料
数据元素：⚠️ 数据的基本单位，通常作为一个整体考虑和处理
数据项：⚠️ 构成数据元素的不可分割的最小单位

💡 例子：一条学生记录是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象 = 具有相同性质的数据元素的集合，是数据的一个子集（如整数集 N = {0, ±1, ±2, …}）。

回源 · PDF 第 13 页 · b_13_8

数据类型分哪三种？什么是 ADT？¶

数据类型 = 一个值的集合 + 定义在该集合上的一组操作的总称。 - 原子类型：值不可再分 - 结构类型：值可进一步分解为若干成分（分量） - 抽象数据类型 ADT：⚠️ 一个数学模型以及定义在该模型上的一组操作 —— 规定了取值范围、结构形式、可执行的操作集合

回源 · PDF 第 14 页 · b_14_2；PDF 第 14 页 · b_14_3

数据结构包含哪三方面内容？¶

数据结构 = 相互之间存在一种或多种特定关系的数据元素的集合，包含三方面：逻辑结构、存储结构、数据的运算。

⚠️ 二者的分工（高频考点）：算法的设计取决于所采用的逻辑结构，算法的实现则依赖于所选择的存储结构。

💡 记忆法："设计看逻辑，实现看存储"。

回源 · PDF 第 14 页 · b_14_5；PDF 第 14 页 · b_14_6

四种逻辑结构分别是什么关系？¶

集合：⚠️ 元素之间除"同属一个集合"外别无其他关系
线性结构：一对一
树形结构：一对多
图状（网状）结构：多对多

⚠️ 线性表是典型的线性结构；集合、树、图都是非线性结构。 ⚠️ 逻辑结构与数据在计算机中的存储方式无关，独立于具体系统。

💡 记忆法："无关系 / 一对一 / 一对多 / 多对多"。

回源 · PDF 第 14 页 · b_14_7；PDF 第 14 页 · b_14_9

四种存储结构的优缺点？¶

存储结构（物理结构）= 数据结构在计算机中的表示形式，⚠️ 依赖于所采用的编程语言。

存储结构	优点	缺点
顺序存储	⚠️ 可随机存取，每个元素占用最少的存储空间	⚠️ 要求连续空间，可能产生较多外部碎片
链式存储	不会出现碎片，能充分利用所有存储单元	⚠️ 每个元素因存指针额外占空间，且只能顺序存取
索引存储	检索速度快	⚠️ 索引表要额外空间，增删数据时需更新索引表
散列存储	⚠️ 检索、插入、删除都非常快	散列函数设计不当会产生冲突，解决冲突增加时空成本

💡 顺序存储的本质：逻辑上相邻的元素物理位置也相邻，关系由存储单元的邻接关系体现。

回源 · PDF 第 15 页 · b_15_1；PDF 第 15 页 · b_15_15

数据的运算为什么要分定义和实现？¶

定义：⚠️ 针对逻辑结构，说明运算的功能
实现：⚠️ 基于存储结构，描述具体的操作步骤

💡 这正好对应上面那句"设计取决于逻辑结构，实现依赖于存储结构"。

回源 · PDF 第 15 页 · b_15_4；PDF 第 15 页 · b_15_5

1.2 算法和算法评价¶

算法的五个特性？¶

有穷性：⚠️ 必须在执行有限步后结束，且每一步都能在有限时间内完成
确定性：每条指令有明确含义，⚠️ 相同的输入只能产生相同的输出
可行性：所描述的操作都能通过已实现的基本运算执行有限次来完成
输入：⚠️ 可以有零个或多个输入
输出：⚠️ 至少有一个输出

💡 最常考的两处对比：输入可以是 0 个，输出至少 1 个；有穷性 vs 可行性（前者管步数，后者管每步能不能做）。

回源 · PDF 第 16 页 · b_16_21

好算法的四个目标？¶

正确性：能正确解决所给问题
可读性：结构清晰、便于阅读交流
健壮性：⚠️ 对非法或异常输入能做出适当处理，而不是产生不可预测的结果
高效率与低存储量需求：效率指执行时间，存储量需求指执行过程中所需的最大存储空间，二者都与问题规模密切相关

回源 · PDF 第 17 页 · b_17_0

时间复杂度到底在算什么？　★2考¶

时间复杂度描述执行时间随问题规模 n 增大的变化趋势，是关于 n 的渐近函数。

推导链： - 算法执行时间用语句频度（某条语句的执行次数）衡量，所有语句频度之和记为 T(n) - n 足够大时低阶项和常数系数可忽略 → 只关注 T(n) 中增长最快的项 - ⚠️ 这一项通常由基本运算（最深层循环内的关键操作）的执行次数决定，该次数的数量级即为整个算法的时间复杂度

大 O 的定义：存在正常数 C 和 n₀，使得 n ≥ n₀ 时 0 ≤ T(n) ≤ C·f(n)，则 T(n) = O(f(n))。

例：T(n) = 3n² + 100n + 5 → O(n²)；T(n) = 2ⁿ + n¹⁰⁰ → O(2ⁿ)。

⚠️ 校订/边界：不存在“外层变化非线性就只能用定义法”的通用定理。例如 i *= 2 可直接由 2ᵗ 与 n 的不等式求出 t = Θ(log n)；看不出时，才回到“数基本操作频度 → 列和式/不等式/递推”。

★ 考过 2011、2012、2013、2014、2017、2019、2022、2025

回源 · PDF 第 17 页 · b_17_5

最好、最坏、平均时间复杂度怎么区分？¶

以"在 A[0…n−1] 中逆序查找 k"为例：

i = n - 1;
while (i >= 0 && (A[i] != k))
    i--;
return i;

最好：A[n−1] 就等于 k → 语句 3 的频度 f(n) = 0
最坏：k 不存在 → 频度 f(n) = n
平均：所有输入等概率出现时的期望运行时间

⚠️ 通常以最坏时间复杂度作为评价标准，因为它提供了运行时间的确定性上界。

回源 · PDF 第 17 页 · b_17_13

加法规则和乘法规则怎么用？¶

加法规则（顺序执行）：O(f) + O(g) = O(max(f, g)) —— 取高阶项
乘法规则（嵌套）：O(f) · O(g) = O(f·g) —— 相乘

教材例（a、b、c 的复杂度分别是 O(1)、O(n)、O(n²)）： - b 和 c 平级顺序放在 a 内 → O(n²)，用加法规则 - c 嵌在 b 内、b 嵌在 a 内 → O(n³)，用乘法规则

💡 判断口诀：看缩进 —— 并列就取大，嵌套就相乘。

回源 · PDF 第 17 页 · b_17_15

常见时间复杂度的大小顺序？¶

O(1) < O(log₂n) < O(n) < O(n log₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

💡 记忆法："常对线、线对方、方立指、指阶幂" —— 常数、对数、线性、线性对数、平方、立方、指数、阶乘、n 的 n 次方。

回源 · PDF 第 18 页 · b_18_3

空间复杂度只算什么？什么叫原地工作？　★1考¶

程序执行所需空间分三块，⚠️ 但只有一块算进空间复杂度： - 指令、常数、与 n 无关的变量 → 固定开销，不随规模变化，不计 - 输入数据 → ⚠️ 只取决于问题本身、与算法无关，不计 - 辅助空间（递归调用栈、临时数组、指针等）→ ⚠️ 只关注这一部分

例：若创建了若干与输入规模 n 同阶的辅助数组，则 S(n) = O(n)。

⚠️ 原地工作 = 仅使用常量级的额外空间，空间复杂度 O(1)。

★ 考过 2010、2011、2012、2013、2015、2016、2018、2019、2020、2021、2025

回源 · PDF 第 17 页 · b_17_2

【原书试题精选与答案方法】第1章¶

两种数据结构的逻辑结构和存储结构相同，就一定是同一种数据结构吗？（1.1 综合应用题 01）¶

不一定。数据结构还包含定义在其上的运算，不能只看“长得像不像、怎么存”。

二叉树和二叉排序树可以采用相同的树形逻辑结构与链式存储结构。
但二者的用途和运算定义不同：普通二叉树的查找通常要遍历，平均可按 \(O(n)\) 理解；二叉排序树在形态较好时平均查找为 \(O(\log_2 n)\)。
答题时用一句总括：逻辑结构 + 存储结构相同，运算不同，仍可能是不同的数据结构。

⚠️ 不要漏掉第三要素“数据的运算”。

回源 · PDF 第 16 页 · b_16_15；PDF 第 16 页 · b_16_16；PDF 第 16 页 · b_16_17

为什么相同的线性逻辑结构换一种存储方式，插入和删除效率就会不同？（1.1 综合应用题 02）¶

顺序表和链表都表示线性结构，但它们体现逻辑关系的方法不同。

顺序存储靠物理相邻表示逻辑相邻，插入或删除后通常要搬移后续元素，平均为 \(O(n)\)。
链式存储靠指针连接结点；若待操作位置及其前驱已经给出，只需修改有限个指针，核心操作为 \(O(1)\)。

💡 王道本题的对比口径是“顺序表要搬移，链表改指针”。答算法题时最好补上“已定位到操作位置”的前提，避免把链表的查找时间也误写成 \(O(1)\)。

回源 · PDF 第 16 页 · b_16_18；PDF 第 16 页 · b_16_19

乘法更新的循环怎样由执行次数推出对数复杂度？（2011 统考真题）¶

遇到 x = 2*x、i *= c 一类循环，不要按“循环体一行”猜复杂度，应设基本运算执行 \(t\) 次。

本题从 \(x=2\) 出发，第 \(t\) 次后数量级为 \(2^{t+1}\)。
把循环条件改写成关于 \(t\) 的不等式，解得 \(t=\Theta(\log_2 n)\)。
因而时间复杂度为 \(O(\log_2 n)\)。

💡 通法：乘除看对数——写出 \(c^t\) 与 \(n\) 的关系再解 \(t\)。

回源 · PDF 第 22 页 · b_22_1；PDF 第 22 页 · b_22_2

每次只把问题规模减 1 的递归，为什么通常是线性复杂度？（2012 统考真题）¶

阶乘递归 fact(n-1) 每层只产生一次递归调用，规模依次为 \(n,n-1,\dots,1\)。

单层基本工作是常数级。
递归深度为 \(n\)。
可写递推式 \(T(n)=T(n-1)+O(1)\)，展开后为 \(O(n)\)。

⚠️ “递归”不等于“指数”。要看每层分出几个子问题，以及问题规模怎样缩小。

回源 · PDF 第 22 页 · b_22_3；PDF 第 22 页 · b_22_4

外层按 2 倍增长、内层固定执行 n 次时，为什么是 nlogn？（2014 统考真题）¶

外层 k*=2 约执行 \(\log_2 n+1\) 趟；每一趟内层都固定执行 \(n\) 次。

因此基本运算总次数为

\[ n(\log_2 n+1), \]

时间复杂度为 \(O(n\log_2 n)\)。

💡 先分别数“外层趟数”和“每趟内层次数”，再用乘法规则相乘。

回源 · PDF 第 22 页 · b_22_6；PDF 第 22 页 · b_22_7；PDF 第 22 页 · b_22_9

为什么看到平方边界还不能立刻写成根号复杂度？（2017、2019、2025 统考真题）¶

三题都先由平方关系求出外层或循环变量的上界，但还要继续数基本运算的总次数。

2017：sum += ++i，执行到 \(1+2+\cdots+i\approx n\)，即 \(i(i+1)/2\approx n\)，故 \(i=\Theta(\sqrt n)\)。
2019：循环终止边界是 \((x+1)^2>n\)，所以 \(x=\Theta(\sqrt n)\)。
2025：外层满足 \(i^2\le n\)，虽然只有 \(\Theta(\sqrt n)\) 趟，但第 \(i\) 趟内层执行 \(i\) 次，总次数为 \(1+2+\cdots+\lfloor\sqrt n\rfloor=\Theta(n)\)，故答案为 \(O(n)\)。

💡 通法：先把终止条件写成 \(t^2\approx n\) 或 \(t(t+1)/2\approx n\)，再问一句：每一趟究竟做 1 次，还是做随 \(i\) 变化的多次？

回源 · PDF 第 22 页 · b_22_10；PDF 第 22 页 · b_22_11；PDF 第 22 页 · b_22_14；PDF 第 22 页 · b_22_15；PDF 第 23 页 · b_23_3；PDF 第 23 页 · b_23_4

外层翻倍、内层工作量也随外层值翻倍时，为什么总复杂度不是 nlogn？（2022 统考真题）¶

本题外层变量取 \(1,2,4,\dots,2^t\)，但第 \(r\) 趟内层工作量不是固定的 \(n\)，而是当前的 \(2^r\)。

总次数是几何级数：

\[ 1+2+4+\cdots+2^t=2^{t+1}-1=\Theta(n), \]

所以时间复杂度为 \(O(n)\)。

⚠️ 只有“每趟内层都做 \(n\) 次”才是 \(n\log n\)；内层上界跟着外层翻倍时，要把每趟次数真正累加。

回源 · PDF 第 22 页 · b_22_16；PDF 第 22 页 · b_22_17；PDF 第 23 页 · b_23_0；PDF 第 23 页 · b_23_2

三段普通程序怎样规范写出 O(n)、O(√n) 和 O(mn)？（1.2 综合应用题 01）¶

按“找基本语句 → 数频度 → 去低阶与常数”的顺序写：

① i++ 型：基本语句执行 \(n-2\) 次，故 \(T(n)=O(n)\)。
② (y+1)^2<=n 型：设循环 \(t\) 次，则 \(t\) 与 \(y\) 同阶，由 \((t+1)^2\le n\) 得 \(t=O(\sqrt n)\)。
③ 两层独立循环：外层 \(n\) 次、内层 \(m\) 次，总次数 \(mn\)，故 \(T(m,n)=O(mn)\)。

💡 这道题正好覆盖三种最基础模型：线性计数、解终止不等式、独立嵌套相乘。

回源 · PDF 第 23 页 · b_23_7；PDF 第 23 页 · b_23_8；PDF 第 23 页 · b_23_9

【原书归纳总结与思维拓展】第1章¶

循环变量参与条件判断时，复杂度应怎样“反解执行次数”？¶

把执行次数设为 \(t\)，根据每次更新后的变量值，建立它与问题规模 \(n\) 的关系，再解出 \(t=f(n)\)。

i *= 2：\(2^t\le n\Rightarrow t=O(\log n)\)。
y++ 且判断 \((y+1)^2<n\)：\(t^2\) 与 \(n\) 同阶，故 \(t=O(\sqrt n)\)。

💡 不是先背答案，而是先问：执行 \(t\) 次后，循环变量变成什么？

回源 · PDF 第 23 页 · b_23_12；PDF 第 23 页 · b_23_13；PDF 第 23 页 · b_23_16；PDF 第 23 页 · b_23_17

循环主体变量与循环条件无关时，怎样选择“递推”还是“累加”？¶

递归程序：写递推关系式并展开，如 \(T(n)=T(n-1)+1=O(n)\)。
非递归循环：逐层数基本运算，必要时写求和式；多层循环从内向外累计。
顺序执行取高阶项，真正嵌套才相乘；若每趟内层次数不同，就写 \(\sum\)，不要机械相乘。

⚠️ 条件判断、赋值等常数开销一般不改变渐近阶，但不能漏掉递归调用栈对空间复杂度的影响。

回源 · PDF 第 24 页 · b_24_0；PDF 第 24 页 · b_24_1；PDF 第 24 页 · b_24_2

斐波那契的递归写法和迭代写法，时空复杂度为什么差别很大？¶

按教材提示比较两种常用实现：

朴素递归 F(n)=F(n-1)+F(n-2) 会反复计算相同子问题，递归树结点数为指数级，通常记时间 \(O(2^n)\)；递归栈深度为 \(O(n)\)。
自底向上迭代只保存前两项，每一项计算一次，时间 \(O(n)\)、额外空间 \(O(1)\)。

💡 这张卡的目的不是死背两个阶，而是识别：递归树是否重复展开同一子问题。若用记忆化，则可把时间降到 \(O(n)\)，但需 \(O(n)\) 额外空间。

回源 · PDF 第 24 页 · b_24_3；PDF 第 24 页 · b_24_4；PDF 第 24 页 · b_24_5；PDF 第 24 页 · b_24_6；PDF 第 24 页 · b_24_8

【易混点】第1章成对概念对照¶

概念 A	概念 B	一句话切分
数据元素	数据项	基本单位，整体处理 vs 不可分割的最小单位
逻辑结构	存储结构	元素间的关系，与机器无关 vs 在计算机中的表示，依赖语言
算法设计	算法实现	取决于逻辑结构 vs 依赖于存储结构
顺序存储	链式存储	可随机存取、有外部碎片 vs 只能顺序存取、每元素多占指针
索引存储	散列存储	建索引表、检索快但要维护 vs 由关键字直接算地址、可能冲突
有穷性	可行性	有限步内结束 vs 每步都能用基本运算做出来
输入	输出	⚠️ 可以 0 个 vs ⚠️ 至少 1 个
加法规则	乘法规则	并列取高阶 vs 嵌套相乘
最坏复杂度	平均复杂度	确定性上界，通用评价标准 vs 等概率下的期望
空间复杂度	输入占用空间	只算辅助空间 vs 不计入

【必背数字】第1章¶

数字	含义
三要素	逻辑结构、存储结构、数据的运算
四种逻辑结构	集合、线性、树形（一对多）、图状（多对多）
四种存储结构	顺序、链式、索引、散列
五个算法特性	有穷、确定、可行、输入（≥0）、输出（≥1）
四个设计目标	正确性、可读性、健壮性、高效率与低存储
O(1) < log₂n < n < n log₂n < n² < n³ < 2ⁿ < n! < nⁿ	复杂度阶次排序
O(1)	原地工作的空间复杂度

【口诀速记】第1章¶

维度	口诀	解释
复杂度阶次	常对线、线对方、方立指、指阶幂	O(1) < log₂n < n < nlog₂n < n² < n³ < 2ⁿ < n! < nⁿ
两条规则	并列取大，嵌套相乘	加法规则取高阶项；乘法规则两者相乘
三要素分工	设计看逻辑，实现看存储	算法设计取决于逻辑结构，实现依赖存储结构
四种逻辑结构	无关系 / 一对一 / 一对多 / 多对多	集合、线性、树形、图状
算法五特性	输入可以 0 个，输出至少 1 个	五特性里最常考的一对
空间复杂度	只算辅助，不算输入	指令常数、输入数据都不计；原地工作 = O(1)

回源 · PDF 第 13 页 · b_13_2；PDF 第 13 页 · b_13_3；PDF 第 13 页 · b_13_4

【解题路线】第1章：看到复杂度题怎么下手¶

① 找最深层循环里的基本运算，数它执行多少次 —— 这个次数的数量级就是答案
② 看循环变量怎么变：⚠️ 加法递增（i++、i+=k）→ 线性；⚠️ 乘法递增（i*=2、i/=2）→ 对数（用 2^t ≈ n 解循环次数）
③ 多段代码：并列取高阶（加法规则）；嵌套相乘（乘法规则） —— 看缩进判断
④ 递归：写出递推式，或数递归树的层数 × 每层代价
⑤ 问空间：⚠️ 只数辅助空间；递归看栈深 = 递归树高度

⚠️ 三个常卡的点：输入数据占用的空间不计入；"原地工作"= O(1)；问"最坏"要构造最不利输入，问"平均"要假设等概率。

回源 · PDF 第 13 页 · b_13_5；PDF 第 13 页 · b_13_6

第1章 绪论

第1章 绪论¶