2024年12月 GESP C++ 7级认证考试真题（含编程操作题部分）
选 单选题（共 15 题，每题 2 分）
已知小写字母 $b$ 的 ASCII 码为 $98$，下列 C++ 代码的输出结果是（ ）。
#include <iostream>
using namespace std;
int main() {
char a = 'b';
cout << a + 1;
return 0;
}
已知 $a$ 为 int 类型变量，$p$ 为 int * 类型变量，下列赋值语句不符合语法的是（ ）。
已知数组 $a$ 的定义 int a[10] = {0}; ，下列说法不正确的是（ ）。
下列关于 C++ 类的说法，错误的是( )。
下列关于有向图的说法，错误的是( )。
一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有 $197$ 个结点，则其叶结点有多少个？( )
下列关于二叉树的说法，错误的是（ ）。
一个简单无向图有 $10$ 个结点、$6$ 条边。在最差情况，至少增加多少条边可以使其连通？（ ）
一个哈希表，包括 $n$ 个位置（分别编号 $0 \sim (n-1)$），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。
以下关于动态规划的说法中，错误的是（ ）。
下面程序的输出为（ ）。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
cout << (int)exp(2) << endl;
return 0;
}
下面程序的输出为（ ）。
#include <iostream>
#define N 10
using namespace std;
int h[N];
int main() {
h[0] = h[1] = 1;
for (int n = 2; n < N; n++)
for (int j = 0; j < n; j++)
h[n] += h[j] * h[n - j - 1];
cout << h[6] << endl;
return 0;
}
上题中程序的时间复杂度为（ ）。
下面 init_sieve 函数的时间复杂度为( )。
int sieve[MAX_N];
void init_sieve(int n) {
for (int i = 1; i <= n; i++)
sieve[i] = i;
for (int i = 2; i <= n; i++)
for (int j = i; j <= n; j += i)
sieve[j]--;
}
下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。
判 判断题（共 10 题，每题 2 分）
表达式 5 ^ 3 的结果为 $125$。
在 C++ 语言中，函数定义和函数调用可以不在同一个文件内。
在 $n$ 个元素中进行二分查找，平均时间复杂度是 $O(\log n)$，但须要事先进行排序。
unsigned long long 类型是 C++ 语⾔中表达范围最大的非负整数类型之一，其表达范围是 。超出该范围的非负整数运算，将无法使用 C++ 语⾔进行计算。
使用 math.h 或 cmath 头文件中的函数，表达式 log2(32) 的结果为 $5$ 、类型为 int。
C++ 是一种面向对象编程语言，C 则不是。继承是面向对象三大特性之一。因此，使用 C 语言无法实现继承。
邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。
MD5 是一种常见的哈希函数，可以由任意长度的数据生成 $128$ 位的哈希值，曾广泛应用于数据完整性校验。
中国科学家的系列工作首次发现了可实用的 MD5 破解方法。之后，MD5 逐渐被其他哈希函数所取代。
递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。
一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。
编 编程操作题（共 2 题，共 50 分）
试题名称：武器购买
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
商店里有 $n$ 个武器，第 $i$ 个武器的强度为 $p_i$，花费为 $c_i$。
小杨想要购买一些武器，满足这些武器的总强度不小于 $P$，总花费不超过 $Q$，小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。
输入格式
第一行包含一个正整数 $t$，代表测试数据组数。
对于每组测试数据，第一行包含三个正整数 $n,P,Q$，含义如题面所示。
之后 $n$ 行，每行包含两个正整数 $p_i,c_i$，代表武器的强度和花费。
输出格式
对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出 -1。
样例输入 #1
3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3
样例输出 #1
3
-1
-1
说明/提示
| 子任务编号 | 数据点占比 | $n$ | $p_i$ | $c_i$ | $P$ | $Q$ |
| :--------: | :--------: | :--------: | :-----------------: | :-----------------: | :-----------------: | :-----------------: |
| $1$ | $20%$ | $\leq 10$ | $1$ | $1$ | $\leq 10$ | $\leq 10$ |
| $2$ | $20%$ | $\leq 100$ | $\leq 5\times 10^4$ | $1$ | $\leq 5\times 10^4$ | $2$ |
| $3$ | $60%$ | $\leq 100$ | $\leq 5\times 10^4$ | $\leq 5\times 10^4$ | $\leq 5\times 10^4$ | $\leq 5\times 10^4$ |
对于全部数据，保证有 $1\leq t\leq 10$，$1\leq n\leq 100$，$1\leq p_i,c_i,P,Q\leq 5\times 10^4$。
试题名称：燃烧
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
小杨有一棵包含 $n$ 个节点的树，其中节点的编号从 $1$ 到 $n$。节点 $i$ 的权值为 $a_i$。
小杨可以选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的在节点间扩散直到不会有新的节点被引燃。
小杨想知道在合理选择初始节点的情况下，最多可以燃烧多少个节点。
输入格式
第一行包含一个正整数 $n$，表示节点数量。
第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，代表节点权值。
之后 $n-1$ 行，每行包含两个正整数 $u_i,v_i$，代表存在一条连接节点 $u_i$ 和 $v_i$ 的边。
输出格式
输出一个正整数，代表最多燃烧的节点个数。
样例输入 #1
5
6 2 3 4 5
1 2
2 3
2 5
1 4
样例输出 #1
3
说明/提示
| 子任务编号 | 数据点占比 | $n$ |
| :--------: | :--------: | :---------: |
| $1$ | $20%$ | $\leq 10$ |
| $2$ | $20%$ | $\leq 100$ |
| $3$ | $60%$ | $\leq 10^5$ |
对于全部数据，保证有 $1\leq n\leq 10^5$，$1\leq a_i\leq 10^6$。