GESP第12次认证真题解析|C++七级真题回顾

C++七级

2025年12月

一、单选题（共15题，每题2分，共30分）

1、下面关于C++中形参、实参和定义域的说法中，正确的一项是（ ）。

A.形参是函数定义时所指定的变量，它只在函数内部有效。

B.在函数内部，可以修改传入的形参的值，即使该形参是一个常量引用。

C.实参和形参的类型必须完全一致，否则会导致编译错误。

D.使用指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参。

【答案】A
【考察知识点】C++函数的形参、实参、作用域，常量引用，指针传参【解析】

A选项：形参是函数定义时声明的参数，属于函数的局部变量，其作用域仅限于函数内部，该说法正确。

B选项：常量引用（const &）的核心特性是禁止通过该引用修改所指向的对象，因此无法修改该形参对应的值，该说法错误。

C选项：C++支持隐式类型转换（如int实参传递给double形参），实参和形参类型不必完全一致，只有无法完成合法类型转换时才会编译错误，该说法错误。

D选项：指针形参本身是实参地址的拷贝，对指针变量本身赋值（如p = &x）只会修改形参指针的指向，不会影响实参；只有通过指针解引用（*p = val）才能修改实参指向的内容，该说法错误。

2、已知三个序列：s1 = {3, 1, 8, 2, 5, 6, 7, 4}， s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}， s3 = {1, 8, 3, 5, 7, 6, 2, 4}。以下哪个序列是它们的最长公共子序列（ ）。

A.{1, 8, 5, 6}

B.{1, 5, 6, 7}

C.{1, 8, 6}

D.{1, 5, 7, 4}

【答案】A
【考察知识点】最长公共子序列（LCS）的定义与判定【解析】

最长公共子序列（LCS）要求序列中的元素按顺序出现（不要求连续），且是三个序列共有的最长子序列。

验证A选项{1,8,5,6}：

s1中顺序：1（位置2）→8（位置3）→5（位置5）→6（位置6）；

s2中顺序：1（位置1）→8（位置4）→5（位置2/8）→6（位置5/9）；

s3中顺序：1（位置1）→8（位置2）→5（位置4）→6（位置6）；该序列在三个序列中均按顺序出现，长度为4。

B选项{1,5,6,7}：s1中5在6前、7在6后，顺序为1→5→6→7，但s2中7在6之后（位置7），5在1之后（位置2），但s3中5在8之后、7在5之后、6在7之后，该序列在s3中顺序为1→5→7→6，6的位置在7之后，不满足“1,5,6,7”的顺序，因此不是公共子序列。

C选项长度为3，短于A选项，不符合“最长”要求。

D选项{1,5,7,4}：s1中5在7前、4在7后，但s2中7在4之后（位置7在位置6后），顺序为1→5→4→7，不满足“1,5,7,4”的顺序，因此不是公共子序列。

3、现有一个地址区间为0~10的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到10冲突了就从0开始往后），现在要依次存储（1,3,5,7,9），哈希函数为h(x)=(x²+x)mod11。其中9存储在哈希表哪个地址中（ ）。

A.

B.

C.

D.

【答案】D【考察知识点】哈希函数计算，线性探测法解决哈希冲突【解析】

依次计算每个数的哈希地址，并处理冲突：

1.计算x=1：h(1)=(1²+1)mod11=2mod11=2→地址2为空，存入。

2.计算x=3：h(3)=(9+3)mod11=12mod11=1→地址1为空，存入。

3.计算x=5：h(5)=(25+5)mod11=30mod11=8→地址8为空，存入。

4.计算x=7：h(7)=(49+7)mod11=56mod11=1→ 地址1已被3占用（冲突），往后找第一个空地址：地址2（被1占用）→地址3（空），存入地址3。

5.计算x=9：h(9)=(81+9)mod11=90mod11=2→地址2已被1占用（冲突），往后查找：

地址3（被7占用）→地址4（空），因此9存入地址4。

4、在0/1背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为W，物品的数量为n，其中第i个物品的重量为w[i]，价值为v[i]。以下关于0/1背包问题的描述，正确的是（ ）。

A.在解决0/1背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次。

B. 0/1背包是P问题（多项式时间可解问题），它可以在O(nW)的时间复杂度内解决。

C. 0/1背包问题中，动态规划解法的空间复杂度为O(nW)，但可以通过滚动数组技巧将空间复杂度优化到O(W)。

D. 0/1背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果。

【答案】C
【考察知识点】0/1背包问题的贪心、动态规划解法，时间/空间复杂度，P问题定义【解析】

A选项：贪心算法仅适用于“分数背包”，0/1背包中贪心无法保证最优解（例如高价值高重量物品与多个低价值低重量物品的取舍），该说法错误。

B选项：O(nW)的时间复杂度中，W是背包容量（数值），并非输入规模的多项式，因此0/1背包是NP问题，而非P问题，该说法错误。

C选项：标准动态规划解法使用二维数组dp[i][j]（前i个物品，容量j的最大价值），空间复杂度O(nW)；滚动数组通过逆序遍历容量，仅用一维数组dp[j]，空间复杂度优化为O(W)，该说法正确。

D选项：0/1背包的子问题存在重叠（如计算dp[i][j]需用到dp[i-1][j]和dp[i-1][j-w[i]]），动态规划的核心就是重用子问题的计算结果，该说法错误。

5、一棵深度为6（根节点深度为1）的完全二叉树，节点总数最少有（ ）。

A.31

B.32

C.63

D.64

【答案】B
【考察知识点】完全二叉树的定义与节点数计算【解析】

完全二叉树的定义：除最后一层外，每一层的节点数均达到最大值；最后一层的节点集中在左侧。

深度为k的完全二叉树，节点数最少的情况是：前k-1层为满二叉树，第k层仅有1个节点。

前5层（深度1~5）的满二叉树节点数：2⁵-1=31；

深度为6时，最少节点数=前5层节点数+第6层1个节点=31+1=32。

6、对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。

A.D E B F H J I G C A是它的后序遍历序列。

B.A B C D E F G H I J是它的广度优先遍历序列。

C.A B D E C F G H I J是它的先序遍历序列。

D.D B E A F C H G J I是它的中序遍历序列。

【答案】D
【考察知识点】二叉树的先序、中序、后序遍历，广度优先遍历（层序遍历）【解析】

二叉树遍历规则：

·先序遍历：根节点 → 左子树 → 右子树；

·中序遍历：左子树 → 根节点 → 右子树；

·后序遍历：左子树 → 右子树 → 根节点；

·广度优先（层序）：按层从左到右访问节点。

结合选项分析错误点：

·D选项给出的序列D B E A F C H G J I不符合中序遍历规则。按照中序遍历规则，应为：D B E A F C H G I J，其中，J在I的右子树，应出现在I的后面，D选项序列不满足。因此该说法错误。

·A、B、C选项分别符合后序、层序、先序遍历的规则，说法正确。

7、下面程序的运行结果为（ ）。

A.2

B.3

C.4

D.5

【答案】B【考察知识点】二分查找（寻找第一个大于等于目标值的元素位置）【解析】

该程序实现的是“寻找有序数组中第一个大于等于x的元素的下标”，核心逻辑：

1.初始化左边界l=0，右边界r=n（左闭右开区间[0, n)）；

2.循环条件l < r，计算中间位置mid：

若a[mid] >= x，说明目标位置在左半区间，调整右边界r=mid；

否则，调整左边界l=mid+1；

3.循环结束时l=r，即为第一个≥x的元素下标。

代入数据模拟执行：

数组num = [1,2,2,3,3,4,5,5,6,7]，x=3，n=10；

初始l=0, r=10：

mid=(0+10)/2=5 → a[5]=4 ≥3→ r=5；

mid=(0+5)/2=2 → a[2]=2 <3→ l=3；

mid=(3+5)/2=4 → a[4]=3 ≥3→ r=4；

mid=(3+4)/2=3 → a[3]=3 ≥3→ r=3；

循环结束（l=r=3），返回3。

8、下面程序中，函数query的时间复杂度是（ ）。

A.O(1)

B.O(logn)

C.O(n)

D.O(nlogn)

【答案】B
【考察知识点】算法时间复杂度分析，二分查找的时间复杂度【解析】

query函数实现的是二分查找逻辑，核心循环的执行次数取决于区间[l, r]的缩小速度：

每次循环将查找区间的长度缩小一半（如从n→n/2→n/4→…→1）；

设循环执行次数为k，则满足n/2^k≤1，解得k≤log₂n；

因此，二分查找的时间复杂度为O(logn)。

9、有5个字符，它们出现的次数分别为2次、2次、3次、3次、5次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度WPL（每个字符的出现次数×它的编码长度，再把每个字符结果加起来）的值为（ ）。

A.30

B.34

C.43

D.47

【答案】B【考察知识点】哈夫曼树的构建，加权路径长度（WPL）计算【解析】

哈夫曼树构建规则：

1.每次选取权值最小的两个节点合并为一个新节点，新节点权值为两节点权值之和；

2.重复步骤1，直到所有节点合并为一棵完整的树；

3.WPL = ∑（字符权值×字符的编码长度）=所有非叶子节点的权值之和（等价计算方式）。

步骤1：初始化权值列表[2,2,3,3,5]；步骤2：合并最小的两个节点（2和2）→ 新节点权值4，列表变为[3,3,4,5]；步骤3：合并最小的两个节点（3和3）→ 新节点权值6，列表变为[4,5,6]；步骤4：合并最小的两个节点（4和5）→ 新节点权值9，列表变为[6,9]；步骤5：合并最后两个节点（6和9）→ 新节点权值15，列表变为[15]；步骤6：计算WPL（非叶子节点权值和）：4 + 6 + 9 + 15 = 34。

10、下面程序的运行结果为（ ）。

A.10

B.16

C.26

D.30

【答案】B【考察知识点】递归函数的执行流程与计算【解析】

逐步展开递归调用：

·f(1)=1×2=2；

·f(2)=2×2=4；

·f(3)=f(2)+f(1)=4+2=6；

·f(4)=f(3)+f(2)=6+4=10；

·f(5)=f(4)+f(3)=10+6=16；

因此程序输出16。

11、一个简单无向图G有36条边，且每个顶点的度数都为4，则图G的顶点个数为（ ）。

A.9

B.12

C.18

D.36

【答案】C
【考察知识点】无向图的握手定理（顶点度数与边数的关系）【解析】

握手定理：无向图中所有顶点的度数之和等于边数的2倍。设顶点个数为n，则：
4n=2×36→4n=72→n=18.

12、下面关于二叉树的说法正确的是（ ）。

A.任意二叉树的中序遍历与后序遍历必定不相同。

B.对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定。

C.若二叉树有n个结点，根节点高度为1，则其高度满足：。

D.在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子。

【答案】C【考察知识点】二叉树的遍历特性，二叉树的高度范围【解析】

A选项：反例——只有一个节点的二叉树，中序和后序遍历均为该节点，遍历序列相同，该说法错误。

B选项：先序+后序无法唯一确定二叉树（例如，根节点只有左子树或只有右子树时，先序和后序序列可能相同），只有先序+中序或后序+中序才能唯一确定，该说法错误。

C选项：

最小高度：完全二叉树的高度，（如n=3，）；

最大高度：单链状二叉树（每个节点只有左/右孩子），高度为n；

因此高度范围满足，该说法正确。

D选项：反例——根节点无左孩子但有右孩子时，先序遍历中根后紧跟的是右孩子，该说法错误。

13、假设一个算法时间复杂度的递推式是（n为正整数），和T(0)=1，那么这个算法的时间复杂度是（ ）。

A.O(n)

B.O(nlogn

C.O(n²)

D.O(n²logn)

【答案】B
【考察知识点】求解递归递推式的时间复杂度【解析】

14、下面哪一个可能是下图的深度优先遍历序列（ ）。

A.1, 5, 6, 3, 2, 8, 9, 4, 7

B.1, 5, 8, 9, 7, 4, 6, 3, 2

C.3, 2, 1, 4, 7, 6, 9, 5, 8

D.2, 5, 6, 3, 8, 7, 9, 4, 1

【答案】B
【考察知识点】图的深度优先遍历（DFS）规则【解析】

深度优先遍历规则：从起始节点出发，尽可能深地访问邻接节点，无法继续时回溯，再访问未访问的邻接节点。

分析选项：

B选项1,5,8,9,7,4,6,3,2符合DFS的“先深后回”规则：

从1出发，访问5；从5出发，访问8；从8出发，访问9；从9出发，访问7；从7出发，访问4；回溯到5，访问6；从6出发，访问3；从3出发，访问2。整个过程符合“深度优先、回溯访问”的逻辑，是合法的DFS序列。

A、C、D选项的节点访问顺序违反DFS规则（如中途未回溯却跳转到非邻接的未访问节点），因此不是合法的DFS序列。

15、下面这个有向图的强连通分量的个数是（ ）。

A.3

B.4

C.5

D.6

【答案】C
【考察知识点】有向图的强连通分量（SCC）定义与计数【解析】

强连通分量定义：有向图中，一个子图内的任意两个节点都可以互相到达（双向可达），且该子图无法再扩大。特别的，强连通分量可以只有单个节点。该有向图的强连通分量数量为5，分别为{1, 2}, {3}, {4, 5, 7, 8}, {6, 9, 10, 11}, {12}。

二、判断题（共10题，每题2分，共20分）

1、C++语言中，表达式3 ^ 2的结果类型为int，值为9。

【答案】×
【考察知识点】C++位运算符与算术运算符的区别【解析】

·^在C++中是按位异或运算符，而非幂运算；

·3 ^ 2的二进制计算：3（011）^ 2（010）= 1（001），结果值为1，而非9；

·若要计算3的2次方，需使用pow(3,2)（cmath库）或3*3；

因此该说法错误。

2、使用cmath头文件中的正弦函数，表达式sin(90)的结果类型为double，值约为1.0。

【答案】×
【考察知识点】C++中三角函数的参数单位（弧度制）【解析】

cmath库中的sin函数参数为弧度（rad），而非角度（°）；

90°对应的弧度是Π/2≈1.5708，sin(90)实际计算的是90弧度的正弦值（约为-0.893997），而非90°的正弦值1.0；

正确写法：sin(M_PI/2)（需定义_USE_MATH_DEFINES），结果约为1.0；

因此该说法错误。

3、使用strcmp("10", "9")比较两个字符串，返回值大于0，说明"10"比"9"大。

【答案】×
【考察知识点】C语言strcmp函数的比较规则（字典序）【解析】

strcmp按字符的ASCII码值逐位比较：

第一个字符：'1'的ASCII码是49，'9'的ASCII码是57；

49 < 57，因此strcmp("10", "9")返回负数（<0），说明"10"字典序小于"9"；因此该说法错误。

4、选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。

【答案】√【考察知识点】排序算法的稳定性定义【解析】

稳定排序：排序后，值相等的元素的相对位置不变；

选择排序：每次选择未排序区间的最小元素，与未排序区间第一个元素交换，可能导致相等元素的相对位置改变（如[2, 2, 1]，第一次交换后变为[1, 2, 2]，但若原序列是[2(1), 1, 2(2)]，排序后变为[1, 2(2), 2(1)]，相对位置改变），因此不稳定；

冒泡排序：仅交换相邻的逆序元素，相等元素不会交换，相对位置不变，因此稳定；

因此该说法正确。

5、求两个长度为序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从O(n²)优化到O(n)。

【答案】√【考察知识点】LCS的动态规划优化（滚动数组）【解析】

标准LCS动态规划使用二维数组dp[i][j]（前i个字符与前j个字符的LCS长度），空间复杂度O(n²)；

观察状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)（当字符相等时），仅依赖上一行（i-1）的结果；

使用滚动数组（一维数组），逆序遍历列维度，可将空间复杂度优化到O(n)；因此该说法正确。

6、在无向图中，所有顶点的度数之和等于边数的两倍。

【答案】√【考察知识点】无向图的握手定理【解析】

无向图中，每条边连接两个顶点，会为两个顶点各贡献1个度数；

因此所有顶点的度数之和=边数× 2；

该说法是握手定理的核心内容，正确。

6、使用邻接矩阵存储一个有V个顶点、E条边的图，对该图进行一次完整的BFS遍历，时间复杂度为O(V+E)。

【答案】×
【考察知识点】BFS的时间复杂度（邻接矩阵vs邻接表）【解析】

邻接表存储：BFS遍历的时间复杂度为O(V+E)（遍历每个顶点V，遍历每条边E）；

邻接矩阵存储：每个顶点需要遍历V个列（检查是否有边），因此时间复杂度为O(V²)（与E无关）；题目中明确是邻接矩阵存储，因此时间复杂度不是O(V+E)，该说法错误。

8、在图像处理或游戏开发中，泛洪（flood fill）算法既可以用BFS实现，也可以用DFS实现。

【答案】√【考察知识点】泛洪算法的实现方式【解析】

泛洪算法（洪水填充）的核心是遍历连通区域（如像素、网格）；

BFS（广度优先）：按层遍历连通区域，适合“逐层扩散”的场景；

DFS（深度优先）：递归/栈遍历连通区域，适合“深度优先扩散”的场景；

两者均可实现泛洪算法，因此该说法正确。

9、使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为O(n)，其中n为元素个数。

【答案】√【考察知识点】哈希表的链地址法，查找的时间复杂度【解析】

链地址法：每个槽位对应一个链表，冲突的元素存入该链表；

最坏情况：所有元素映射到同一个槽位，该槽位的链表长度为n；

查找时需遍历该链表，最坏时间复杂度为O(n)；

因此该说法正确。

10、一个包含V个顶点的连通无向图，其任何一棵生成树都恰好包含V-1条边。

【答案】√【考察知识点】生成树的定义与性质【解析】

生成树定义：连通图的极小连通子图，包含所有顶点，且边数最少；

性质：V个顶点的连通无向图，生成树的边数必为V-1（边数少于V-1则不连通，多于V-1则有环）；

因此该说法正确。

三、编程题（共2题，每题25分，共50分）

编程题1

• 试题名称：城市规划

• 时间限制：1.0s

• 内存限制：512.0M

题目描述

A 国有n座城市，城市之间由m条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2,…,n编号。第i(1≤i≤m)条双向道路连接城市u_i与城市v_i。

对于城市u和城市v而言，它们之间的连通度d(u,v)定义为从城市u出发到达城市v所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足d(u,v)=d(v,u)，特殊地有d(u,u)=0。

现在A国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得max_1≤i≤nd(u,i)最小的u，若存在多个可能的u则选取其中最小的。

输入格式

第一行，两个正整数n,m，表示A国的城市数量与双向道路数量。接下来m行，每行两个整数u_i,v_i，表示一条连接城市u_i与城市v_i的双向道路。

输出格式

输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。

样例

输入样例1

输出样例1

输入样例2

输出样例2

数据范围

对于40%的测试点，保证1≤n≤300。对于所有测试点，保证1≤n≤2000,1≤m≤2000,1≤u_i,v_i≤n。

【考察知识点】图的广度优先遍历（BFS）、最短路径（无权图）、枚举与最优解选择

【解析】

1.问题核心：

对每个城市u，计算其到所有其他城市的最短路径（连通度），并找到其中的最大值（建设难度）；

在所有城市中，找到建设难度最小的城市（若有多个，选编号最小的）。

2.解法思路：

由于是无权图，最短路径可通过BFS高效求解（时间复杂度O(n+m)per BFS）；

枚举每个城市作为起点，执行BFS，记录该城市到所有其他城市的最短路径，计算最大路径长度（建设难度）；

维护当前最优解：初始为城市1，遍历过程中若发现建设难度更小的城市，更新最优解；若难度相同，保留编号更小的城市。

3.关键细节：

邻接表存储图结构，适合处理稀疏图（m≤2000）；

BFS时初始化距离数组为“无穷大”（如n+1），起点距离设为0；

队列实现BFS，保证按层遍历，得到的是最短路径。

参考程序

编程题2

• 试题名称：学习小组

• 时间限制：1.0 s

• 内存限制：512.0 MB

题目描述

班主任计划将班级里的n

名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以1,2,…,n编号，第i名同学有其发言积极度c_i。

观察发现，如果一个学习小组中恰好包含编号为p₁,p₂,...,p_k的k名同学，则该学习小组的基础讨论积极度为a_k，综合讨论积极度为a_k+max{c_p1,c_p2,…,c_pk}-min{c_p1,c_p2,…,c_pk}，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。

给定基础讨论积极度a₁,a₂,…,a_n，请你计算将这n名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。

输入格式

第一行，一个正整数n，表示班级人数。第二行，n个非负整数c₁,c₂,…,c_n，表示每位同学的发言积极度。第三行，n个非负整数a₁,a₂,…,a_n，表示不同人数学习小组的基础讨论积极度。

输出格式

输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。

样例

输入样例1

输出样例1

输入样例2

输出样例2

数据范围

对于40%的测试点，保证c_i=0。对于所有测试点，保证1≤n≤300，0≤c_i≤10⁴，0≤a_i≤10⁴。

【考察知识点】动态规划（DP）、排序优化、区间最值

【解析】

1.问题核心：

将n个同学划分成若干组，每组的综合积极度=a_k+(maxc-minc)（k为组人数）；

求所有划分方案中综合积极度之和的最大值。

2.解法思路：

排序优化：将c_i排序后，任意连续区间[l,r]的maxc-minc=c[r]-c[l]（简化计算）；

动态规划定义：f[i][j]表示前i个同学，划分成j组的最大综合积极度；

状态转移：枚举最后一组的人数k，则f[i][j]=max(f[i-k][j-1]+a_k+(c[i]-c[i-k+1]))；

最终答案：max(f[n][1],f[n][2],…,f[n][n])（所有可能的分组数）。

3.关键细节：

排序c数组，将“任意子集的最值差”转化为“连续区间的端点差”，不影响最终结果（分组是任意的，排序后仅改变计算方式）；

动态规划的枚举顺序：从后往前枚举，避免重复计算。

参考程序