数据结构算法应用题

408（全国硕士研究生招生考试计算机学科专业基础）历年数据结构算法大题，枚举如下：

2009：链表中倒数第 k 个节点

题目

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

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

$$|\text{data}|\text{link}|$$

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

1. 描述算法的基本设计思想；
2. 描述算法的详细实现步骤；
3. 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处请给出简要注释。

难度：简单

考察单链表、同向双指针

2010：189. 旋转数组

题目

189. 轮转数组 - 力扣（LeetCode） 设计将 n（n > 1）个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 p（0 < p < n）个位置。即将 R 中的数据由（$X_0,X_1,\dots ,X_{n-1}$）变换为（$X_p,X_{p+1},\dots ,X_{n-1},X_0,X_1,\dots ,X_{p-1}$）。要求：

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

难度：中等

考察数组的原地翻转

2011：4. 寻找两个正序数组的中位数

题目

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

一个长度为 $L$（$L\ge 1$）的升序序列 $S$，处在第 $\lfloor L/2\rfloor$ 个位置的数称为 $S$ 的中位数。

例如，若序列 $S1=(11,13,15,17,19)$，则 $S1$ 的中位数是 $15$；两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 $S2=(2,4,6,8,20)$，则 $S1$ 和 $S2$ 的中位数是 $11$。现在有两个等长升序序列 $A$ 和 $B$，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$ 的中位数。要求：

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

难度：困难

考察二分查找、分块

2012：160. 相交链表

题目

160. 相交链表 - 力扣（LeetCode）

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。 设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 $[\text{data}\mid \text{next}]$，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：

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

难度：简单

考察分叉链表及双指针

2013：169. 多数元素

题目

169. 多数元素 - 力扣（LeetCode） 设包含 4 个数据元素的集合 S={"do", "for", "repeat", "while"}，各元素的查找概率依次为：$p_1=0.35$, $p_2=0.15$, $p_3=0.15$, $p_4=0.35$。将 $S$ 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2。请回答：

1. 若采用顺序存储结构保存 $S$，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
2. 若采用链式存储结构保存 $S$，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

难度：简单

考察摩尔投票法。

2014：二叉树的带权路径长度

题目

1376. 通知所有员工所需的时间 - 力扣（LeetCode） 二叉树的带权路径长度 (WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 $T$，采用二叉链表存储，结点结构为：

$$[\text{left}|\text{weight}|\text{right}]$$

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 $T$ 的根结点的指针，请设计求 $T$ 的 WPL 的算法，要求：

1. 给出算法的基本设计思想；
2. 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义；
3. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

难度：中等

考察带权路径长度 WPL 的概念以及广度优先遍历 BFS 或深度优先遍历 DFS。

2015：83. 删除排序链表中的重复元素

题目

83. 删除排序链表中的重复元素 - 力扣（LeetCode） 用单链表保存 m 个整数，结点的结构为：$[data][link]$，且 $|data|\le n$ (n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：

则删除结点后的 head 为：

要求：

1. 给出算法的基本设计思想。
2. 使用 C 或 C++ 语言，给出单链表结点的数据类型定义。
3. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
4. 说明你所设计算法的时间复杂度和空间复杂度。

难度：简单

考察单链表遍历。

2016：698. 划分为 k 个相等的子集

题目

698. 划分为k个相等的子集 - 力扣（LeetCode） 已知由 $n$ ($n\ge 2$) 个正整数构成的集合 $A=\{a_k|0\le k<n\}$，将其划分为两个不相交的子集 $A_1$ 和 $A_2$，元素个数分别是 $n_1$ 和 $n_2$，$A_1$ 和 $A_2$ 中元素之和分别为 $S_1$ 和 $S_2$。设计一个尽可能高效的划分算法，满足 $|n_1-n_2|$ 最小且 $|S_1-S_2|$ 最大。要求：

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

难度：中等

考察排序，利用快速排序 Pivot 思想对数组进行分组。

2017：将二叉树转换中缀表达式

题目

反向题目：1597. 根据中缀表达式构造二叉表达式树 - 力扣（LeetCode） 请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时：

输出的等价中缀表达式分别为 $(a+b)\ast (c\ast (-d))$ 和 $(a\ast b)+(-(c-d))$。

二叉树结点定义如下：

typedef struct node{
    char data[10];      //存储操作数或操作符
    struct node *left, *right;
}BTree;

要求：

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

难度：简单

考察二叉树中序遍历。

2018：41. 缺失的第一个正数

题目

41. 缺失的第一个正数 - 力扣（LeetCode） 给定一个含 $n(n\ge 1)$ 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 $\{-5,3,2,3\}$ 中未出现的最小正整数是 $1$；数组 $\{1,2,3\}$ 中未出现的最小正整数是 $4$。要求：

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

难度：困难

考察数组的原地标记，技巧性极强。

2019：143. 重排链表

题目

143. 重排链表 - 力扣（LeetCode） 设线性表 $L=(a_1,a_2,a_3,\dots ,a_{n-2},a_{n-1},a_n)$ 采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node
{   int data;
    struct node*next;
} NODE;

请设计一个空间复杂度为 $O(1)$ 且时间上尽可能高效的算法，重新排列 $L$ 中的各结点，得到线性表 $L^{\prime }=(a_1,a_n,a_2,a_{n-1},a_3,a_{n-2},\dots )$。要求：

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

难度：中等

考察链表的原地翻转，交叉连接，快慢指针找中间结点。

2020：不同数组中元素间的最小距离

题目

定义三元组 $(a,b,c)$（$a,b,c$ 均为正数）的距离 $D=|a-b|+|b-c|+|c-a|$。给定 3 个非空整数集合 $S1$、$S2$ 和 $S3$，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)$（其中 $a\in S1,b\in S2,c\in S3$）中的最小距离。例如 $S1=\{-1,0,9\}$，$S2=\{-25,-10,10,11\}$，$S3=\{2,9,17,30,41\}$，则最小距离为 $2$，相应的三元组为 $(9,10,9)$。

要求：

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

难度：未知（个人评价中等）

不同数组中元素间的最小距离，多指针法，技巧性极强。

2021：未找到对应原题

题目

已知无向连通图 G 由顶点集 V 和边集 E 组成，$|E|>0$，当 G 中度为奇数的顶点个数为不大于 2 的偶数时，G 存在包含所有边且长度为 $|E|$ 的路径（称为 EL 路径）。设图 G 采用邻接矩阵存储，类型定义如下:

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
}MGraph;

请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1 ，否则返回 0。要求:

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

难度：简单

考察无向图顶点度的概念和邻接矩阵的遍历，虽然是简单题，但是意味着 408 开始把图论纳入考察范围。

2022：新增考点：并查集，红黑树

题目

已知非空二叉树 $T$ 的结点值均为正数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

$T$ 中不存在的结点在数组 SqBiTNode 中用 $-1$ 表示。例如，对于下图所示的两棵非空二叉树 $T_1$ 和 $T_2$：

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 true，否则，返回 false，要求：

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

个人认为考察红黑树代码的可能性不大，考察并查集代码确有可能，并查集模板虽然有点长，但的确是一个可以千变万化的动态算法。

2023：非空有向图的 K 顶点个数

题目

已知有向图 $G$ 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;      // 图中顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

将图中出度大于入度的顶点称为 K 顶点。例如在题 41 图中，顶点 $a$ 和 $b$ 都是 K 顶点。

请设计算法： int printVertices(MGraph G)，对给定的任意非空有向图 $G$，输出 $G$ 中所有 K 顶点，并返回 K 顶点的个数。要求：

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

难度：中等

2024：判定拓扑序列的唯一性

题目

2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序展开，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;      // 图的顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法：int uniquely(MGraph G)，判定 G 是否存在唯一的拓扑序列。若是，则返回 1，否则返回 0。

要求如下。

1. 给出算法的基本设计思想。（4 分）
2. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（9 分）

难度：中等

BFS/BPS

2025：数组元素最大乘积问题

题目

有两个长度均为 $n$ 的一维整型数组 $A[n]$、$res[n]$，计算 $A[i]$ 与 $A[j]$ （$0\le i\le j\le n-1$）乘积的最大值，并将其保存到 $res[i]$ 中。若 $A[]=\{1,4,-9,6\}$，则得到 $res[]=\{6,24,81,36\}$。现给定数组 $A$，请设计时间空间上尽可能高效的算法 $CalMulMax$，求 $res$ 中各元素的值。函数原型为：void CalMulMax(int A[], int res[], int n)。

1. 给出算法的基本思想。（4 分）
2. 用 C/C++ 描述算法关键之处给出注释。（7 分）
3. 说明时间、空间复杂度。（2 分）

难度：中等

一次遍历保存最大正数和最大负数，而后根据符号与最大值相乘。