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/1背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为
，物品的数量为 ，其中第 个物品的重量为 ，价值为 。以下关于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（每个字符的出现次数 它的编码长度，再把每个字符结果加起来）的值为（ ）。
下面程序的运行结果为（ ）。
#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，则图 的顶点个数为（ ）。
下面关于二叉树的说法正确的是（ ）。
假设一个算法时间复杂度的递推式是 （ 为正整数），和 ，那么这个算法的
时间复杂度是（ ）。
下面哪一个可能是下图的深度优先遍历序列（ ）。
下面这个有向图的强连通分量的个数是（ ）。
判 判断题（共 10 题，每题 2 分）
C++语⾔中，表达式3 ^ 2的结果类型为int，值为9。
使用cmath头文件中的正弦函数，表达式sin(90)的结果类型为double，值约为1.0。
使用strcmp("10", "9")比较两个字符串，返回值大于0，说明"10"比"9"大。
选择排序是一种不稳定的排序算法，⽽冒泡排序是一种稳定的排序算法。
求两个长度为 序列的最长公共⼦序列（LCS）长度时，可以使用滚动数组将空间复杂度从 优化到
。
在无向图中，所有顶点的度数之和等于边数的两倍。
使用邻接矩阵存储一个有 个顶点、 条边的图，对该图进行一次完整的BFS遍历，时间复杂度为
。
在图像处理或游戏开发中，泛洪（flood fill）算法既可以用BFS实现，也可以用DFS实现。
使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 ，
其中 为元素个数。
一个包含 个顶点的连通无向图，其任何一棵生成树都恰好包含 条边。
编 编程操作题（共 2 题，共 50 分）
试题名称：城市规划
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
A 国有 座城市，城市之间由 条双向道路连接，任意⼀座城市均可经过若⼲条双向道路到达另⼀座城市。城市依
次以 编号。第 （ ）条双向道路连接城市 与城市 。
对于城市 和城市 ⽽⾔，它们之间的连通度 定义为从城市 出发到达城市 所需经过的双向道路的最少条
数。由于道路是双向的，可以知道连通度满⾜ ，特殊地有 。
现在 A 国正在规划城市建设⽅案。城市 的建设难度为它到其它城市的最⼤连通度。请你求出建设难度最⼩的城
市，如果有多个满⾜条件的城市，则选取其中编号最⼩的城市。形式化地，你需要求出使得 最⼩的
，若存在多个可能的 则选取其中最⼩的。
输入格式
第⼀⾏，两个正整数 ，表⽰ A 国的城市数量与双向道路数量。
接下来 ⾏，每⾏两个整数 ，表⽰⼀条连接城市 与城市 的双向道路。
输出格式
输出⼀⾏，⼀个整数，表⽰建设难度最⼩的城市编号。如果有多个满⾜条件的城市，则选取其中编号最⼩的城市。
数据范围
对于 的测试点，保证 。
对于所有测试点，保证 ， ， 。
试题名称：学习⼩组
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
班主任计划将班级⾥的 名同学划分为若⼲个学习⼩组，每名同学都需要分⼊某⼀个学习⼩组中。班级⾥的同学依
次以 编号，第 名同学有其发⾔积极度 。
观察发现，如果⼀个学习⼩组中恰好包含编号为 的 名同学，则该学习⼩组的基础讨论积极度为 ，
综合讨论积极度为 ，也即基础讨论积极度加上⼩组内同学的最⼤
发⾔积极度与最⼩发⾔积极度之差。
给定基础讨论积极度 ，请你计算将这 名同学划分为学习⼩组的所有可能⽅案中，综合讨论积极度之
和的最⼤值。
输入格式
第⼀⾏，⼀个正整数 ，表⽰班级⼈数。
第⼆⾏， 个⾮负整数 ，表⽰每位同学的发⾔积极度。
第三⾏， 个⾮负整数 ，表⽰不同⼈数学习⼩组的基础讨论积极度。
输出格式
输出⼀⾏，⼀个整数，表⽰所有划分⽅案中，学习⼩组综合讨论积极度之和的最⼤值。
数据范围
对于 的测试点，保证 。
对于所有测试点，保证 ， ， 。