2024年12月CCF—GESP（C++八级）编程能力等级认证试卷
八级
2024
2025-06-07 16:53:54
58次
一、单选题
下面最长公共子序列程序中，横线处应该填入的是（ ）。
#define MAX(A, B) (((A) > (B)) ? (A) : (B))
#define MIN(A, B) (((A) < (B)) ? (A) : (B))
int dp[MAX_L + 1][MAX_L + 1];
int LCS(char str1[], char str2[]) {
int len1 = strlen(str1);
int len2 = strlen(str2);
for (int i = 0; i < len1; i++)
for(int j = 0; j < len2; j++)
if (str1[i] == str2[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
else
________; // 在此处填入选项
return dp[len1][len2];
} | A． dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] |
B． dp[i + 1][j + 1] = MIN(dp[i][j + 1], dp[i + 1][j]) |
| C． dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j]) |
D． dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j]) + 1 |
【知识点】 CCF—GESP C++八级
下面程序的输出为（ ）。
#include <iostream>
using namespace std;
int main() {
int N = 15, cnt = 0;
for (int x = 0; x + x + x <= N; x++)
for (int y = x; x + y + y <= N; y++)
for (int z = y; x + y + z <= N; z++)
cnt++;
cout << cnt << endl;
return 0;
} | A． 174 |
B． 447 |
| C． 816 |
D． 4096 |
【知识点】 CCF—GESP C++八级
下列Dijkstra算法中，横线处应该填入的是（ ）。
typedef struct Edge {
int in, out; // 从下标in顶点到下标out顶点的边
int len; // 边长度
struct Edge * next;
} Edge;
// v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
void dijkstra(int v, Edge * graph[], int start, int * dis) {
const int MAX_DIS = 0x7fffff;
for (int i = 0; i < v; i++)
dis[i] = MAX_DIS;
dis[start] = 0;
int * visited = new int[v];
for (int i = 0; i < v; i++)
visited[i] = 0;
visited[start] = 1;
for (int t = 0; ; t++) {
int min = MAX_DIS, minv = -1;
for (int i = 0; i < v; i++) {
if (visited[i] == 0 && min > dis[i]) {
min = dis[i];
minv = i;
}
}
if (minv < 0)
break;
visited[minv] = 1;
for (Edge * e = graph[minv]; e != NULL; e = e->next) {
________; // 在此处填入选项
}
}
delete[] visited;
} A．if (dis[e->out] > e->len) dis[e->out] = e->len; |
B．if (dis[e->out] > min + e->len) dis[e->out] = min + e->len; |
C．if (dis[e->in] > e->len) dis[e->in] = e->len; |
D．if (dis[e->in] > min + e->len) dis[e->in] = min + e->len; |
【知识点】 CCF—GESP C++八级
在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为1，表示该位对应的数被选中，反之为0表示未选中。例如，从 0 - 5 这 6 个数中选出 3 个，则 0b111000 代表选中 3, 4, 5 三个数， 0b011001 代表选中 0, 3, 4 三个数。zuhe_next 函数按组合对应的整数由大到小的顺序，求出组合 c 的下一个组合。横线处可以填入的是（ ）。
int intlow2(int c) {
return ________; // 在此处填入选项
}
int zuhe_next_incur(int c, int n, int l) {
if (n == 1) return c;
if ((c & (1 << l)) == 0) {
int d = intlow2(c);
c = (c & ~d);
c = (c | (d >> 1));
} else {
c = (c & ~(1 << l));
c = zuhe_next_incur(c, n - 1, l + 1);
int d = intlow2(c);
c = (c | (d >> 1));
}
return c;
}
// 从n个数中选m个，当前组合为c
int zuhe_next(int c, int n, int m) {
return zuhe_next_incur(c, n, 0);
} | A． ((c - 1) ^ c) |
B． (((c - 1) ^ c) + 1) |
| C． (((c - 1) ^ c) >> 1) |
D． ((((c - 1) ^ c) + 1) >> 1) |
【知识点】 CCF—GESP C++八级
下面的快速排序程序中，两处横线处分别应填入的是（ ）。
void quick_sort(int a[], int n) {
if (n <= 1)
return;
int pivot = 0, l = 0, r = n - 1;
while (________) { // 在此处填入选项
while (r > pivot && a[r] >= a[pivot])
r--;
if (r > pivot) {
int temp = a[pivot];
a[pivot] = a[r];
a[r] = temp;
pivot = r;
}
while (l < pivot && a[l] <= a[pivot])
l++;
if (l < pivot) {
int temp = a[pivot];
a[pivot] = a[l];
a[l] = temp;
pivot = l;
}
}
quick_sort(a, pivot);
quick_sort(________); // 在此处填入选项
} | A． l < r a + pivot + 1, n - pivot - 1 |
B． l < r a + pivot + 1, n - pivot |
| C． l <= r a + pivot + 1, n - pivot - 1 |
D． l <= r a + pivot + 1, n - pivot |
【知识点】 CCF—GESP C++八级
二、判断题
三、编程题
排队
时间限制：1.0 s
内存限制：512.0 MB
题目描述
小杨所在班级共有 n 位同学，依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有 m 对这样的关系（ m 是一个非负整数）。当 m≥1 时，第 i 对关系 (1≤i≤m) 给出 ai,bi，表示排队时编号为 ai的同学需要排在编号为 bi的同学前面，并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对 109+7 取模的结果。
输入格式
第一行，两个整数 n,m，分别表示同学们的数量与关系数量。
接下来 m 行，每行两个整数 ai,bi，表示一对关系。
输出格式
一行，一个整数，表示答案对 109+7 取模的结果。
输入样例 1
4 2 1 3 2 4
输出样例 1
2
输入样例 2
3 0
输出样例 2
6
输入样例 3
3 2 1 2 2 1
输出样例 3
0
数据范围
对于 20% 的测试数据点，保证 1≤n≤8,0≤m≤10 。
对于另外 20% 的测试数据点，保证 1≤n≤103,0≤m≤1 。
对于所有测试数据点，保证 1≤n≤2×105,0≤m≤2×105。
【知识点】 CCF—GESP C++八级
树上移动
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有一棵包含 n 个节点的树，其中节点的编号从 1 到 n ，每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t 并从节点 s 出发移动到节点 t ，移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过 k 个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。
输入格式
第一行包含两个正整数 n,k，代表节点数量和至多经过的黑色节点数。
第二行包含 n 个正整数 a1,a2,...,an，代表节点颜色，如果 ai=0，代表节点颜色为白色，如果 ai=1，代表节点颜色为黑色。
之后 n−1 行，每行包含两个正整数 ui,vi，代表存在一条连接节点 ui和 vi的边。
输出格式
输出一个正整数，代表最多经过的节点数。
输入样例
5 1 0 0 1 1 1 1 2 2 3 2 5 1 4
输入样例
3
对于全部数据，保证有 1≤n≤1000,0≤k≤1000,0≤ai≤1。
【知识点】 CCF—GESP C++八级
