数据结构第 1 章：绪论

408 数据结构「绪论」复习：核心知识点、真题题型、通用解法与易错点。

本章依据本站 408 真题 → 数据结构 → 第 1 章绪论，以及 408 模拟选择题 → 数据结构 → 第 1 章绪论 整理。本站本章真题一共整理了 2011、2012、2014、2017、2019、2022、2023 七道，其中前六道都是复杂度，第七道考顺序存储的操作复杂度；模拟题则进一步补充了算法特性、递归空间复杂度、双指针摊还分析、二叉树递归等变式。(Any Docs)

内容按照 408 实际命题方式 组织，而不是机械罗列教材概念。

一、本章在 408 中到底重要在哪里？

从本站现有真题看，本章的命题重心非常鲜明：

考法	真题情况	重要程度
程序时间复杂度	2011、2012、2014、2017、2019、2022	★★★★★
顺序存储操作复杂度	2023	★★★
空间复杂度	真题页暂未单独出现，模拟题多次覆盖	★★★★
算法基本特征	模拟题出现	★★
数据结构基本概念、逻辑结构/存储结构	本页真题暂未直接出现	★★

所以这一章真正要形成的能力不是“背诵大 O 定义”，而是：

看到任意一小段程序，能够迅速找到决定执行次数的变量，再把执行次数转化成关于问题规模的数量级。

很多学生后面学树、图、查找、排序时复杂度总出错，其实根源都在这一章。

二、必须掌握的基础概念

1. 什么叫数据结构？

可以把“数据结构”理解成两件事的组合：

数据之间有什么关系 + 数据在计算机里怎么放。

例如学生信息按照学号排成一个序列：

逻辑上，它们是“一前一后”的线性关系。

至于实际存储，可以连续放：

A B C D E

也可以通过指针连起来：

A → B → C → D → E

因此要区分：

层面	问什么
逻辑结构	数据元素之间是什么关系？
存储结构	这种关系在计算机内存中如何实现？

典型逻辑结构包括集合结构、线性结构、树形结构和图状结构。

最容易混淆的一点是：

逻辑结构相同，不代表存储结构相同。

同一个线性表既可以采用顺序存储，也可以采用链式存储。

三、题型一：算法基本概念判断

这是本章最简单的一类题，考到基本不能丢。

网站模拟题：

王道·卷一 Q01

题意：下面哪一个不是算法的主要特征？

A. 有穷性 B. 可行性 C. 确定性 D. 可读性

答案：D。(Any Docs)

算法通常强调：

有穷性、确定性、可行性、输入和输出。

“可读性”当然是好程序的重要性质，但算法不是因为“不可读”就不是算法。

这里有一个特别容易出的陷阱：

程序可以无限执行，但算法必须有穷。

例如一个操作系统：

while (1) {
    process();
}

程序当然允许一直运行。

但如果若声称它是“求数组最大值的算法”，却永远不结束，那它就不是一个正确的求最大值算法。

四、时间复杂度的真正含义

设某算法的基本操作执行次数为：

T (n)

其中问题规模为：

n

时间复杂度并不是计算“程序运行了多少秒”，而是研究：

n \to \infty

时，执行次数增长得有多快。

例如：

T (n) = 3 n^{2} + 20 n + 100

真正决定增长速度的是：

n^{2}

因此写为：

T (n) = Θ (n^{2})

408 选择题通常写成：

O (n^{2})

虽然严格数学意义上大 O 是上界，但考试中“时间复杂度为 O(...)”一般是在寻找最紧的常见数量级。

五、复杂度比较必须非常熟

常见复杂度从小到大：

O (1) < O (lo g n) < O (n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)

其中最需要建立直觉的是：

lo g n

通常来自“每轮乘一个常数或者除一个常数”。

而：

n

通常来自：

i^{2} \approx n

或：

1 + 2 + \dots + i \approx n

六、题型二：变量每次乘常数——对数复杂度

这是第一章最高频模板之一。

真题：2011 年 408

网站题目可以概括为：

x = 2;

while (x < n / 2)
    x = 2 * x;

问时间复杂度。本站答案为：

O (lo g_{2} n)

(Any Docs)

怎么分析？

不要盯着 while 猜。

应该问：

执行 k 次以后 x 变成多少？

初始：

x = 2

一次以后：

x = 4

两次：

x = 8

因此 k 次后：

x = 2^{k + 1}

循环大约在：

2^{k + 1} \approx \frac{n}{2}

时停止。

两边取对数：

k = Θ (lo g n)

所以：

T (n) = Θ (lo g n)

模拟题：王道·卷三 Q01

题目变为：

i = 2;

while (i < n / 3)
    i = i * 3;

网站答案仍然是：

O (lo g n)

(Any Docs)

为什么底数从 2 变成 3，复杂度没变？

因为：

lo g_{3} n = \frac{lo g _{2} n}{lo g _{2} 3}

而：

\frac{1}{lo g _{2} 3}

只是一个常数。

所以复杂度分析中：

O (lo g_{2} n) = O (lo g_{3} n) = O (lo g n)

模拟题：王道·卷四 Q01

题意：

i = n * n;

while (i != 1)
    i = i / 2;

每一次缩小一半。

执行 k 次以后数量级为：

\frac{n ^{2}}{2 ^{k}}

停止条件大致是：

\frac{n ^{2}}{2 ^{k}} \approx 1

所以：

2^{k} \approx n^{2}

于是：

k \approx 2 lo g_{2} n

因此：

T (n) = Θ (lo g n)

(Any Docs)

一句话模板

凡看到：

i *= c;

或者：

i /= c;

且：

c > 1

第一反应就是：

O (lo g n)

七、题型三：普通递归——看递归深度和每层工作量

2012 年 408 真题

网站题目是递归求阶乘：

int fact(int n) {
    if (n <= 1)
        return 1;

    return n * fact(n - 1);
}

问时间复杂度。

本站答案：

O (n)

(Any Docs)

为什么不是：

O (lo g n)

也不是指数级？

递归调用过程：

fact(n)
fact(n-1)
fact(n-2)
...
fact(1)

一共有大约：

n

层。

可以写递推式：

T (n) = T (n - 1) + O (1)

展开：

T (n) = T (n - 2) + 2 O (1)

继续：

T (n) = T (1) + (n - 1) O (1)

所以：

T (n) = Θ (n)

这道题更重要的隐藏考点：空间复杂度

虽然真题问的是时间复杂度，但必须同时知道：

S (n) = Θ (n)

原因不是总共进行了多少次递归，而是：

某一时刻同时存在多少层栈帧。

递归调用过程中：

fact(n)
 ↓
fact(n-1)
 ↓
fact(n-2)
 ↓
...
 ↓
fact(1)

最深时同时存在约 n 层。

因此递归空间：

O (n)

这个思想会直接用于后面的树和图。

八、题型四：两层循环不能看到两层就写平方

这是 408 极其爱挖的坑。

2014 年真题

网站题目：

count = 0;

for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

本站答案：

O (n lo g n)

(Any Docs)

外层：

1,2,4,8,...

所以执行：

Θ (lo g n)

次。

而每一次外循环中，内层固定执行：

n

次。

因此总次数：

n \times Θ (lo g n)

也就是：

Θ (n lo g n)

什么时候可以直接相乘？

只有类似这种真正“独立”的循环：

for (...) {
    for (...) {
        ...
    }
}

外层每执行一次，内层都执行同一个数量级。

才可以大致：

外层次数 \times 内层次数

但如果内层次数随外层变量变化，就必须求和。

这是本章最重要的原则之一。

九、题型五：累计量达到 n——建立方程

2017 年 408 真题

网站题目：

int func(int n) {
    int i = 0, sum = 0;

    while (sum < n)
        sum += ++i;

    return i;
}

答案：

O (n)

(Any Docs)

第一次循环：

s u m = 1

第二次：

s u m = 1 + 2

第三次：

s u m = 1 + 2 + 3

执行 i 次：

s u m = 1 + 2 + \dots + i

利用等差数列：

s u m = \frac{i ( i + 1 )}{2}

停止时约满足：

\frac{i ( i + 1 )}{2} \approx n

看最高次项：

i^{2} \approx 2 n

所以：

i = Θ (n)

因此：

T (n) = Θ (n)

以后看到这种题怎么办？

例如：

s = 0;

for (i = 1; s < n; i++)
    s += i;

不要去模拟。

直接建立：

1 + 2 + \dots + i \approx n

然后：

i^{2} \approx n

得到：

O (n)

十、题型六：循环变量满足平方条件——直接解不等式

2019 年真题

题目：

x = 0;

while (n >= (x + 1) * (x + 1))
    x = x + 1;

网站答案：

O (n)

(Any Docs)

循环能够继续的条件：

(x + 1)^{2} \leq n

因此：

x + 1 \leq n

变量每次只增加 1，所以循环次数：

Θ (n)

2017 和 2019 本质其实是一道题

2017：

1 + 2 + \dots + i \approx n

推出：

i^{2} \approx n

2019：

i^{2} \approx n

直接出现。

最终都得到：

i \approx n

所以不要把真题记成“两道孤立的题”。

应该记成统一模型：

当循环终止条件最终转化成“循环次数的平方约等于 n”，复杂度就是平方根级。

十一、题型七：内层执行次数随外层变化——必须求和

这是 2022 真题最值得掌握的技巧。

2022 年 408 真题

题目：

int sum = 0;

for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

网站答案：

O (n)

而不是：

O (n lo g n)

(Any Docs)

很多人会说：

外层：

O (lo g n)

内层最大：

O (n)

所以：

O (n lo g n)

这是错误的。

因为不同轮的内层执行次数不同。

i 的取值：

1
2
4
8
...

总次数应该是：

T (n) = 1 + 2 + 4 + 8 + \dots

这是等比数列。

若最后一项数量级为 n，则：

1 + 2 + 4 + \dots + 2^{k} = 2^{k + 1} - 1

因此：

T (n) = Θ (n)

十二、这是复杂度题最重要的升级思想：求和而不是机械相乘

遇到：

for (...) {
    for (...) {
    }
}

应问：

第 k 次外层循环，内层究竟执行几次？

于是总复杂度其实是：

T (n) = k \sum 第 k 轮的工作量

2014 真题对应：

T (n) = n + n + n + \dots + n

一共：

Θ (lo g n)

项，所以：

T (n) = Θ (n lo g n)

而 2022 真题对应：

T (n) = 1 + 2 + 4 + \dots

所以：

T (n) = Θ (n)

两道题摆在一起学，价值非常高。

十三、模拟强化：不是所有双重循环都是平方复杂度

王道·卷一 Q02

网站模拟题大意：

for (i = 1; i <= n; i++) {
    for (j = 2 * i; j <= n; j++) {
        y += i * j;
    }
}

答案：

O (n^{2})

(Any Docs)

注意内层只有：

2 i \leq n

的时候才运行。

也就是：

i \leq \frac{n}{2}

固定 i 时，内层次数约为：

n - 2 i + 1

总次数：

T (n) = i = 1 \sum ⌊ n /2 ⌋ (n - 2 i + 1)

展开后，本质仍然是平方数量级：

T (n) = Θ (n^{2})

这道题训练的是：

内外层相关时，先写出“第 i 轮执行多少次”，再求和。

十四、题型八：双指针——两个循环也可以是线性复杂度

本站里的 竟成·模拟一-01 非常值得做。

题目使用左右指针，大致逻辑为：

int cnt = 0, left = 0;

for (int right = 0; right < n; right++) {
    if (nums[right] == 1)
        cnt++;

    while (left <= right && cnt >= k) {
        if (nums[left] == 1)
            cnt--;

        left++;
    }
}

问时间复杂度。

答案：

O (n)

(Any Docs)

表面上是：

for
    while

但绝对不能直接写：

O (n^{2})

因为 right 从左到右最多移动：

n

次。

而 left 从头到尾也只会向右走，不会回退，所以最多：

n

次。

总移动次数至多数量级：

n + n

因此：

T (n) = O (n)

这就是摊还分析的基本思想。

以后看到：

“双指针都只单调移动、不回退”

第一反应应该是：

O (n)

而不是：

O (n^{2})

这也是后面字符串、链表、数组算法中非常实用的规律。

十五、题型九：空间复杂度——千万不要数总调用次数

网站模拟题在这一点上补得很好。

竟成·模拟二-01：斐波那契

题目比较：

int f1(int n) {
    if (n == 1) return 1;
    if (n == 0) return 0;
    return f1(n - 1) + f1(n - 2);
}

和使用长度约为 n 的数组进行动态规划的 f2。

问两者空间复杂度。

网站答案：

O (n), O (n)

(Any Docs)

最容易犯的错误：

因为递归树的结点数量大约指数增长，就认为空间复杂度是：

O (2^{n})

错。

例如：

                 f(n)
              /        \
          f(n-1)       f(n-2)
          / ...

左右子树不是全部同时存在于调用栈中。

真正决定递归空间的是：

最长的一条递归调用链。

最长链：

f(n)
f(n-1)
f(n-2)
...
f(1)

所以最大深度：

n

空间：

O (n)

虽然它的时间复杂度确实是指数级。

因此一定分清：

时间 \neq = 空间

十六、题型十：二分递归——时间可能是 n，空间却是 log n

竟成·模拟七-01

网站题目：

int fun(int *arr, int m, int n) {
    if (m == n)
        return 1;

    int mid = (m + n) / 2;

    return fun(arr, m, mid)
         + fun(arr, mid + 1, n);
}

问空间复杂度。

答案：

O (lo g n)

(Any Docs)

每层区间长度减半：

n \to \frac{n}{2} \to \frac{n}{4} \to \dots \to 1

若递归深度为 k：

\frac{n}{2 ^{k}} \approx 1

所以：

2^{k} \approx n

得到：

k = Θ (lo g n)

因此空间：

S (n) = Θ (lo g n)

但它的时间复杂度是多少？

这个地方特别适合拓展。

每个区间最终都要处理。

递推式：

T (n) = 2 T (\frac{n}{2}) + O (1)

递归树：

1 个结点
2 个结点
4 个结点
8 个结点
...

总节点数量：

1 + 2 + 4 + \dots + n

所以：

T (n) = Θ (n)

最终：

时间 O (n) ， 空间 O (lo g n)

这是408很喜欢的组合。

十七、模拟强化：树递归的复杂度

本站 王道·卷二 Q01 给出了这样一个函数：

int maxFunc(TreeNode* root) {
    if (root == NULL)
        return 0;

    return max(
        maxFunc(root->left),
        maxFunc(root->right)
    ) + 1;
}

设二叉树有 n 个结点，问时间复杂度。

答案：

O (n)

(Any Docs)

非常多人会想：

“二叉树高度是 log n，所以复杂度是 log n。”

错。

树高只说明最长递归链。

但这个函数为了求高度，需要访问所有结点。

如果左右子树结点数分别为：

n_{L}, n_{R}

则：

T (n) = T (n_{L}) + T (n_{R}) + O (1)

因为：

n_{L} + n_{R} = n - 1

所以每个结点仅处理一次：

T (n) = Θ (n)

这里再次体现：

递归深度决定空间；访问节点总数更常决定时间。

十八、题型十一：顺序存储为什么能 O(1) 随机访问？

2023 年 408 真题

网站题意：

长度为 n 的有序顺序表，下面哪个操作平均时间复杂度可以达到：

O (1)

A. 按指定值查找元素 B. 插入指定值元素 C. 删除第 i 个元素 D. 获取第 i 个元素

答案：D。(Any Docs)

这是第一章和第二章“线性表”的连接题。

为什么第 i 个元素可以直接得到？

顺序表连续存储。

假设首元素地址：

L O C (a_{1})

每个元素占 L 个字节。

那么：

L O C (a_{i}) = L O C (a_{1}) + (i - 1) L

只需要一次乘法和一次加法即可定位。

无论：

i = 2

还是：

i = 1000000

都是固定次数计算。

因此：

T (n) = O (1)

这就是所谓的：

随机访问 Random Access。

十九、为什么另外三个不是 O(1)？

按值查找

因为题目说明“有序”，所以可以折半查找：

O (lo g n)

但仍不是：

O (1)

插入

即使利用二分查找快速找到插入位置，后面的元素仍然可能需要整体后移：

1 3 5 7 9

插入 4

1 3 _ 5 7 9

移动元素平均为线性数量级：

O (n)

所以整个插入仍为：

O (n)

这是408非常容易出的陷阱：

查找插入位置快，不代表插入本身快。

删除第 i 个元素

删除后后续元素需要前移：

平均：

O (n)

二十、一个非常重要的表：顺序表常见复杂度

操作	时间复杂度
已知下标访问元素	O(1)
已知下标修改元素	O(1)
无序表按值查找	O(n)
有序表折半查找	O(log n)
插入	O(n)
删除	O(n)

这个表以后学第二章仍然会反复出现。

二十一、一个容易出错的特殊模拟题：i 每次平方

网站 竟成·模拟五-01：

int sum = 0;

for (int i = 2; i <= n; i *= i)
    for (int j = 1; j <= i; j++)
        sum++;

i 的变化：

也就是：

2, 2^{2}, 2^{4}, 2^{8}, 2^{16}, \dots

外层次数大约只有：

O (lo g lo g n)

但千万不能得出：

O (lo g lo g n)

因为内层每轮执行 i 次。

总执行次数：

2 + 4 + 16 + 256 + \dots

序列增长非常快，总和由最后的大项主导。

网站在给定选项中选择：

O (n)

(Any Docs)

不过这里补充一个严格性问题：

由于 i 只能取：

2, 4, 16, 256, \dots

对于任意给定 n，最后一个 i 并不一定与 n 同阶，因此把它在所有 n 上直接写成严格的：

Θ (n)

并不严谨。

但：

O (n)

确实成立，而且是题目提供选项中的最小标准上界，所以按这道模拟选择题应选 B。

这个区别值得知道，不需要为408常规题过度纠结。

二十二、复杂度题真正通用的“六步法”

以后拿到陌生程序，不要靠感觉。

第一步：找基本操作

通常是最内层语句，例如：

count++;

真正的问题变成：

它总共执行多少次？

第二步：找控制变量

观察：

i++
i += k
i *= 2
i /= 2
sum += i
i *= i

这决定循环次数模型。

第三步：写第 k 次后的变量

例如：

i *= 2

得到：

i_{k} = 2^{k}

例如：

i++

得到：

i_{k} \approx k

第四步：利用终止条件列方程

例如：

2^{k} \approx n

于是：

k \approx lo g n

或者：

k^{2} \approx n

于是：

k \approx n

第五步：多层循环判断“乘还是求和”

若每轮固定执行 n 次：

n + n + \dots + n

可以写乘法。

若每轮不同：

1 + 2 + 4 + \dots

必须求和。

第六步：删掉常数和低阶项

例如：

3 n^{2} + 100 n + 7

最终：

O (n^{2})

这套方法几乎可以吃掉本章全部真题。

二十三、观察到程序时可以直接做的“模式匹配”

程序特征	第一反应
`i++` 跑到 n	O(n)
`i += c` 跑到 n	O(n)
`i *= c`	O(log n)
`i /= c`	O(log n)
两层均跑 n 次	O(n²)
一层 n，一层 log n	O(n log n)
累加 1+2+…+k 达到 n	O(√n)
判断 k² ≤ n	O(√n)
1+2+4+…+n	O(n)
两个单调双指针	通常 O(n)
递归参数每次减 1	栈深通常 O(n)
递归规模每次减半	栈深通常 O(log n)

这一张表建议真正记住。

二十四、最容易错的五种思维

错误一：看到两层循环就写平方

2022 真题直接反例：

1 + 2 + 4 + \dots + n = O (n)

不是：

O (n lo g n)

错误二：只看循环次数，不看循环体成本

外层：

O (lo g n)

并不说明整个程序：

O (lo g n)

因为里面可能还有大量工作。

错误三：递归调用很多，所以空间也很多

错误。

空间看的是：

同一时刻存在的最大递归深度。

例如斐波那契递归：

时间很大，但空间只是：

O (n)

错误四：二叉树高度 log n，所以遍历也是 log n

错误。

平衡树高度可以是：

O (lo g n)

但如果需要访问全部 n 个结点：

O (n)

错误五：能二分找到位置，所以插入也是 log n

错误。

顺序表：

查找位置：

O (lo g n)

移动元素：

O (n)

总复杂度由大项决定：

O (n)

二十五、补充一道很像未来 408 的综合变式

考虑：

int count = 0;

for (int i = 1; i <= n; i *= 2) {
    for (int j = 0; j < i; j++)
        count++;

    for (int k = 0; k < n; k++)
        count++;
}

问复杂度。

很多人可能看到第一部分：

1 + 2 + 4 + \dots + n = O (n)

于是答：

O (n)

但是别忘了第二个循环。

外层执行：

O (lo g n)

次。

而第二个内循环每次执行：

n

次。

因此这部分：

O (n lo g n)

总复杂度：

O (n) + O (n lo g n)

保留高阶项：

O (n lo g n)

这类题就是把 2014 和 2022 两道真题揉在一起，非常符合408变式风格。

二十六、再预测一道空间复杂度题

int fun(int n) {
    if (n <= 1)
        return 1;

    return fun(n / 2) + fun(n / 2);
}

问时间和空间复杂度。

很多人会认为两个都是：

O (lo g n)

实际上不是。

递归树高度：

O (lo g n)

所以空间复杂度：

O (lo g n)

但每层节点数：

1, 2, 4, 8, \dots

最后一层约 n 个节点。

总节点数：

1 + 2 + 4 + \dots + n

因此：

O (n)

所以答案：

T (n) = O (n), S (n) = O (lo g n)

这正是本站模拟题中“二叉树递归 + 二分递归空间”两种思想的融合。

二十七、本章最后应该形成什么能力？

按照本站的真题分布，第 1 章不值得花大量时间背长篇概念，而应该形成下面这条完整思考链：

程序
 ↓
基本操作
 ↓
循环变量如何变化
 ↓
执行 k 次后变量是多少
 ↓
利用终止条件求 k
 ↓
若有嵌套，判断相乘还是求和
 ↓
若有递归，分别考虑：
    总调用量 → 时间
    最大递归深度 → 空间
 ↓
得到渐近复杂度

尤其建议把六道真题组成三组来记：

真题组合	本质
2011 + 模拟乘 3 / 除 2	倍增倍减 → 对数
2017 + 2019	平方达到 n → 平方根
2014 + 2022	嵌套循环：机械相乘 vs 按轮求和

而 2023 真题 则单独记住顺序存储的核心优势：

连续存储 \Rightarrow 按下标随机访问 O (1)

综合本站的真题与模拟题，第 1 章最值得投入时间的排序就是：复杂度求和模型 > 递归时间/空间区分 > 倍增倍减循环 > 顺序表随机访问 > 算法概念判断 > 其余绪论概念。 网站本身也明确建议研究408时采用“知识点 → 真题 → 命题方式总结 → 模拟题补充”的路径，而本章的真题分布恰好非常适合这样学。(Any Docs)

本站：408 真题·数据结构第 1 章绪论本站：408 模拟选择题·数据结构第 1 章绪论

数据结构第 1 章：绪论

On this page