2024年3月CCF—GESP（C++七级）编程能力等级认证试卷
七级
2024
2024-04-17 15:51:50
64次
一、单选题
下面 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 - 1;
}
}
return -1;
} | A． O(n) |
B． O(log(n)) |
| C． O(1) |
D． 可能无法返回 |
【知识点】 CCF—GESP C++七级
下面的程序属于哪种算法( )。
int pos[8];
void queen(int n) {
for (int i = 0; i < 8; i++) {
pos[n] = i;
bool attacked = false;
for (int j = 0; j < n; j++)
if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j]- j) {
attacked = true;
break;
}
if (attacked)
continue;
if (n == 7) {
return;
} else {
queen(n + 1);
}
}
} | A． 贪心算法 |
B． 动态规划 |
| C． 深度优先搜索 |
D． 广度优先搜索 |
【知识点】 CCF—GESP C++七级
下面 schedule 函数的时间复杂度为( )。
#include <algorithm>
using namespace std;
struct activity {
int id, start, end;
};
bool compare(activity a, activity b) {
return a.end < b.end;
}
int schedule(int n, activity * p) {
sort(p, p + n, compare);
int cnt = 0, end = 0;
for (int i = 0; i < n; i++) {
if (p[i].start >= end) {
end = p[i].end;
cnt++;
}
}
return cnt;
} | A． O(n) |
B． O(log(n)) |
| C． O(nlog(n)) |
D． O(n2) |
【知识点】 CCF—GESP C++七级
下面 count_triple 函数的时间复杂度为( )。
nt count_triple(int n) {
int cnt = 0;
for (int a = 1; a <= n; a++)
for (int b = a; a + b <= n; b++)
for (int c = b; a + b + c <= n; c++)
if (a * a + b * b == c * c)
cnt++;
return cnt;
} | A． O(N) |
B． O(N2) |
| C． O(N3) |
D． O(N4) |
【知识点】 CCF—GESP C++七级
二、判断题
三、编程题
交流问题
问题描述
来自2所学校A校、B校的N名同学相聚在一起相互交流，方便起见，我们把这些同学从1至N编号。他们共进行了M次交流，第i次交流中，编号为ui,vi的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流，同校同学并不会相互交流。
作为 A 校顾问，你对 B 校的规模非常感兴趣，你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数N,M，表示同学的人数，交流的次数。
接下来M行，每行两个正整数ui,vi，表示一次交流。
题目保证输入合法，即交流一定是跨校开展的。
输出描述
输出一行两个整数，用单个空格隔开，分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4 3 1 2 2 3 4 2
样例输出 1
1 3
样例输入 2
7 5 1 2 2 3 4 2 5 6 6 7
样例输出 2
2 5
数据规模
对于30的测试点，保证N≤17，M≤50；
对于60的测试点，保证N≤500，M≤2000；
对于100的测试点，保证N≤105，M≤2×105。
【知识点】 CCF—GESP C++七级
俄罗斯方块
题面描述
小杨同学用不同种类的俄罗斯方块填满了一个大小为n×m的网格图。
网格图由n×m个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。
例如，在如下情况中，方块1和方块2是同一种俄罗斯方块，而方块1和方块3不是同一种俄罗斯方块。
输入格式
第一行包含两个正整数n,m，表示网格图的大小。
对于之后n行，第i行包含m个正整数ai1,ai2,...,aim,表示该行m个方块的颜色。
输出格式
输出一个非负整数，表示俄罗斯方块的种类数。
样例输入
5 6 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 6 6 7 7 8 6 6 7 7 8 8
样例输出
7
样例解释
数据范围
【知识点】 CCF—GESP C++七级
