2026年9月 GESP C++ 7级认证考试真题（客观题部分）
选 单选题（共 15 题，每题 2 分）
下列 C++ 代码的输出结果是（ ）。
#include <iostream>
using namespace std;
int main() {
int a = 5, b = 3;
cout << (a & b) + (a | b) << endl;
return 0;
}
使用 cmath 或 math.h 中的数学库函数，下列说法中正确的是（ ）。
有 个字符，出现次数分别为 、 、 、 。构造哈夫曼树后，出现次数为 的字符的哈夫曼编码长度为
（ ）。
从 个点连接成的网格的左上角走到右下角，每次只能向右或向下移动，不同的路径共有（ ）条。
在含有 个结点的二叉排序树中查找一个元素，平均时间复杂度和最坏时间复杂度分别为（ ）。
有 堆⽯⼦，数量分别为 、 、 、 。每次可以合并相邻两堆，合并代价为两堆⽯⼦数之和。将所有⽯⼦合
并成一堆的最小总代价为（ ）。
在无权图中，使用 BFS 从起点开始遍历，并在访问由结点 u 扩展的相邻结点 v 时记录 dist[v] =
dist[u] + 1，且起点的 dist 为 0，则最终 dist[v] 表⽰的是（ ）。
在二维网格上实现泛洪填充时，为了防⽌递归层数过深，最适合的非递归实现方式是（ ）。
关于哈希表，下列说法正确的是（ ）。
下列 C++ 代码的输出结果是（ ）。
#include <iostream>
using namespace std;
void inc(int &x) {
x++;
}
int main() {
int a = 3;
inc(a);
cout << a;
return 0;
}
用动态规划求两个序列 和 的最长公共⼦序列长度，若 dp[i][j] 表⽰ 前 i 个元素与 前 j 个
元素的 LCS 长度。当 时，正确的状态转移是（ ）。
下列代码是一维数组优化 0/1 背包的核心片段，执行后 dp[8] 的输出结果是（ ）。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int w = 3, v = 5, W = 8;
int dp[9] = {0};
for (int c = W; c >= w; c--)
dp[c] = max(dp[c], dp[c - w] + v);
cout << dp[8] << endl;
return 0;
}
若要求排序后相等元素的相对顺序保持不变，下列排序算法中最不适宜使用的是（ ）。
下列代码片段的时间复杂度为（ ）。
long long s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j += i)
s += i + j;
已知 int a[6] = {1, 3, 5, 7, 9, 11}; int *p = a + 1;，则表达式 *(p + 3) 的值是（ ）。
判 判断题（共 10 题，每题 2 分）
使用 cmath 或 math.h 中的函数，表达式 exp(0) 的结果值为 1.0，且类型为 double。
采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。
在哈夫曼树中，出现次数更多的叶⼦结点，其深度总是更小。
在一个有向图中，所有顶点的入度之和总是等于所有顶点的出度之和。
广度优先搜索通常借助队列实现，深度优先搜索通常借助栈或递归实现。
快速排序的平均时间复杂度为 ，最坏时间复杂度也为 。
为解决 0/1 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。
使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。
在按层序从 开始对结点编号的完全二叉树中，编号为 （ ）的结点的⽗结点编号为 。
在定义了数组 int arr[10]; 后，表达式 arr 和表达式 &arr[0] 总是等价的。
编 编程操作题（共 2 题，共 50 分）
试题名称：必经之路
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
给定一张有 $n$ 个结点 $m$ 条边的有向图 $G$，$G$ 中的结点依次以 $1,2,\ldots,n$ 编号。第 $i$ 条边（$1\le i\le m$）从结点 $u_i$ 指向结点 $v_i$。
$G$ 中任一入度为 $0$ 的结点可以作为合法起点，任一出度为 $0$ 的结点可以作为合法终点。
如果 $G$ 中所有可能的从合法起点到合法终点的路径都会经过结点 $u$，则称 $u$ 是必经点。注意必经点可以为合法起点或合法终点。
请你求出 $G$ 中所有必经点的编号。
例如，在下图中合法起点有点 $1$ 与点 $2$，合法终点有点 $7$ 与点 $8$。
(1) (5)---->(7)
\ ^ \ ^
v / v /
(3) / (6)
^ \ / \
/ v / v
(2)---->(4) (8)
```text
所有合法起点到合法终点的路径为：
- $1\to 3\to 4\to 5\to 7$
- $1\to 3\to 4\to 5\to 6\to 7$
- $1\to 3\to 4\to 5\to 6\to 8$
- $2\to 3\to 4\to 5\to 7$
- $2\to 3\to 4\to 5\to 6\to 7$
- $2\to 3\to 4\to 5\to 6\to 8$
- $2\to 4\to 5\to 7$
- $2\to 4\to 5\to 6\to 7$
- $2\to 4\to 5\to 6\to 8$
因此必经点有两个，编号分别为 $4,5$。
**输入格式**
第一行，两个正整数 $n,m$，表示有向图 $G$ 中的结点数与边数。
接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示一条从结点 $u_i$ 指向结点 $v_i$ 的有向边。
保证 $G$ 中至少有一个合法起点，至少有一个合法终点，且至少存在一条从一个合法起点到一个合法终点路径，同时不存在孤立点（即出度和入度都为 $0$ 的点）。
**输出格式**
第一行，一个整数，表示必经点的数量 $k$。
如果存在必经点，则第二行从小到大输出 $G$ 中所有必经点的编号。
**样例输入 #1**
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 4
5 7
**样例输出 #1**
2
4 5
**样例输入 #2**
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 5
4 7
**样例输出 #2**
0
**说明/提示**
对于 $40\%$ 的测试点，保证 $1\le n\le 100$，$1\le m\le 200$。
对于所有测试点，保证 $1\le n\le 1000$，$1\le m\le 2000$。保证 $G$ 中至少有一个合法起点，至少有一个合法终点，且至少存在一条从一个合法起点到一个合法终点路径，同时不存在孤立点（即出度和入度都为 $0$ 的点）。试题名称：括号序列
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
对于字符串 $S$ 与 $T$，如果从 $S$ 中删除任意多个字符可以得到 $T$，那么 $T$ 是 $S$ 的子序列。换言之，$T$ 是选取 $S$ 中的若干字符按下标顺序连接而成的。两个子序列不同当且仅当所选取的下标不同。
例如 sun 是 sequence 的子序列，因为从 sequence 中删除 eq、e 和 ce 可以得到 sun；sequence 有 $2^8$ 个不同的子序列，其中有空字符串，也有三个不同的子序列 e，因为 sequence 的第 $2,5,8$ 个字符都为 e，分别保留这三个字符得到的子序列是不同的。
对于字符串 $S$，如果 $S$ 满足以下条件那么 $S$ 是合法括号序列：
- $S$ 是空字符串，或者
- $S$ 可由
(、合法括号序列、)三者连接得到，或者 - $S$ 可由两个合法括号序列连接得到。
例如 ()、()()、(()) 和 (()()) 都是合法括号序列。但是 (()、)( 不是合法括号序列。
给定一个长度为 $n$ 的仅包含 ( 与 ) 的字符串 $S$。请你求出 $S$ 所有 $2^n$ 个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对 $10^9$ 取模的结果。
例如，$S$ 为 ))(()( 时共有 $3$ 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 ()。
输入格式
第一行，一个正整数 $n$，表示字符串 $S$ 的长度。
第二行，长度为 $n$ 的仅包含 ( 与 ) 的字符串 $S$。
输出格式
输出一行，一个整数，表示 $S$ 的合法括号子序列的数量对 $10^9$ 取模的结果。
样例输入 #1
6
))(()(
样例输出 #1
3
样例输入 #2
34
((((((((((((((((()))))))))))))))))
样例输出 #2
333606220
说明/提示
对于 $40\%$ 的测试点，保证 $1\le n\le 400$。
对于所有测试点，保证 $1\le n\le 2000$。