2025年12月 GESP C++ 7级认证考试真题（含编程操作题部分）
选 单选题（共 15 题，每题 2 分）
下面关于 C++ 中形参、实参和定义域的说法中，正确的一项是（ ）。
已知三个序列：$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}$。以下哪个序列是它们的最长公共子序列（ ）。
现有一个地址区间为 $[0, 9]$ 的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到 $9$ 冲突了就从 $0$ 开始往后），现在要依次存储 $[3, 5, 2, 9, 1, 8]$，哈希函数为 $h(x) = x % 10$。其中 $8$ 存储在哈希表哪个地址中（ ）。
在 0/1 背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为 $W$，物品的数量为 $n$，其中第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$。以下关于 0/1 背包问题的描述，正确的是（ ）。
一棵深度为 $6$（根节点深度为 $1$）的完全二叉树，节点总数最少有（ ）。
对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。
下面程序的运行结果为（ ）。
#include <iostream>
int query(int n, int *a, int x) {
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
if (l == n) return -1;
return l;
}
int main() {
int n = 10;
int x = 3;
int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
std::cout << query(n, num, x) << "\n";
return 0;
}
下面程序中，函数 query 的时间复杂度是（ ）。
#include <iostream>
int query(int n, int *a, int x) {
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
if (l == n) return -1;
return l;
}
int main() {
int n = 10;
int x = 3;
int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
std::cout << query(n, num, x) << "\n";
return 0;
}
有 $5$ 个字符，它们出现的次数分别为 $2$ 次、$2$ 次、$3$ 次、$3$ 次、$5$ 次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度 WPL（每个字符的出现次数 $\times$ 它的编码长度，再把每个字符结果加起来）的值为（ ）。
下面程序的运行结果为（ ）。
#include <iostream>
using namespace std;
int f(int n) {
if (n <= 2) return n * 2;
return f(n - 1) + f(n - 2);
}
int main() {
cout << f(5) << endl;
return 0;
}
一个简单无向图有 $36$ 条边，且每个顶点的度数都为 $4$，则图的顶点个数为（ ）。
下面关于二叉树的说法正确的是（ ）。
假设一个算法时间复杂度的递推式是 $T(n) = 2T(n/2) + n$（$n$ 为正整数），和 $T(1) = 1$，那么这个算法的时间复杂度是（ ）。
下面哪一个可能是下图的深度优先遍历序列（ ）。
下面这个有向图的强连通分量的个数是（ ）。
判 判断题（共 10 题，每题 2 分）
C++ 语言中，表达式 3 ^ 2 的结果类型为 int，值为 $9$。
使用 cmath 头文件中的正弦函数，表达式 sin(90) 的结果类型为 double，值约为 $1.0$。
使用 strcmp("10", "9") 比较两个字符串，返回值大于 $0$ ，说明 "10" 比 "9" 大。
选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。
求两个长度为 $n$ 的序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从 $O(n^2)$ 优化到 $O(n)$。
在无向图中，所有顶点的度数之和等于边数的两倍。
使用邻接矩阵存储一个有 $n$ 个顶点、 $m$ 条边的图，对该图进行一次完整的 BFS 遍历，时间复杂度为 $O(n^2)$。
在图像处理或游戏开发中，泛洪（flood fill）算法既可以用 BFS 实现，也可以用 DFS 实现。
使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 $O(n)$，其中 $n$ 为元素个数。
一个包含 $n$ 个顶点的连通无向图，其任何一棵生成树都恰好包含 $n-1$ 条边。
编 编程操作题（共 2 题，共 50 分）
试题名称：城市规划
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
A 国有 $n$ 座城市，城市之间由 $m$ 条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以 $1,2,\ldots,n$ 编号。第 $i$（$1\le i\le 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\limits_{1\le i\le n}d(u,i)$ 最小的 $u$，若存在多个可能的 $u$ 则选取其中最小的。
输入格式
第一行，两个正整数 $n,m$，表示 A 国的城市数量与双向道路数量。
接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一条连接城市 $u_i$ 与城市 $v_i$ 的双向道路。
输出格式
输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。
样例输入 #1
3 3
1 2
1 3
2 3
样例输出 #1
1
样例输入 #2
4 4
1 2
2 3
3 4
2 4
样例输出 #2
2
说明/提示
对于 $40%$ 的测试点，保证 $1\le n\le 300$。
对于所有测试点，保证 $1\le n\le 2000$，$1\le m\le 2000$，$1\le u_i,v_i\le n$。
试题名称：学习小组
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以 $1,2,\ldots,n$ 编号，第 $i$ 名同学有其发言积极度 $c_i$。
观察发现，如果一个学习小组中恰好包含编号为 $p_1,p_2,\ldots,p_k$ 的 $k$ 名同学，则该学习小组的基础讨论积极度为 $a_k$，综合讨论积极度为 $a_k+\max{c_{p_1},c_{p_2},\ldots,c_{p_k}}−\min{c_{p_1},c_{p_2},\ldots,c_{p_k}}$，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。
给定基础讨论积极度 $a_1,a_2,\ldots,a_n$，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。
输入格式
第一行，一个正整数 $n$，表示班级人数。
第二行，$n$ 个非负整数 $c_1,c_2,\ldots,c_n$，表示每位同学的发言积极度。
第三行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示不同人数学习小组的基础讨论积极度。
输出格式
输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。
样例输入 #1
4
2 1 3 2
1 5 6 3
样例输出 #1
12
样例输入 #2
8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4
样例输出 #2
21
说明/提示
对于 $40%$ 的测试点，保证 $c_i=0$。
对于所有测试点，保证 $1\le n\le 300$，$0\le c_i\le 10^4$，$0\le a_i\le 10^4$。