2024年9月 GESP C++ 7级认证考试真题（含编程操作题部分）
选 单选题（共 15 题，每题 2 分）
已知小写字母 $b$ 的 ASCII 码为 $98$ ，下列 C++ 代码的输出结果是（ ）。
#include <iostream>
using namespace std;
int main() {
char a = 'b';
a++;
cout << a;
return 0;
}
已知 $a$ 为 int 类型变量，下列表达式不符合语法的是（ ）。
下列关于 C++ 语言中指针的叙述，不正确的是（ ）。
下列关于 C++ 类的说法，错误的是( )。
某二叉树 $T$ 的先序遍历序列为：{A B D C E G H F}，中序遍历序列为：{D B A H G E C F}，则下列说法中正确的是( )。
一棵完全二叉树有 $431$ 个结点，则叶结点有多少个？( )
下列关于树的说法，错误的是（ ）。
一个简单无向图有 $10$ 个结点、$30$ 条边。再增加多少条边可以成为完全图。（ ）
以下哪个方案可以合理解决或缓解哈希表冲突（ ）。
一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（ ）。
下面程序的输出为（ ）。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
cout << (int)log(8) << endl;
return 0;
}
下面程序的输出为（ ）。
#include <iostream>
#define N 10
using namespace std;
int path[N][N];
int main() {
for (int i = 1; i < N; i++)
path[i][0] = i;
for (int j = 1; j < N; j++)
path[0][j] = j;
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
path[i][j] = path[i - 1][j] + path[i][j - 1];
cout << path[8][4] << endl;
return 0;
}
上题中程序的时间复杂度为（ ）。
下面 fib 函数的时间复杂度为( )。
int fib_rcd[MAX_N];
int fib(int n) {
if (n <= 1)
return 1;
if (fib_rcd[n] > 0)
return fib_rcd[n];
return fib(n - 1) + fib(n - 2);
}
下列选项中，哪个可能是下图的广度优先遍历序列（ ）。
判 判断题（共 10 题，每题 2 分）
表达式 'a' << 1 的结果为 'a '。
在 C++ 语⾔中，函数可以定义在另一个函数定义之内。
选择排序一般是不稳定的。
埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法，欧拉筛法的时间复杂度更低。
使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的结果类型为 double、值约为 $0.5$。
一颗 $n$ 层的完全二叉树，一定有 $2^n - 1$ 个结点。
一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历。
某个哈希表键值 $x$ 为整数，$H(x) = x % p$ 是常用的哈希函数之一，要求 $p$ 选择素数是因为这样不会产生冲突。( )
使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作。
一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。
编 编程操作题（共 2 题，共 50 分）
试题名称：小杨寻宝
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
小杨有一棵包含 $n$ 个节点的树，树上的一些节点放置有宝物。
小杨可以任意选择一个节点作为起点并在树上移动，但是小杨只能经过每条边至多一次，当小杨经过一条边后，这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。
小杨想请你帮他判断自己能否成功取得所有宝物。
输入格式
本题单个测试点内有多组测试数据。输入第一行包含一个正整数 $t$，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。
第一行包含一个正整数 $n$，代表树的节点数。
第二行包含 $n$ 个非负整数 $a_1, a_2, \dots a_n$，其中如果 $a_i = 1$，则节点 $i$ 放置有宝物；若 $a_i = 0$，则节点 $i$ 没有宝物。
之后 $n - 1$ 行，每行包含两个正整数 $x_i, y_i$，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。
输出格式
对于每组测试数据，如果小杨能成功取得所有宝物，输出 Yes，否则输出 No。
样例输入 #1
2
5
0 1 0 1 0
1 2
1 3
3 4
3 5
5
1 1 1 1 1
1 2
1 3
3 4
3 5
样例输出 #1
Yes
No
说明/提示
样例 1 解释
对于第一组测试用例，小杨从节点 $2$ 出发，按照 $2-1-3-4$ 的顺序即可成功取得所有宝物。
数据规模与约定
| 子任务编号 | 数据点占比 | $t$ | $n$ |
| :-: | :-: | :-: | :-: |
| $1$ | $20%$ | $\leq 10$ | $\leq 5$ |
| $2$ | $20%$ | $\leq 10$ | $\leq 10^3$ |
| $3$ | $60%$ | $\leq 10$ | $\leq 10^5$ |
对全部的测试点，保证 $1 \leq t \leq 10$，$1 \leq n \leq 10^5$，$0 \leq a_i \leq 1$，且保证树上至少有一个点放置有宝物。
试题名称：矩阵移动
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
小杨有一个 $n \times m$ 的矩阵，仅包含 01? 三种字符。矩阵的行从上到下编号依次为 $1,2,\dots, n$，列从左到右编号依次为 $1, 2, \dots, m$。小杨开始在矩阵的左上角 $(1,1)$，小杨只能向下或者向右移动，最终到达右下角 $(n, m)$ 时停止，在移动的过程中每经过一个字符 1 得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为 $0$ 分。
小杨可以将矩阵中不超过 $x$ 个字符 ? 变为字符 1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。
输入格式
第一行包含一个正整数 $t$，代表测试用例组数，接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n + 1$ 行。
第一行包含三个正整数 $n, m, x$，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的仅含 01? 的字符串。
输出格式
对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。
样例输入 #1
2
3 3 1
000
111
01?
3 3 1
000
?0?
01?
样例输出 #1
4
2
说明/提示
样例 1 解释
对于第二组测试用例，将 $(2,1)$ 或者 $(3,3)$ 变为 $1$ 均是最优策略。
数据规模与约定
| 子任务编号 | 数据点占比 | $t$ | $n,m$ | $x$ |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $30%$ | $\leq 5$ | $\le 10$ | $=1$ |
| $2$ | $30%$ | $\le 10$ | $\le 500$ | $\le 30$ |
| $3$ | $40%$ | $\le 10$ | $\le 500$ | $\le 300$ |
对全部的测试数据，保证 $1 \leq t \leq 10$，$1 \leq n,m \leq 500$，$1 \leq x \leq 300$，保证所有测试用例 $n \times m$ 的总和不超过 $2.5 \times 10^5$。