🏷️ 知识点：复杂度分析

共 25 道相关题目

2026 年第 1 题数据结构选择题

当存储空间有足够的空闲空间时，在保持表内元素顺序相对不变的情况下，下列哪些操作会必然导致产生移动次数（）。 I. 表头插入一个元素II. 表头删除一个元素III. 表尾插入一个元素IV. 表尾删除一个元素

A. I、II B. I、III C. II、IV D. III、IV

[tag_link]

正确答案：A

在顺序存储结构中，元素连续存放以保持逻辑顺序。表头插入元素时，需将所有现有元素后移一位为新元素腾出空间；表头删除元素时，需将所有剩余元素前移一位以填补空位，这两种操作均必然导致元素移动。而表尾插入或删除元素时，仅需在末尾进行操作，不影响其他元素的位置，因此不会产生移动次数。故必然导致移动次数的操作是Ⅰ和Ⅱ。

模拟卷年第 1 题数据结构选择题

设 $n$ 是描述问题规模的正整数，下列程序片段的时间复杂度是（　）。

A. $O (lo g n)$ B. $O (n)$ C. $O (n lo g n)$ D. $O (n)$

复杂度分析

[tag_link]

正确答案：D

程序片段中，变量 y 从 0 开始，每次循环迭代 y 增加 1。循环条件为 $n \geq (y + 1)^{2}$ ，即 $(y + 1)^{2} \leq n$ 时循环继续。因此，循环执行的次数取决于满足该条件的最大整数 y。设循环迭代了 k 次，则 k 满足 $k^{2} \leq n$ 且 $(k + 1)^{2} > n$ ，这意味着 k 是 $⌊ n ⌋$ 。循环迭代次数与 $n$ 成正比，故时间复杂度为 $O (n)$ 。其他选项中， $O (lo g n)$ 、 $O (n)$ 和 $O (n lo g n)$ 均与迭代次数不符。

模拟卷年第 1 题数据结构选择题

设 $n$ 是描述问题规模的正整数，下面程序片段的时间复杂度是（）。

A. $O (lo g n)$ B. $O (n)$ C. $O (n)$ D. $O (n^{3})$

复杂度分析

[tag_link]

正确答案：A

程序片段中，变量 i 初始化为 2。循环条件为 i < n/3，每次循环体执行 i = i * 3，使得 i 的值以指数速度增长。设循环执行次数为 k。在执行 k 次后，i 的值变为 2 × 3^k。循环终止时满足 2 × 3^k ≥ n/3，由此可得 k ≥ log₃(n/6)。由于对数函数的特性，k 与 log n 成正比。每次循环体执行时间为常数，因此整体时间复杂度取决于循环次数，为 O(log n)。选项 A 正确。

模拟卷年第 1 题数据结构选择题

设 $n$ 是描述问题规模的正整数，下列程序片段的时间复杂度是（）。

A. $O (lo g n)$ B. $O (n)$ C. $O (n)$ D. $O (n^{2})$

复杂度分析

[tag_link]

正确答案：A

程序首先将变量 $i$ 初始化为 $n$ 的平方，即 $i = n^{2}$ 。

然后进入 while 循环，循环条件为 $i \neq = 1$ ，每次迭代将 $i$ 除以 $2$ 。循环的迭代次数取决于 $i$ 从 $n^{2}$ 减少到 $1$ 所需除以 $2$ 的次数。
设迭代次数为

$k$ ，经过 $k$ 次迭代后， $i$ 的值变为 $n^{2} / 2^{k}$ 。

当循环终止时， $i = 1$ ，因此有 $n^{2} / 2^{k} = 1$ ，即 $n^{2} = 2^{k}$ 。取对数可得 $k = lo g_{2} (n^{2}) = 2 lo g_{2} n$ 。
在时间复杂度分析中，常数因子可以忽略，因此迭代次数

$k$ 的数量级为 $O (lo g n)$ 。

所以，该程序片段的时间复杂度是 $O (lo g n)$ 。对比选项，A 正确。

2011 年第 1 题数据结构选择题

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

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

复杂度分析

A. $O(\log n)$

B. $O(n)$

C. $O(n\log_2 n)$

D. $O(n^2)$

[tag_link]

正确答案：A

在程序中，执行频率最高的语句为x = x * 2，设该语句总共执行了 T(n) 次，则2T(n)+1≤n/2，故T(n)=log2(n/2)−1=log2n−2，得T(n)=O(log2n)。

2012 年第 1 题数据结构选择题

求整数n(n≥0)阶乘的算法如下，其时间复杂度是（）。

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

复杂度分析

A. $O(\log_2 n)$

B. $O(n)$

C. $O(n\log_2 n)$

D. $O(n^2)$

[tag_link]

正确答案：B

本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是≤1，每调用一次 fact()，传入该层 fact() 的参数值减 1。采用递归式来表示时间复杂度有Tn={O(1),n≤1T(n−1)+1,n>1则T(n)=T(n−1)+1=T(n−2)+2=⋯=T(1)+n−1=O(n)，故时间复杂度为O(n)。

2013 年第 1 题数据结构选择题

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）。

复杂度分析

A.O(n)

B.O(m×n)

C.O(min(m,n))

D.O(max(m,n))

[tag_link] 正确答案：D两个升序链表合并，两两比较表中元素，每比较一次确定一个元素的链接位置（取较小元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为O(m+n)=O(max(m,n))。

2014 年第 1 题数据结构选择题

下列程序段的时间复杂度是()。

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

A.O(log₂n)

B.O(n)

C.O(nlog₂n)

D.O(n²)

[tag_link]

正确答案：C

内层循环条件 j ≤ n 与外层循环的变量无关，每次循环 j 自增 1, 每次内层循环都执行 n 次。外层循环条件为 k ≤ n , 增量定义为 k *= 2, 可知循环次数为 2 k ≤ n , 即 k ≤ l o g 2 ( n ) 。所以内层循环的时间复杂度是 O ( n ) , 外层循环的时间复杂度是 O ( l o g 2 n ) 。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度 T ( n ) = T 1 ( n ) T 2 ( n ) = O ( n ) O ( l o g 2 ( n )) = O ( n l o g 2 n ) , 选 C。

2017 年第 1 题数据结构选择题

下列函数的时间复杂度是（）。

int func(int n) {
    int i = 0, sum = 0;
    while(sum < n)
        sum += ++i;
    return i;
}

复杂度分析

A. (O(n)) B. (O(\sqrt{n})) C. (O(\log_2 n)) D. (O(n\log_2 n))

[tag_link]

正确答案：B

sum += ++i;相当于++i; sum = sum + i;进行到第 k 趟循环，sum = (1+k)*k/2。显然需要进行O(n1/2)趟循环，因此这也是该函数的时间复杂度。

2019 年第 1 题数据结构选择题

设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（）。

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

复杂度分析

A. (O(n)) B. (O(\sqrt{n})) C. (O(n\log_2 n)) D. (O(\log_2 n))

[tag_link]

正确答案：B

假设第 k 次循环终止，则第 k 次执行时，(x+1)2>n，x 的初始值为 0，第 k 次判断时，x=k-1，即k2>n，k>n1/2,，因此该程序段的时间复杂度为O(n1/2)。

2022 年第 1 题数据结构选择题

下列程序段的时间复杂度是()。

|nt sum =0;for(Int |=1;|<n;| *=2)

for ( |nt j= 0; j<|;j ++)

sum ++ ;

A.O(log₂n)

B.O(n)

C.O(nlog₂n)

D.O(n²)

[tag_link]

正确答案：B

当外层循环的变量 i 取不同值时，内层循环就执行多少次，因此总循环次数为的所有取值之和。假设外层循环共执行 k 次，当 i = 1 , 2 , 4 , 8 , ⋯ , 2 k − 1 ( 2 k − 1 < n ≤ 2 k ) 时，内层循环执行 i 次，因此总循环次数 T = 1 + 2 + 4 + 8 + ⋯ + 2 k − 1 = 2 k − 1 即 n < T < 2 n ，时间复杂度为 O ( n ) 。

2025 年第 1 题数据结构选择题

以下 C 代码的时间复杂度是（）。

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

复杂度分析

A. O(log2N) B. O(N) C. O(Nlog2N) D. O(N^2)

[tag_link]

正确答案：B

外层循环的条件是i2<n，因此 i 的最大值为n。内层循环的的次数同样与 i 相同。所以总的循环次数为n n =n，时间复杂度为O(n)。

2026 年第 6 题数据结构选择题

有向图 G=(V,E) 采用邻接表存储，求某点入度的时间复杂度为？

A. O(|V|) B. O(|E|) C. O(|V|)·|E|) D. O(|V|+|E|)

[tag_link]

正确答案：D

【解析】 在邻接表存储中，求某点的入度需要检查所有顶点的出边链表，统计指向该点的边数。这需要访问所有∣V∣个顶点以及所有∣E∣条边，因此时间复杂度为O(∣V∣+∣E∣)。由于O(∣V∣+∣E∣)与O(max(∣V∣,∣E∣))等价，故选项 D 正确。其他选项均不能完整描述该时间复杂度。

2016 年第 7 题数据结构选择题

若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）

复杂度分析邻接表拓扑排序

A. (O(n)) B. (O(n+e)) C. (O(n^2)) D. (O(n\log_2 n))

[tag_link]

正确答案：B

用邻接表实现 Kahn 拓扑排序时，初始化入度并让每个顶点至多入队、出队一次，共 O(n)；删除某顶点的出边时，每条弧只沿邻接表扫描一次，共 O(e)。因此总时间复杂度为 O(n+e)，选 B。若改用邻接矩阵，每次查找出边要扫描一整行，通常为 O(n²)。

模拟卷年第 8 题数据结构选择题

假设有 $n$ 个顶点 $e$ 条边的有向图用邻接表表示，则删除与某个顶点 $v$ 相关的所有边的时间复杂度为（）。

A. O(n) B. O(e) C. O(n+e) D. O(ne)

复杂度分析

[tag_link]

正确答案：C

在有向图的邻接表表示中，每个顶点维护一个链表存储其出边。删除与顶点 $v$ 相关的所有边包括两部分：一是删除顶点 $v$ 的所有出边，二是删除所有指向顶点 $v$ 的入边。删除出边只需清空顶点 $v$ 的邻接链表，时间复杂度为 $O ((v))$ ，其中 $(v) \leq e$ 。删除入边则需要遍历所有顶点的邻接链表，检查每条边是否指向 $v$ ，并在找到时删除。遍历所有链表需访问 $n$ 个顶点和 $e$ 条边，时间复杂度为 $O (n + e)$ 。因此，总时间复杂度为 $O ((v)) + O (n + e) = O (n + e)$ 。

模拟卷年第 11 题数据结构选择题

下列排序方法中，时间性能与待排序记录的初始状态无关的是（）。

A. 插入排序和快速排序

B. 归并排序和快速排序

C. 选择排序和归并排序

D. 插入排序和归并排序

复杂度分析归并排序

[tag_link]

正确答案：C

排序算法的时间性能是否与初始状态相关，取决于其时间复杂度在不同输入情况下的变化。插入排序在最好情况下（已排序）时间复杂度为 O ( n ) ，最坏和平均为 O ( n 2 ) ，因此与初始状态有关；快速排序的平均时间复杂度为 O ( n lo g n ) ，但最坏情况下（如已排序数组且枢轴选择不当时）会退化到 O ( n 2 ) ，也与初始状态有关。归并排序采用分治策略，无论输入数据是否有序，其时间复杂度稳定为 O ( n lo g n ) ，与初始状态无关；选择排序始终通过遍历未排序部分寻找最小（或最大）元素，其最好、最坏和平均时间复杂度均为 O ( n 2 ) ，因此也与初始状态无关。选项 C 中的选择排序和归并排序均满足时间性能与初始状态无关的条件，而其他选项至少包含一种与初始状态相关的算法，故 C 为正确答案。

模拟卷年第 11 题数据结构选择题

设待排序元素序列所有元素的关键字都相等，则下列排序方法中排序速度最慢的是（）。

A. 直接插入排序

B. 冒泡排序

C. 简单选择排序

D. 基数排序

复杂度分析

[tag_link]

正确答案：C

当待排序元素序列中所有关键字都相等时，序列本身已处于有序状态。此时，不同排序算法的性能表现取决于它们在最好情况下的时间复杂度或实际执行步骤。直接插入排序：在最好情况下（序列有序），只需进行 n-1 次比较，且无需移动元素，时间复杂度为 O(n)，速度很快。冒泡排序：通过优化（如设置交换标志），在序列有序时，一趟扫描（n-1 次比较）后即可终止，时间复杂度也为 O(n)，效率较高。简单选择排序：无论序列是否有序，都必须执行 n-1 趟选择操作，每趟需比较剩余元素以确定最小（或最大）值，比较次数恒定为约 n(n-1)/2 次，时间复杂度始终为 O(n²)，无法利用有序性加速，因此在此场景下速度最慢。基数排序：其时间复杂度为 O(d*(n+k))，其中 d 为关键字位数，k 为基数。当所有关键字相等时，分配和收集操作仍需执行，但整体仍保持线性时间复杂度，远优于 O(n²)。综上所述，在关键字全相等的情况下，简单选择排序由于固定的二次时间复杂度，排序速度最慢。

模拟卷年第 41 题数据结构综合题

（13 分）设有 $n$ 个不全为负的整型元素存储在一维数组 A[p] 中，它包含很多连续的子数组，例如数组 A = {1, -2, 3, 10, -4, 7, 2, -5}，请设计一个时间上尽可能高效的算法，求出数组 A 的子数组之和的最大值（例如数组 A 的最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和 18）。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

信号量复杂度分析

[tag_link]

**【答案】** (1) 基本设计思想：采用 Kadane 算法（动态规划思想）。遍历数组，维护两个变量：current_sum 记录以当前元素结尾的子数组的最大和，max_sum 记录全局最大子数组和。对于每个元素，若 current_sum 为负，则将其重置为当前元素值（因为负数会减小后续子数组的和），否则将当前元素加入 current_sum。然后更新 max_sum。遍历完成后，max_sum 即为所求。

(2) C 语言算法描述：

#include 
#include  // 使用 INT_MIN 初始化

int maxSubArray(int A[], int n) {
    int current_sum = 0;       // 当前子数组和
    int max_sum = INT_MIN;     // 最大子数组和，初始化为最小整数
    for (int i = 0; i < n; i++) {
        // 若当前子数组和为负，则从 A[i] 重新开始，否则累加
        if (current_sum < 0) {
            current_sum = A[i];
        } else {
            current_sum += A[i];
        }
        // 更新全局最大值
        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
    }
    return max_sum;
}
`

(3) 时间复杂度：O(n)，其中 n 为数组长度，仅需一次遍历。空间复杂度：O(1)，仅使用常数个辅助变量。

**【解析】** 该算法基于动态规划，核心是确定以每个元素结尾的最大子数组和。设以元素 A[i] 结尾的最大子数组和为 f(i)，则状态转移方程为：f(i) = max(A[i], f(i-1) + A[i])。这是因为如果 f(i-1) 为负，其对 A[i] 无增益，故从 A[i] 重新开始；否则累加。算法中的 current_sum 即 f(i)，max_sum 记录所有 f(i) 的最大值。由于数组不全为负，max_sum 至少为非负，但算法也适用于全负情况。遍历一次即可求得结果，因此时间效率高，且仅需常数空间。

模拟卷 年第 42 题
数据结构
综合题

（12 分）假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：

（1）给出算法的基本设计思想。

（2）写出二叉树采用的存储结构代码。

（3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。

复杂度分析图的遍历

[tag_link]

【答案】

（1）算法的基本设计思想：采用递归的深度优先搜索（DFS）方法。从根结点开始，先序遍历二叉树，在遍历过程中使用一个动态数组（如向量）记录当前访问路径。当访问到目标结点时，当前数组中的结点序列即为根结点到目标结点的路径；如果当前结点不是目标结点，则递归遍历其左子树和右子树。若左右子树均未找到目标结点，则进行回溯，从路径中移除当前结点，并返回上一层继续搜索。这种方法利用回溯确保路径的正确性。

（2）二叉树采用的存储结构代码（C 语言描述）：

typedef struct BiTNode {
    char data;                        // 结点数据，假设为字符型
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

（3）算法描述（C++ 语言，基于上述存储结构）：

#include <vector>
using namespace std;

// 函数功能：查找从根结点到目标结点的路径
// 参数：root 为当前子树根结点，target 为目标结点，path 用于存储路径
// 返回值：bool 类型，找到路径返回 true，否则返回 false
bool findPath(BiTree root, BiTree target, vector<BiTree> &path) {
    if (root == nullptr) return false;            // 空树，直接返回 false
    path.push_back(root);                         // 当前结点加入路径
    if (root == target) return true;              // 找到目标结点，返回 true
    if (findPath(root->lchild, target, path)) return true;  // 递归搜索左子树
    if (findPath(root->rchild, target, path)) return true;  // 递归搜索右子树
    path.pop_back();                              // 左右子树均未找到，回溯，移除当前结点
    return false;
}
// 调用示例：假设 root 为根结点指针，target 为目标结点指针，path 为空的 vector<BiTree> 类型，
// 调用 findPath(root, target, path) 后，若返回 true，则 path 中存储从根到目标的路径结点序列。

【解析】算法的核心思想是递归深度优先搜索，结合回溯记录路径。从根结点开始，先访问当前结点并加入路径，然后判断是否为给定结点：若是则成功；否则递归搜索左子树和右子树。递归调用前将当前结点加入路径，调用后若子树中找到目标，则当前结点保留在路径中（因为它是路径的一部分），否则通过 pop_back() 移除当前结点，实现回溯。这保证了路径从根结点到目标结点的顺序性。存储结构采用二叉链，每个结点包含数据域和左右孩子指针，便于递归遍历。算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需要遍历所有结点；空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈和路径向量占用，路径向量最多存储 h 个结点。该算法简洁有效，适用于二叉链存储的二叉树路径查找问题。

模拟卷 年第 42 题
数据结构
综合题

（13 分）将一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个已排好序数组的一个旋转，求该旋转数组的最小元素。如，数组 {3, 4, 5, 1, 2} 为有序数组 {1, 2, 3, 4, 5} 的一个旋转数组，该数组的最小值为 1。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

复杂度分析

[tag_link]

【答案】

（1）基本设计思想：采用改进的二分查找。由于旋转数组由两个有序子数组构成，且最小元素是第二个子数组的首元素。设置两个指针 low 和 high 分别指向数组首尾，计算中间位置 mid。比较 nums[mid] 与 nums[high]：若 nums[mid] > nums[high]，说明最小值在右半部分，令 low = mid + 1；若 nums[mid] < nums[high]，说明最小值在左半部分（包含 mid），令 high = mid；若相等，无法判断，但可通过 high– 缩小范围（不会丢失最小值）。重复直到 low == high，此时指向最小元素。

（2）算法描述（C++）： int findMin ( vector < int >& nums ) { int low = 0 , high = nums . size () - 1 ; while ( low < high ) { int mid = low + ( high - low ) / 2 ; // 防止溢出 if ( nums [ mid ] > nums [ high ]) { low = mid + 1 ; // 最小值在右半部分 } else if ( nums [ mid ] < nums [ high ]) { high = mid ; // 最小值在左半部分（可能为 mid） } else { high – ; // 相等时无法判断，缩小右边界 } } return nums [ low ]; // low == high，指向最小值 }

（3）时间复杂度：平均 O(log n)，最坏情况（全部相等） O(n)。空间复杂度：O(1)，仅用了常数个变量。【解析】本题是旋转数组找最小值的经典问题。原数组有序，旋转后形成两个有序子数组，且最小值位于第二个子数组开头。直接遍历需要 O(n) 时间，而利用二分思想可提升效率。比较 nums[mid] 与 nums[high] 是关键：若 nums[mid] > nums[high]，说明 mid 属于第一个子数组，最小值必在 mid 右侧；若 nums[mid] < nums[high]，说明 mid 属于第二个子数组，最小值在 mid 左侧（含 mid）；若相等，则无法二分（如数组有重复元素），但通过 high– 可逐步缩小范围，确保不遗漏最小值。算法在大部分情况下达到对数复杂度，仅当大量重复元素时退化为线性，这是处理重复情况下的最优方式之一。

模拟卷 年第 42 题
数据结构
综合题

在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组 [2, 4, 1, 16, 7, 5, 11, 9] 中，数对之差的最大值是 11，是 16 减去 5 的结果。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

复杂度分析

[tag_link]

【答案】

（1）算法的基本设计思想：通过一次遍历数组，维护两个变量： maxLeft 记录当前遍历位置左边的最大值， maxDiff 记录当前找到的最大数对之差。对于每个位置 j （从第二个元素开始），计算 maxLeft - arr[j] 得到当前差值，并更新 maxDiff 。同时，如果 arr[j] 大于 maxLeft ，则更新 maxLeft 为 arr[j] ，以确保后续计算使用正确的左边最大值。这样可以在 O(n) 时间内找到最大数对之差。

（2）C++ 语言描述算法： #include <iostream> #include <climits> // 用于 INT_MIN int maxPairDiff ( int arr [], int n ) { if ( n < 2 ) { // 数组至少需要两个元素，否则返回一个较小值或抛出异常 // 这里根据题目假设 n>=2，简单处理返回 0 return 0 ; } int maxLeft = arr [ 0 ]; // 初始化左边最大值为第一个元素 int maxDiff = INT_MIN ; // 初始化最大差值为最小整数，确保能被更新 for ( int j = 1 ; j < n ; j ++ ) { int diff = maxLeft - arr [ j ]; // 计算当前数对之差 if ( diff > maxDiff ) { maxDiff = diff ; // 更新最大差值 } if ( arr [ j ] > maxLeft ) { maxLeft = arr [ j ]; // 更新左边最大值 } } return maxDiff ; } int main () { int arr [] = { 2 , 4 , 1 , 16 , 7 , 5 , 11 , 9 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int result = maxPairDiff ( arr , n ); std :: cout << "最大数对之差为：" << result << std :: endl ; // 输出 11 return 0 ; }

（3）时间复杂度：算法只需遍历数组一次，因此时间复杂度为 O(n)，其中 n 是数组的长度。空间复杂度为 O(1)，只使用了常数个额外变量。【解析】该问题要求找到所有数对 (a[i], a[j]) （其中 i < j ）的差值 a[i] - a[j] 的最大值。暴力枚举所有对的时间复杂度为 O(n²)，效率较低。优化算法基于以下观察：对于每个 j ，要使 a[i] - a[j] 最大，只需找到 j 左边（即 i < j ）的最大值 maxLeft ，然后计算 maxLeft - a[j] 。因此，通过一次遍历，维护 maxLeft （初始为第一个元素）和 maxDiff （初始为最小整数），对于每个后续元素 arr[j] ，计算当前差值并更新 maxDiff ，同时更新 maxLeft 为 max(maxLeft, arr[j]) 。这样确保了对每个 j 都考虑了左边最大值，从而正确得到全局最大差值。例如，数组 [2, 4, 1, 16, 7, 5, 11, 9] 中，遍历到 j=5 （元素 5）时， maxLeft 为 16，差值 16-5=11 被记录为最大差值。算法只遍历一次，高效且正确。

模拟卷 年第 42 题
数据结构
综合题

（12 分）假设二叉树采用二叉链表存储结构，设计一个算法求其指定的某一层 k （ k > 1 ）的叶子结点个数，要求：

（1）给出算法的基本设计思想。

（2）写出二叉树采用的存储结构代码。

（3）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

复杂度分析链表

[tag_link]

【答案】

（1）算法的基本设计思想：采用递归先序遍历二叉树，遍历时记录当前节点所在层数。若当前层数等于指定层数 k ，则判断该节点是否为叶子结点（左右孩子均为空），若是则计数器加 1；若当前层数小于 k ，则递归遍历其左右子树；若当前层数大于 k ，则停止向下递归。最终累计得到第 k 层的叶子结点个数。

（2）二叉树采用的二叉链表存储结构代码： typedef struct BiTNode { char data ; // 结点数据，假设为字符型 struct BiTNode * lchild , * rchild ; // 左右孩子指针 } BiTNode , * BiTree ;

（3）算法描述（C 语言）： // 函数功能：计算二叉树 T 中第 k 层的叶子结点个数 // 参数：T 为二叉树根结点指针，currentLevel 为当前结点所在层数（根结点为第 1 层），k 为指定层数 // 返回值：第 k 层的叶子结点个数 int countLeafAtLevel ( BiTree T , int currentLevel , int k ) { if ( T == NULL ) { // 空树，返回 0 return 0 ; } if ( currentLevel == k ) { // 到达第 k 层 // 判断是否为叶子结点 if ( T -> lchild == NULL && T -> rchild == NULL ) { return 1 ; } else { return 0 ; } } else if ( currentLevel < k ) { // 当前层小于 k，继续向下递归 return countLeafAtLevel ( T -> lchild , currentLevel + 1 , k ) + countLeafAtLevel ( T -> rchild , currentLevel + 1 , k ); } else { // 当前层大于 k，不再递归 return 0 ; } } // 调用示例：int leafCount = countLeafAtLevel(root, 1, k); 【解析】算法设计思想解析：由于需要统计二叉树中指定层 k 的叶子结点个数，采用深度优先搜索（DFS）策略，通过递归遍历二叉树并在过程中跟踪当前层数。当层数等于 k 时，判断当前结点是否为叶子结点并进行计数；若层数小于 k ，则继续递归遍历左右子树；若层数大于 k ，则提前返回，避免无效访问。这种方法只需遍历一次二叉树，且在层数超过 k 时停止递归，提高了效率。存储结构采用标准的二叉链表，每个结点包含数据域和指向左右子树的指针，便于递归操作。算法实现时，递归终止条件包括：结点为空时返回 0；当前层数等于 k 时，根据叶子结点定义返回 1 或 0；当前层数小于 k 时，递归计算左右子树的叶子结点数之和；当前层数大于 k 时直接返回 0。该算法的时间复杂度为 O ( n ) ，最坏情况下需访问所有结点（当 k 大于等于树高时）；空间复杂度为 O ( h ) ， h 为树的高度，即递归栈的深度。注意题目中 k > 1 ，但算法对 k = 1 同样适用，调用时传入 currentLevel=1 即可。

模拟卷 年第 42 题
数据结构
综合题

（13 分）已知一棵二叉树采用二叉链表存储，结点结构为：

root 指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过 1。例如下图所示的二叉树就是一棵平衡二叉树。

要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

复杂度分析平衡二叉树

[tag_link]

【答案】

（1）基本设计思想：采用递归后序遍历二叉树，在计算每个结点高度的同时判断其左右子树是否平衡。递归函数返回当前子树的高度，若子树不平衡则返回 -1 作为标志。对于每个结点，先递归检查其左右子树，若任一子树返回 -1，则当前子树不平衡；否则计算左右子树高度差，若超过 1 则返回 -1，否则返回当前子树高度（即左右子树最大高度加 1）。最终，若根结点对应的递归返回值不为 -1，则二叉树是平衡的。

（2）算法描述（C 语言）： #include <stdlib.h> // 用于 abs 函数 #include <stdbool.h> // 用于 bool 类型 struct Node { struct Node * lchild ; int data ; struct Node * rchild ; }; // 辅助函数：检查以 root 为根的子树是否平衡，返回高度；若不平衡返回 -1 int checkBalance ( struct Node * root ) { if ( root == NULL ) { return 0 ; // 空树高度为 0，平衡 } // 递归检查左子树 int leftHeight = checkBalance ( root -> lchild ); if ( leftHeight == - 1 ) { return - 1 ; // 左子树不平衡，向上传递 } // 递归检查右子树 int rightHeight = checkBalance ( root -> rchild ); if ( rightHeight == - 1 ) { return - 1 ; // 右子树不平衡，向上传递 } // 检查当前结点左右子树高度差 if ( abs ( leftHeight - rightHeight ) > 1 ) { return - 1 ; // 当前结点不平衡 } // 返回当前子树高度 return ( leftHeight > rightHeight ? leftHeight : rightHeight ) + 1 ; } // 主函数：判断二叉树是否平衡 bool isBalanced ( struct Node * root ) { return checkBalance ( root ) != - 1 ; } 【解析】该算法基于递归实现，核心思想是在计算结点高度时同步判断平衡性，避免重复遍历。checkBalance 函数采用后序遍历顺序：先递归处理左右子树，再处理当前结点。若子树不平衡（返回 -1），则立即向上返回，无需进一步计算；否则比较左右子树高度差，若超过 1 则返回 -1 表示不平衡，否则返回当前子树高度。isBalanced 函数通过调用 checkBalance 检查返回值是否为 -1 来判断整棵树的平衡性。算法中每个结点仅访问一次，时间复杂度为 O(n)，n 为结点数；递归栈空间复杂度为 O(h)，h 为树高。这种设计既高效又简洁，符合题目要求。

模拟卷 年第 42 题
数据结构
综合题

单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是为空的）。试编写算法判断单链表是否存在环。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

链表复杂度分析

[tag_link]

【答案】

（1）基本设计思想：采用快慢指针法（Floyd 判圈算法）。设置两个指针，慢指针每次移动一步，快指针每次移动两步。如果链表中存在环，快指针最终会追上慢指针并相遇；如果不存在环，快指针会首先到达链表尾部（即指向 NULL）。

（2）算法描述（C++）： struct ListNode { int val ; ListNode * next ; ListNode ( int x ) : val ( x ), next ( NULL ) {} }; bool hasCycle ( ListNode * head ) { if ( head == NULL || head -> next == NULL ) { return false ; // 空链表或只有一个节点且无环 } ListNode * slow = head ; ListNode * fast = head ; while ( fast != NULL && fast -> next != NULL ) { slow = slow -> next ; // 慢指针移动一步 fast = fast -> next -> next ; // 快指针移动两步 if ( slow == fast ) { return true ; // 相遇，说明有环 } } return false ; // 快指针到达尾部，说明无环 }

（3）时间复杂度：O(n)，其中 n 为链表节点数。在最坏情况下，需要遍历整个链表一次或两次。空间复杂度：O(1)，仅使用了两个额外指针。【解析】该算法的核心是快慢指针的追逐原理。如果链表有环，快指针每次比慢指针多移动一步，两者在环内的相对距离每次减少一步，因此必然会在有限步内相遇；如果链表无环，快指针将先到达链表尾部（即遇到 NULL）。时间复杂度为 O(n)，因为每个节点最多被访问两次（快指针可能遍历两次）；空间复杂度为 O(1)，因为只使用了常数级别的额外空间。这种方法是判断链表是否存在环的最优解之一，既高效又节省内存。

2009 年第 42 题
数据结构
综合题

(15分)已知一个带有表头结点的单链表，结点结构为：

|data|link|

假设该链表只给出了头指针 list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点( k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回1；否则，只返回0。要求：

(1)描述算法的基本设计思想；

(2)描述算法的详细实现步骤；

(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或者C++或 Java 语言实现),关键之处请给出简要注释。

[tag_link]

1）算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。

2）算法的详细实现步骤： count=0，p 和 q 指向链表表头结点的下一个结点；若 p 为空，转 5；若 count 等于 k，则 q 指向下一个结点；否则，count=count+l; p 指向下一个结点，转 2：若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0；算法结束。

3）算法实现

int FindElement(Node *head, int k)
{
    Node *p1 = head;
    Node *p2 = head;
    for (int i = 0; i < k; i++)
    {
        p1 = p1->link;
        if (p1 == NULL)
        {
            return 0;
        }
    }

    while (p1 != NULL)
    {
        p1 = p1->link;
        p2 = p2->link;
    }
    printf("%d\n", p2->data);
    return 1;
}

提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。【评分说明】① 若所给出的算法采用一遍扫描方式就能得到止确结果，可给满分 15 分：若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分；若采用递归算法得到正确结果的，最高给 10 分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分；若实现的算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。 ②若在算法基本思想描述和算法步骤描述中因文学表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照 () 的标准给分。 ③若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。

← 返回真题分析