2025年6月CCF—GESP（C++七级）编程能力等级认证试卷
七级
2025
2026-04-02 18:09:51
186次
一、单选题
下面程序的输出为？（ ）
#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {
if (n <= 1)
return n;
if (rec_fib[n] == 0)
rec_fib[n] = fib(n - 1) + fib(n - 2);
return rec_fib[n];
}
int main() {
cout << fib(6) << endl;
return 0;
} | A． 8 |
B． 13 |
| C． 64 |
D． 结果是随机的。 |
【知识点】 CCF—GESP C++七级
下面 search 函数的平均时间复杂度为？（ ）
int search(int n, int * p, int target) {
int low = 0, high = n;
while (low < high) {
int middle = (low + high) / 2;
if (target == p[middle]) {
return middle;
} else if (target > p[middle]) {
low = middle + 1;
} else {
high = middle;
}
}
return -1;
} | A． O(n log(n)) |
B． O(n) |
| C． O(long(n)) |
D． O(1) |
【知识点】 CCF—GESP C++七级
下面程序的时间复杂度为？（ ）
int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
for (int n = 2; n <= MAXN; n++) {
if (!isPrime[n])
primes[num++] = n;
for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
isPrime[n * primes[i]] = true;
if (n % primes[i] == 0)
break;
}
}
} | A． O(n) |
B． O(n×log n) |
| C． O(n×log log n) |
D．
|
【知识点】 CCF—GESP C++七级
二、判断题
三、编程题
线图
时间限制：1 s，内存限制：512 MB
【问题描述】
给定由 n 个结点与 m 条边构成的简单无向图 G，结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建：
（1）初始时线图 L(G) 为空。
（2）对于无向图 G 中的一条边，在线图 L(G) 中加入与之对应的一个结点。
（3）对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2)，若存在 G 中的结点同时连接这两条边（即 u1, v1之一与 u2, v2之一相同），则在线图 L(G) 中加入一条无向边，连接 (u1, v1)、(u2, v2) 在线图中对应的结点。
请你求出线图 L(G) 中所包含的无向边的数量。
【输入描述】
第一行，两个正整数 n、m，分别表示无向图 G 中的结点数与边数。
接下来 m 行，每行两个正整数 ui、vi，表示 G 中连接 ui、vi 的一条无向边。
【输出描述】
输出共一行，一个整数，表示线图 L(G) 中所包含的无向边的数量。
【样例输入1】
5 4 1 2 2 3 3 1 4 5
【样例输出1】
3
【样例输入2】
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
【样例输出2】
30
【样例解释1】
【数据范围】
对于60%测试点，保证 1 <= n、m <= 500。
对于所有测试点，保证 1 <= n、m <= 100000。
【知识点】 CCF—GESP C++七级
调味平衡
时间限制：1 s，内存限制：512 MB
【问题描述】
小 A 准备了 n 种食材用来制作料理，这些食材依次以 1、2、……、n 编号，第 i 种食材的酸度为 ai，甜度为 bi。
对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度 A 为放入食材的酸度之和，甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等，那么料理的调味是平衡的。
过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。
你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？
【输入描述】
第一行，一个正整数 n，表示食材种类数量。
接下来 n 行，每行两个正整数 ai、bi，表示食材的酸度与甜度。
【输出描述】
输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。
【样例输入1】
3 1 2 2 4 3 2
【样例输出1】
8
【样例输入2】
5 1 1 2 3 6 1 8 2 5 7
【样例输出2】
2
【数据范围】
对于40%的测试点，保证 1 <= n <= 10，1 <= ai、bi <= 10。
对于另外20%的测试点，保证 1 <= n <= 50，1 <= ai、bi <= 10。
对于所有测试点，保证 1 <= n <= 100，1 <= ai、bi <= 500。
【知识点】 CCF—GESP C++七级
