2025年3月CCF—GESP（C++五级）编程能力等级认证试卷
五级
2025
2026-03-27 18:29:56
97次
一、单选题
对下面两个函数，说法【错误】的是？（ ）
int factorialA(int n) {
if (n <= 1) return 1;
return n * factorialA(n - 1);
}
int factorialB(int n) {
if (n <= 1) return 1;
int res = 1;
for(int i=2; i<=n; i++)
res *= i;
} | A． 两个函数的实现的功能相同。 |
B． 两个函数的时间复杂度均为 O(n)。 |
| C． factorialA采用递归方式。 |
D． factorialB采用递归方式。 |
【知识点】 CCF—GESP C++五级
函数 int findMax(int arr[], int low, int high) 计算数组中最大元素，其中数组 arr 从索引low 到 high ，（ ）正确实现了分治逻辑？
A．if (low == high) return arr[low]; int mid = (low + high) / 2; return arr[mid]; |
B．if (low >= high) return arr[low]; int mid = (low + high) / 2; int leftMax = findMax(arr, low, mid - 1); int rightMax = findMax(arr, mid, high); return leftMax + rightMax; |
C．if (low > high) return 0; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return leftMax * rightMax; |
D．if (low == high) return arr[low]; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return (leftMax > rightMax) ? leftMax : rightMax; |
【知识点】 CCF—GESP C++五级
下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，横线上应填的最佳代码是？（ ）
vector<int> sieve_linear(int n) {
vector<bool> is_prime(n +1, true);
vector<int> primes;
if (n < 2) return primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n/2; i++) {
if (is_prime[i])
primes.push_back(i);
for (int j = 0; ___________________ ; j++) { // 在此处填入代码
is_prime[ i * primes[j] ] = false;
if (i % primes[j] == 0)
break;
}
}
for (int i = n/2 +1; i <= n; i++) {
if (is_prime[i])
primes.push_back(i);
}
return primes;
} | A． j < primes.size() |
B． i * primes[j] <= n |
| C． j < primes.size() && i * primes[j] <= n |
D． j <= n |
【知识点】 CCF—GESP C++五级
下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是？（ ）
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
_____________________ // 在此处填入代码
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
} | A． int mid = left + (right - left) / 2; |
B． int mid = left; |
| C． int mid = (left + right) / 2; |
D． int mid = right; |
【知识点】 CCF—GESP C++五级
假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail ，链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。
下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是？（ ）
// 链表结点
template <typename T>
struct ListNode {
T data;
ListNode* prev;
ListNode* next;
// 构造函数
explicit ListNode(const T& val = T())
: data(val), prev(nullptr), next(nullptr) {}
};
struct LinkedList {
ListNode<T>* head;
ListNode<T>* tail;
};
void InitLinkedList(LinkedList* list) {
list->head = new ListNode<T>;
list->tail = new ListNode<T>;
________________________________ // 在此处填入代码
}; | A． list->head->prev = list->head; list->tail->prev = list->head; |
B． list->head->next = list->tail; list->tail->prev = list->head; |
| C． list->head->next = list->tail; list->tail->next = list->head; |
D． list->head->next = list->tail; list->tail->next = nullptr; |
【知识点】 CCF—GESP C++五级
双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。
设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p ，则下述语句中【错误】的是？（ ）
| A． p->next->prev = p->next; p->prev->next = p->prev; delete p; |
B． p->prev->next = p->next; p->next->prev = p->prev; delete p; |
| C． p->next->prev = p->prev; p->next->prev->next = p->next; delete p; |
D． p->prev->next = p->next; p->prev->next->prev = p->prev; delete p; |
【知识点】 CCF—GESP C++五级
考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是？（ ）
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 基准值
int i = low - 1;
for (int j = low; j < high; j++) {
____________________ // 在此处填入代码
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
} A．if (arr[j] > pivot) {
i++;
swap(arr[i], arr[j]);
} |
B．if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
} |
C．if (arr[j] < pivot) {
swap(arr[i], arr[j]);
i++;
} |
D．if (arr[j] == pivot) {
i++;
swap(arr[i], arr[j]);
} |
【知识点】 CCF—GESP C++五级
小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为？（ ）
vector<int> multiply(vector<int>& a, vector<int>& b) {
int m = a.size(), n = b.size();
vector<int> c(m + n, 0);
// 逐位相乘，逆序存储
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c[i + j] += a[i] * b[j];
}
}
// 处理进位
int carry = 0;
for (int k = 0; k < c.size(); ++k) {
______________________ // 在此处填入代码
c[k] = temp % 10;
carry = temp / 10;
}
while (c.size() > 1 && c.back() == 0)
c.pop_back();
return c;
} | A． int temp = c[k]; |
B． int temp = c[k] + carry; |
| C． int temp = c[k] - carry; |
D． int temp = c[k] * carry; |
【知识点】 CCF—GESP C++五级
二、判断题
三、编程题
原根判断
时间限制：1 s，内存限制：512 MB
【问题描述】
小 A 知道，对于质数 p 而言，p 的原根 g 是满足以下条件的正整数：
其中 a mod p 表示 a 除以 p 的余数。
小 A 现在有一个整数 T，请你帮他判断 a 是不是 p 的原根。
【输入描述】
第一行，一个正整数 T，表示测试数据组数。
每组测试数据包含一行，两个正整数 a、p。
【输出描述】
对于每组测试数据，输出一行，如果 a 是 p 的原根则输出 Yes ，否则输出 No 。
【样例输入1】
3 3 998244353 5 998244353 7 998244353
【样例输出1】
Yes Yes No
【数据范围】
对于 40% 的测试点，保证 3<=p<=1000。
对于所有测试点，保证 1<=T<=20， 3<=p<=10^9，1<a<p ， p为质数。
对于所有测试点，保证 ，-100<= A(i,j) <=100 。
【知识点】 CCF—GESP C++五级
平均分配
时间限制：1 s，内存限制：512 MB
【问题描述】
小 A 有 2n 件物品，小 B 和小 C 想从小 A 手上买走这些物品。对于第 i 件物品，小 B 会以 bi 的价格购买，而小 C 会以 ci 的价格购买。
为了平均分配这 2n 件物品，小 A 决定小 B 和小 C 各自只能买走恰好 n 件物品。你能帮小 A 求出他卖出这 2n 件物品所能获得的最大收入吗？
【输入描述】
第一行，一个正整数 n。
第二行， 2n 个整数 b1、b2、……、b(2n)。
第三行， 2n 个整数 c1、c2、……、c(2n)。
【输出描述】
一行，一个整数，表示答案。
【样例输入1】
3 1 3 5 6 8 10 2 4 6 7 9 11
【样例输出1】
36
【样例输入2】
2 6 7 9 9 1 2 10 12
【样例输出2】
35
【数据范围】
对于 20% 的测试点，保证 1<=n<=8。
对于另外 20% 的测试点，保证 0<=bi<=1，0<=ci<=1 。
对于所有测试点，保证 0<=n<=10^5，0<=bi<=10^9 ，0<=ci<=10^9 。
【知识点】 CCF—GESP C++五级
