GESP 2024年12月认证 C++ 7级真题
好的，我现在需要仔细处理用户提供的PDF内容，将其完整整理出来。首先，用户的要求是不能有任何精简或概括，必须保持所有内容与原文完全一致，包括题目、选项、代码段等，并且排版要美观，不能省略任何部分。
首先，我会检查用户提供的文档结构。看起来这是一个CCF编程能力等级认证的C++七级考试题目，包含单选题、判断题和编程题。每个部分都有详细的题目和选项，还有一些代码示例。
接下来，我需要确保所有题目的格式正确。例如，单选题的题号和选项排列可能需要调整，确保表格结构正确。用户提供的部分表格可能存在格式问题，比如题号排列可能不整齐，需要按照原文的表格结构来复原。
对于代码部分，用户提供的参考程序可能存在缩进问题，需要保留原始代码的缩进和结构。例如，编程题1和2的参考程序中的循环和条件语句的缩进是否正确，是否有遗漏的括号等。同时，要注意代码中的特殊符号是否正确转义，比如尖括号是否需要使用HTML实体。
另外，数学公式部分，如题目中涉及的复杂度表示，可能需要使用LaTeX格式来正确呈现，确保公式中的上下标和符号正确显示。例如，第7题中的“⌊log₂n⌋”需要正确转换为LaTeX格式。
在处理判断题时，要注意题号的对齐和答案的标记是否正确。用户提供的判断题答案部分可能存在空格或符号错误，需要核对每个题号的答案是否正确对应。
还需要检查所有题目的选项是否完整，没有遗漏。例如，第1题到第15题的每个选项是否都正确列出，特别是用户提供的表格中可能存在合并单元格的情况，需要正确拆分以确保每个选项独立显示。
在处理编程题时，要确保输入输出格式的描述准确无误，样例输入和输出的排版正确，包括子任务表格中的参数是否正确对齐。此外，参考程序中的代码可能存在拼写错误或语法错误，需要仔细检查，例如变量名是否正确，循环结构是否闭合等。
最后，整体排版要美观，可能需要使用Markdown的表格、代码块、列表等元素来保持结构清晰。确保所有内容与原文一致，没有遗漏或添加任何信息。
在整理过程中，如果发现任何不确定的地方，比如代码段中的不完整行或可能的拼写错误，需要根据上下文进行合理推断，确保输出的内容尽可能接近原始文档。同时，注意中英文标点的正确使用，避免出现乱码或格式错误。
完成所有检查后，将整理好的内容按照用户的要求输出，确保每个部分都正确无误，排版美观，内容完整。
CCF编程能力等级认证
Grade Examination of Software Programming
C++七级
2024年12月
1 单选题（每题2分，共30分）
| 题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 答案 | D | A | A | C | C | B | B | C | D | D | B | A | D | B | A |
第1题
已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（ ）。
第2题
已知 a 为 int 类型变量，p 为 int* 类型变量，下列赋值语句不符合语法的是（ ）。
第3题
已知数组 a 的定义 int a[10] = {0};，下列说法不正确的是（ ）。
• A. 语句 a[-1] = 0; 会产生编译错误。
• B. 数组 a 的所有元素均被初始化为 0。
• C. 数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。
• D. 语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。
第4题
下列关于 C++ 类的说法，错误的是（ ）。
• A. 构造函数不能声明为虚函数，但析构函数可以。
• B. 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
• C. 静态方法属于类、不属于对象，因此不能使用 对象.方法(...) 的形式调用静态方法。
• D. 析构派生类的对象时，一定会调用基类的析构函数。
第5题
下列关于有向图的说法，错误的是（ ）。
• A. n 个顶点的弱连通有向图，最少有 n-1 条边。
• B. n 个顶点的强连通有向图，最少有 n 条边。
• C. n 个顶点的有向图，最多有 n×(n-1) 条边。
• D. n 个顶点的有向完全图，有 n×(n-1) 条边。
第6题
一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有 197 个结点，则其叶结点有多少个？（ ）
• A. 98
• B. 99
• C. 不存在这样的树。
• D. 无法确定叶结点数量。
第7题
下列关于二叉树的说法，错误的是（ ）。
• A. 二叉排序树的中序遍历顺序与元素排序的顺序是相同的。
• B. n 个元素的二叉排序树，其高一定为 ⌊log₂n⌋。
• C. 自平衡二叉查找树（AVL 树）是一种二叉排序树。
• D. 任意的森林，都可以映射为一棵二叉树进行表达和存储。
第8题
一个简单无向图有 10 个结点、6 条边。在最差情况，至少增加多少条边可以使其连通？（ ）
• A. 3
• B. 4
• C. 6
• D. 9
第9题
一个哈希表，包括 n 个位置（分别编号 0~(n-1)），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。
• A. 如果哈希函数取值范围为 0~(n-1)，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 O(n)。
• B. 如果哈希函数取值范围为 0~(n-1)，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 O(1)。
• C. 如果哈希函数取值范围为 0~(m-1)（m < n），且当发生哈希函数碰撞时仅在 m~(n-1) 的范围内寻找空位，则查询操作的最差时间复杂度为 O(n-m)。
• D. 查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。
第10题
以下关于动态规划的说法中，错误的是（ ）。
• A. 动态规划方法将原问题分解为一个或多个相似的子问题。
• B. 动态规划方法通常能够列出递推公式。
• C. 动态规划方法有递推和递归两种实现形式。
• D. 递推实现动态规划方法的时间复杂度总是不低于递归实现。
第11题
下面程序的输出为（ ）。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
cout << (int)exp(2) << endl;
return 0;
} • A. 4
• B. 7
• C. 100
• D. 无法通过编译。
第12题
下面程序的输出为（ ）。
#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;
} • A. 132
• B. 1430
• C. 16796
• D. 结果是随机的。
第13题
上题中程序的时间复杂度为（ ）。
• A. O(N)
• B. O(N log N)
• C. O(N²)
• D. O(2^N)
第14题
下面 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]--;
} • A. O(n)
• B. O(n log n)
• C. O(n²)
• D. 无法正常结束。
第15题
下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。
• A. 1,2,3,5,7,8,6,9,4
• B. 1,4,7,8,9,5,2,3,6
• C. 1,5,7,8,9,4,2,3,6
• D. 1,2,3,6,9,8,5,7,4
2 判断题（每题2分，共20分）
| 题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 答案 | × | √ | √ | × | × | × | √ | √ | √ | × |
第1题
表达式 5 ^ 3 的结果为 125。
第2题
在 C++ 语言中，函数定义和函数调用可以不在同一个文件内。
第3题
在 n 个元素中进行二分查找，平均时间复杂度是 O(log n)，但需要事先进行排序。
第4题
unsigned long long 类型是 C++ 语言中表达范围最大的非负整数类型之一，其表达范围是 [0, 2^64 - 1]。超出该范围的非负整数运算，将无法使用 C++ 语言进行计算。
第5题
使用 math.h 或 cmath 头文件中的函数，表达式 log2(32) 的结果为 5、类型为 int。
第6题
C++ 是一种面向对象编程语言，C 则不是。继承是面向对象三大特性之一。因此，使用 C 语言无法实现继承。
第7题
邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。
第8题
MD5 是一种常见的哈希函数，可以由任意长度的数据生成 128 位的哈希值，曾广泛应用于数据完整性校验。中国科学家的系列工作首次发现了可实用的 MD5 破解方法。之后，MD5 逐渐被其他哈希函数所取代。
第9题
递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。
第10题
一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。
3 编程题（每题25分，共50分）
3.1 编程题1
试题名称：武器购买
时间限制：1.0s
内存限制：512.0MB
题面描述
商店里有 n 个武器，第 i 个武器的强度为 p_i，花费为 c_i。小杨想要购买一些武器，满足这些武器的总强度不小于 P，总花费不超过 Q。小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。
输入格式
第一行包含一个正整数 t，代表测试数据组数。
对于每组测试数据，第一行包含三个正整数 n, P, Q，含义如题面所示。
之后 n 行，每行包含两个正整数 p_i, c_i，代表武器的强度和花费。
输出格式
对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出 -1。
样例
输入：
3
2 3 2
3 3
1 2
4 1 2
8 1
2 9
2 3
10 1000 1000
1 1 输出：
-1
2
-1 子任务
| 子任务编号 | 数据点占比 | n | p_i | c_i | P | Q |
|---|---|---|---|---|---|---|
| 1 | 20% | ≤10 | 1 | 1 | ≤10 | ≤10 |
| 2 | 20% | ≤100 | ≤10^4 | 1 | ≤5×10^4 | ≤5×10^4 |
| 3 | 60% | ≤100 | ≤5×10^4 | ≤5×10^4 | ≤5×10^4 | ≤5×10^4 |
参考程序
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[50010];
ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
dp[0] = 0;
for (auto& weapon : weapons) {
int p = weapon.first;
int c = weapon.second;
for (int j = Q; j >= c; --j) {
if (dp[j - c] >= 0) {
dp[j] = max(dp[j], dp[j - c] + p);
}
}
}
for (int j = 0; j <= Q; ++j) {
if (dp[j] >= P) {
return j;
}
}
return -1;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, P, Q;
cin >> n >> P >> Q;
memset(dp, -0x3f, sizeof dp);
vector<pair<int, int>> weapons(n);
for (int i = 0; i < n; ++i) {
cin >> weapons[i].first >> weapons[i].second;
}
cout << solve(n, P, Q, weapons) << "\n";
}
return 0;
} 3.2 编程题2
试题名称：燃烧
时间限制：1.0s
内存限制：512.0MB
题面描述
小杨有一棵包含 n 个节点的树，其中节点的编号从 1 到 n。节点 i 的权值为 a_i。小杨可以选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃，火焰会在节点间扩散直到不会有新的节点被引燃。小杨想知道在合理选择初始节点的情况下，最多可以燃烧多少个节点。
输入格式
第一行包含一个正整数 n，代表节点数量。
第二行包含 n 个正整数 a_1, a_2, ..., a_n，代表节点权值。
之后 n-1 行，每行包含两个正整数 u_i, v_i，代表存在一条连接节点 u_i 和 v_i 的边。
输出格式
输出一个正整数，代表最多燃烧的节点个数。
样例
输入：
5
2 6 2 3 5
3 1
2 4
5 2
4 5 输出：
3 子任务
| 子任务编号 | 数据点占比 | n |
|---|---|---|
| 1 | 20% | ≤10 |
| 2 | 20% | ≤100 |
| 3 | 60% | ≤10^5 |
参考程序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], sum[N], down[N];
vector<int> g[N];
void dfs_down(int x, int fa) {
down[x] = 1;
for (int i : g[x]) {
if (i != fa) {
dfs_down(i, x);
if (a[x] > a[i]) {
down[x] += down[i];
}
}
}
}
void dfs_sum(int x, int fa) {
if (a[x] > a[fa]) {
sum[x] += sum[fa] + down[fa];
}
for (int i : g[x]) {
if (i != fa) {
dfs_sum(i, x);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs_down(1, 0);
dfs_sum(1, 0);
int mx = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx, sum[i] + down[i]);
}
cout << mx << "\n";
return 0;
}