一、单项选择题
更直观的方法：计算基本运算 $i = i*2$ 的执行次数（每执行一次， $i$ 乘以 2），其中判断条件可以理解为 $2^{t} = n$ ，即 $t = \log_2n$ ，则 $T(n) = O(\log_2n)$ 。
07. C
基本运算为 $i++$ ，设执行次数为 $t$ ，有 $t \cdot t \cdot t \leqslant n$ ，即 $t^3 \leqslant n$ 。因此有 $t \leqslant \sqrt[3]{n}$ ，则 $T(n) = O(\sqrt[3]{n})$ 。
08. D
这是冒泡排序的算法代码，考查最坏情况下的元素交换次数（若觉得理解起来有困难，则可在学完第8章后再回顾）。当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。此时，
$$
T (n) = \sum_ {i = 2} ^ {n - 1} \sum_ {j = 1} ^ {i - 1} 1 = \sum_ {i = 2} ^ {n - 1} i - 1 = (n - 2) (n - 1) / 2 = O \left(n ^ {2}\right)
$$
所以在最坏情况下该语句的频度是 $O(n^{2})$ 。
09. A
当程序段中有条件判断语句时，取分支路径上的最大时间复杂度。
10. A
$\mathrm{m} + +$ 语句的执行次数为
$$
\sum_ {i = 1} ^ {n} \sum_ {j = 1} ^ {2 i} 1 = \sum_ {i = 1} ^ {n} 2 i = 2 \sum_ {i = 1} ^ {n} i = n (n + 1)
$$
11. C
本题求的是递归调用的时间复杂度，递归调用可视为多重循环，每次递归执行的基本语句是if $(n == 1)$ return 1; ，因此可以认为单层循环的执行次数为1，设递归次数为 $t$ ， $2^{t}\leqslant n$ ，即 $t\leqslant \log_2n$ ，共执行了 $\log_2n$ 次递归调用，总执行次数 $T = \log_2n\times 1$ ，所以时间复杂度为 $O(\log_2n)$ 。
<!-- page: 22 -->
2027年数据结构考研复习指导
| 循环变量 i | 单层循环语句 | 单层循环执行次数 |
| --- | --- | --- |
| n | if (n==1) return 1; | 1 |
| n/2 | if (n==1) return 1; | 1 |
| n/4 | if (n==1) return 1; | 1 |
| ... | ... | ... |
| 1 | if (n==1) return 1; | 1 |
12. A
基本运算（执行频率最高的语句）为 $x = 2*x$，每执行一次，$x$ 乘以 2，设执行次数为 $t$，则有 $2^{t+1} < n/2$，所以 $t < \log_2(n/2) - 1 = \log_2 n - 2$，得 $T(n) = O(\log_2 n)$。
13. B
本题求的是递归调用的时间复杂度，递归调用可视为多重循环，每次递归执行的基本语句是 if (n<=1) return 1;，因此，可以认为单层循环的执行次数为 1，共执行了 $n$ 次递归调用，总执行次数 $T = 1 + 1 + \cdots + 1 = n$，所以时间复杂度为 $O(n)$。
| 循环变量 i | 单层循环语句 | 单层循环执行次数 |
| --- | --- | --- |
| n | if (n<=1) return 1; | 1 |
| n-1 | if (n<=1) return 1; | 1 |
| n-2 | if (n<=1) return 1; | 1 |
| ... | ... | ... |
| 1 | if (n<=1) return 1; | 1 |
14. C
对于单层循环如 for (j=1; j<=n; j++) count++;，可以直接数出执行次数为 n，因此可将多层循环转换成多个并列的单层循环，且列出每个单层循环如下（假设 t 为循环变量的幂次）：
| 循环变量 k | 单层循环语句 | 单层循环执行次数 |
| --- | --- | --- |
| 1 | for (j=1; j<=n; j++) | n |
| 2^{1} | for (j=1; j<=n; j++) | n |
| 2^{2} | for (j=1; j<=n; j++) | n |
| ... | ... | ... |
| 2^{t} | for (j=1; j<=n; j++) | n |
进入外层循环的条件是 $k \leqslant n$，当循环结束时，循环变量的幂次 $t$ 满足 $2^t \leqslant n < 2^{t+1}$，即 $t \leqslant \log_2 n$。所以总执行次数 $T = n(t + 1) = n(\log_2 n + 1)$，时间复杂度为 $O(n \log_2 n)$。
15. B
基本运算为 sum+=++i，等价于“++i；sum=sum+i”，每执行一次，i 都自增 1。当 i=1 时，sum=0+1；当 i=2 时，sum=0+1+2；当 i=3 时，sum=0+1+2+3，以此类推，得出 sum=0+1+2+3+…+i=(1+i)×i/2，可知循环次数 t 满足(1+t)·t/2<n，故时间复杂度为 O(n^1/2)。
注意
统考真题中常将 $\log_2$ 书写为 $\log$，此时默认底数为 2。
16. B
假设第 $k$ 次循环终止，则第 $k$ 次执行时，$(x + 1)^2 > n$，$x$ 的初始值为 0，第 $k$ 次判断时，$x = k - 1$，即 $k^2 > n$，$k > \sqrt{n}$，因此该程序段的时间复杂度为 $O(n^{1/2})$。
17. B
对于单层循环如 for (j=0; j<=i; j++) sum++;，可以直接数出执行次数为 i，因此可将多
<!-- page: 23 -->
第1章 绪论
11
层循环转换成多个并列的单层循环，且列出每个单层循环如下（假设 $t$ 为循环变量的幂次）：
| 循环变量 i | 单层循环语句 | 单层循环执行次数 |
| --- | --- | --- |
| 1 | for (j=0; j<1; j++) | 1 |
| 2^{1} | for (j=0; j<2; j++) | 2 |
| 2^{2} | for (j=0; j<2^{2}; j++) | 4 |
| ... | ... | ... |
| 2^{t} | for (j=0; j<2^{t}; j++) | 2^{t} |
进入外层循环的条件是 $i < n$，当循环结束时，循环变量的幂次 $t$ 满足 $2^t < n \leqslant 2^{t+1}$。总执行次数 $T = 1 + 2^1 + 2^2 + \dots + 2^t = 2^{t+1} - 1$，即 $n-1 \leqslant T$ 且 $T < 2n-1$，所以时间复杂度为 $O(n)$。
## 18. B
对于单层循环 for $(j = 1; j <= i; j++)$ count++;，其每趟的执行次数为 $i$（$j$ 从 1 到 $i$）。外层循环的条件为 $i^2 \leqslant n$，即 $i \leqslant \sqrt{n}$。因此，可将多层循环转换为多个并列的单层循环，列出每个单层循环如下。总执行次数 $T(n) = 1 + 2 + \dots + \left\lfloor \sqrt{n} \right\rfloor = n / 2 + \left\lfloor \sqrt{n} \right\rfloor / 2$，时间复杂度为 $O(n)$。
| 循环变量 i | 单层循环语句 | 单层循环执行次数 |
| --- | --- | --- |
| 1 | for (j=1; j<=i; j++) | 1 |
| 2 | for (j=1; j<=i; j++) | 2 |
| ... | for (j=1; j<=i; j++) | ... |
| $\left\lfloor \sqrt{n} \right\rfloor$ | for (j=1; j<=i; j++) | $\left\lfloor \sqrt{n} \right\rfloor$ |
## 二、综合应用题
### 01.【解答】
① 基本语句 $k = k + 10 * i$ 共执行了 $n - 2$ 次，故 $T(n) = O(n)$。
② 设循环体共执行 $t$ 次，每循环一次，循环变量 $y$ 加 1，最终 $t = y$。故 $t^2 \leqslant n$，得 $T(n) = O(n^{1/2})$。
③ 内循环执行 $m$ 次，外循环执行 $n$ 次，根据乘法原理，共执行了 $mn$ 次，故 $T(m, n) = O(mn)$。
## 归纳总结
本章的核心在于分析程序的时间复杂度。读者不仅要能快速判断算法的渐近复杂度，更要掌握规范、严谨的推导过程——许多人在解题时虽能“一眼看出”答案，却难以清晰地阐述其分析逻辑。为此，编者综合众多资料，将此类问题归纳为以下两种典型情形，以供参考。
### 1. 循环主体中的变量参与循环条件的判断
对于采用循环递推实现的算法，应先建立基本运算的执行次数 $x$ 与问题规模 $n$ 之间的关系式，解得 $x = f(n)$。若 $f(n)$ 的最高次幂为 $k$，则时间复杂度为 $O(n^k)$。例如，
1. int i=1;
while (i<=n)
i=i*2;
2. int y=5;
while ((y+1)*(y+1)<n)
y=y+1;
在例 1 中，设基本运算 $i = i*2$ 的执行次数为 $t$，则 $2^t \leqslant n$，解得 $t \leqslant \log_2 n$，故 $T(n) = O(\log_2 n)$。
在例 2 中，设基本运算 $y = y + 1$ 的执行次数为 $t$，则 $t = y - 5$，且 $(t + 5 + 1)(t + 5 + 1) < n$，解得 $t < \sqrt{n} - 6$，即 $T(n) = O(\sqrt{n})$。
<!-- page: 24 -->
2027年数据结构考研复习指导
## 2. 揭环主体中的变量与循环条件无关
此类问题可采用数学归纳法或直接累计循环执行次数。分析多层循环时，应从内向外逐层计算，忽略单步语句、条件判断语句，仅关注主体语句的执行次数。此类问题又可分以下两种。
- 递归程序通常通过建立递推关系式求解。时间复杂度的分析如下：
$$
T(n) = 1 + T(n - 1) = 1 + 1 + T(n - 2) = \dots = n - 1 + T(1)
$$
即 $T(n) = O(n)$。
- 非递归程序的分析较为简单，可直接累加次数。本节前面已给出相关习题。
## 思维拓展
求解斐波那契数列
$$
F(n) = \begin{cases}
0, & n = 0 \\
1, & n = 1 \\
F(n - 1) + F(n - 2), & n > 1
\end{cases}
$$
有两种常用的算法：递归算法和非递归算法。试分别分析两种算法的时间复杂度。
### 提示
请结合归纳总结中的两种方法进行解答。
---
购买王道书，就上
**王道官方考研书店**
wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 25 --> # 第2章 # 线性表 ## 【考纲内容】 （一）线性表的基本概念 （二）线性表的实现 顺序存储：链式存储 （三）线性表的应用 ## 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 【复习提示】
线性表是算法题命题的重点。应牢固掌握其在两种存储结构（顺序存储与链式存储）下的各种基本操作，并在平时的学习中注重动手能力的培养。另需提醒的是，算法最重要的是思想！考场时间紧迫，在试卷上并不要求代码具备实际可执行性，应着重清晰地表达出算法的核心思想与关键步骤，而不必过于拘泥于语法、边界等细节。此外，即使采用暴力法，通常也能获得大部分分数，因此在时间紧张时建议直接采用。注意，算法题只能使用 $C/C++$ 语言实现。
## 2.1 线性表的定义和基本操作
### 2.1.1 线性表的定义
线性表是由 $n$ （$n \geqslant 0$）个相同数据类型的元素组成的有限序列。其中 $n$ 为表长；当 $n = 0$ 时，线性表为空表。若用 $L$ 表示一个线性表，则其一般形式为
$$
L = \left(a _ {1}, a _ {2}, \dots , a _ {t}, a _ {t + 1}, \dots , a _ {n}\right)
$$
式中，$a_{1}$ 是唯一的“第一个”数据元素，也称表头元素；$a_{n}$ 是唯一的“最后一个”数据元素，也称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继（“直接前驱”与“前驱”、“直接后继”与“后继”通常被视为同义词）。以上即为线性表的逻辑特性，这种一对一的线性逻辑关系正是线性表名称的由来。
由此，可总结出线性表的特点如下：
- 表中元素的个数有限。
<!-- page: 26 -->
2027年数据结构考研复习指导
- 表中元素具有逻辑上的顺序性，即存在明确的先后次序。
- 表中元素均为数据元素，每个元素在线性表中被视为一个不可分割的单位。
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
- 表中元素具有抽象性，即仅讨论元素之间的逻辑关系，而不考虑其究竟表示什么内容。
## 注意
线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是两种存储结构，二者属于不同层面的概念，因此不要将其混淆。
## 2.1.2 线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作集合，其他较复杂的功能通常可通过调用这些基本操作来实现。线性表的主要操作如下。
- InitList(&L)：初始化表。构造一个空的线性表。
- Length(L)：求表长。返回线性表 L 的长度，即其中数据元素的个数。
- LocateElem(L,e)：按值查找操作。在表 L 中查找值为 e 的元素，并返回其位置。
- GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素值。
- ListInsert(&L,i,e)：插入操作。在表L的第i个位置插入指定元素e。
- ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回被删元素的值。
- PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。
- DestroyList(&L)：销毁操作。销毁线性表，并释放其占用的内存空间。
## 注意
① 基本操作的具体实现取决于所用的存储结构，存储结构不同，算法的实现方式也不同。② 符号&表示 C++语言中的引用调用；在 C 语言中，可通过指针实现相同效果。
## 2.1.3 本节试题精选
### 单项选择题
01. 线性表是具有 $n$ 个（ ）的有限序列。
A. 数据表
B. 字符
C. 数据元素
D. 数据项
02. 下列几种描述中，（ ）是一个线性表。
A. 由 $n$ 个实数组成的集合
B. 由100个字符组成的序列
C. 所有整数组成的序列
D. 邻接表
03. 在线性表中，除开始元素外，每个元素（）。
A. 只有唯一的前驱元素
B. 只有唯一的后继元素
C. 有多个前驱元素
D. 有多个后继元素
04. 若非空线性表中的元素既没有直接前驱，又没有直接后继，则该表中有（ ）个元素。
A. 1
B. 2
C. 3
D. $n$
## 2.1.4 答案与解析
### 单项选择题
01. C
线性表是由具有相同数据类型的有限数据元素组成的，数据元素是由数据项组成的。
<!-- page: 27 -->
第2章 线性表
15
02. B
线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误；选项A集合中的元素没有前后驱关系，错误；选项D属于一种存储结构，本题要求选出的是一个具体的线性表，不要将二者混为一谈。只有选项B符合线性表定义的要求。
03. A
线性表中，除最后一个（或第一个）元素外，每个元素都只有一个后继（或前驱）元素。
04. A
线性表中的第一个元素没有直接前驱，最后一个元素没有直接后继；当线性表中仅有一个元素时，该元素既没有直接前驱，又没有直接后继。
## 2.2 线性表的顺序表示
### 2.2.1 顺序表的定义
**特别指导** ▶（算法题）顺序表的应用（2010、2011、2018、2020、2025）
线性表的顺序存储也称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置，第 $i$ 个元素的存储位置之后紧接着存放的是第 $i + 1$ 个元素，称 $i$ 为元素 $a_{i}$ 在顺序表中的位序。因此，顺序表的特点是：表中元素的逻辑顺序与其物理存储顺序完全一致。
设顺序表 $L$ 的起始存储地址为 LOC(A)，每个数据元素占用的存储空间大小为 sizeof(ElemType)，则顺序表的存储结构如图2.1所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.1 线性表的顺序存储结构 由于任意数据元素的存储地址与顺序表起始地址之间的偏移量与其位序呈线性关系，因此可在 $O(1)$ 时间内直接访问表中任意位置的元素，这种特性使得线性表的顺序存储结构属于随机存取。在高级程序设计语言中，通常使用数组来实现顺序表。 ### 注意 线性表中元素的位序从1开始，而数组中元素的下标从0开始，注意二者之间的转换。 假定线性表的元素类型为ElemType，则静态分配的顺序表存储结构描述为一维数组既可以静态分配，也可以动态分配。静态分配时，数组的大小和存储空间在编译时已经固定，一旦空间占满，再插入新元素将导致溢出，进而可能引发程序异常。 动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句申请的。当空间占满时，可以另行开辟一块更大的存储空间，将原表中的所有元素复制到新空间中，从而实现存储容量的扩充，而无须在初始化时为线性表一次性划分全部可能用到的空间。 动态分配的顺序表存储结构描述为 C 的初始动态分配语句为 C++的初始动态分配语句为 **注意** 动态分配并不是链式存储，它同样属于顺序存储结构。其物理结构没有变化，依然支持随机存取，只是存储空间的大小可以在运行时动态调整。 顺序表的主要优点：① 可进行随机访问，即通过首地址和元素序号可在 $O(1)$ 时间内找到指定的元素；② 存储密度高，每个结点仅存储数据元素，无额外指针开销。顺序表的缺点也很明显：① 插入和删除操作效率较低，需要移动大量元素；② 要求分配连续的存储空间，不够灵活。 ## 2.2.2 顺序表上基本操作的实现 **考虑表格** 顺序表上操作的时间复杂度分析（2023） 本节仅讨论顺序表的初始化、插入、删除和按值查找，其他基本操作的实现都较为简单。 **注意** 在各种操作的实现中（包括严格做老师的教材），通常可以忽略边界条件判断、变量定义、内存分配失败等实现细节，即不要求代码具有实际可执行性，而应重点体现算法的核心思想与逻辑步骤。#define MaxSize 50 //定义线性表的最大长度 typedef struct{ ElemType data[MaxSize]; //顺序表的元素 <!-- page: 28 --> 2027年数据结构考研复习指导 ```txt int length; //顺序表的当前长度 } SqList; //顺序表的类型定义