2024年9月CCF—GESP（C++五级）编程能力等级认证试卷
五级
2024
2025-05-29 09:21:07
76次
一、单选题
考虑以下C++代码实现的归并排序算法：
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}对长度为 n 的数组 arr ，挑用函数 merge_sort(a, 0, n-1) ，在排序过程中 merge 函数的递归调用次数大约是（ ）。
| A． O(1) |
B． O(n) |
| C． O(logn) |
D． O(nlogn) |
【知识点】 CCF—GESP C++五级
根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79 中查找数值 31 ，循环while (left <= right) 执行的次数为（ ）。
int binary_search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1; // 如果找不到目标元素，返回-1
}| A． 1 |
B． 2 |
| C． 3 |
D． 4 |
【知识点】 CCF—GESP C++五级
下面函数可以将 n 的所有质因数找出来，其时间复杂度是（ ）。
#include <iostream>
#include <vector>
vector<int> get_prime_factors(int n) {
vector<int> factors;
while (n % 2 == 0) {
factors.push_back(2);
n /= 2;
}
for (int i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
if (n > 2) {
factors.push_back(n);
}
return factors;
}| A． O(n2) |
B． O(nlogn) |
| C． |
D． O(n) |
【知识点】 CCF—GESP C++五级
下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是( )。
vector<int> sieve_linear(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i <= n / 2; i++) {
if (is_prime[i])
primes.push_back(i);
________________________________ { // 在此处填入代码
is_prime[i * primes[j]] = 0;
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． for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) |
B． for (int j = 1; j < primes.size() && i * j <= n; j++) |
| C． for (int j = 2; j < primes.size() && i * primes[j] <= n; j++) |
D． 以上都不对 |
【知识点】 CCF—GESP C++五级
下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是( )。
void sieve_Eratosthenes(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
________________________________ { // 在此处填入代码
is_prime[j] = false;
}
}
}
for (int i = sqrt(n) + 1; i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
}
}
return primes;
}| A． for (int j = i; j <= n; j++) |
B． for (int j = i * i; j <= n; j++) |
| C． for (int j = i * i; j <= n; j += i) |
D． for (int j = i; j <= n; j += i) |
【知识点】 CCF—GESP C++五级
对下面两个函数，说法错误的是（ ）。
int sumA(int n) {
int res = 0;
for (int i = 1; i <= n; i++) {
res += i;
}
return res;
}
int sumB(int n) {
if (n == 1)
return 1;
int res = n + sumB(n - 1);
return res;
}| A． sumA体现了迭代的思想。 |
B． SumB采用的是递归方式。 |
| C． SumB函数比SumA的时间效率更高。 |
D． 两个函数的实现的功能相同。 |
【知识点】 CCF—GESP C++五级
通过（ ）操作，能完成在双向循环链表结点 p 之后插入结点 s 的功能（其中 next 域为结点的直接后继，prev 域为结点的直接前驱）。
| A． p->next->prev = s; s->prev = p; p->next = s; s->next = p->next; |
B． p->next->prev = s; p->next = s; s->prev = p; s->next = p->next; |
| C． s->prev = p; s->next = p->next; p->next = s; p->next->prev = s; |
D． s->next = p->next; p->next->prev = s; s->prev = p; p->next = s; |
【知识点】 CCF—GESP C++五级
现在有 n 个人要过河，每只船最多载2人，船的承重为100kg。下列代码中，数组 weight 中保存有 n 个人的体重（单位为kg），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（ ）。
int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
if (weight[i] + weight[j] <= 100) {
i++;
}
count++;
}
printf("过河的船数：%d\n", count);| A． 枚举算法 |
B． 贪心算法 |
| C． 迭代算法 |
D． 递归算法 |
【知识点】 CCF—GESP C++五级
二、判断题
三、编程题
小杨的武器
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有 n 种不同的武器，他对第 i ii 种武器的初始熟练度为ci。
小杨会依次参加 m 场战斗，每场战斗小杨只能且必须选择一种武器使用，假设小杨使用了第 i 种武器参加了第 j 场战斗，战斗前该武器的熟练度为ci′，则战斗后小杨对该武器的熟练度会变为 ci′+aj。需要注意的是，aj可能是正数，0 或负数，这意味着小杨参加战斗后对武器的熟练度可能会提高，也可能会不变，还有可能降低。
小杨想请你编写程序帮他计算出如何选择武器才能使得 m 场战斗后，自己对 n 种武器的熟练度的最大值尽可能大。
输入格式
第一行包含两个正整数 n,m，含义如题面所示。
第二行包含 n 个正整数 c1,c2,...,cn，代表小杨对武器的初始熟练度。
第三行包含 m 个正整数 a1,a2,...,am，代表每场战斗后武器熟练度的变化值。
输出格式
输出一个整数，代表 m 场战斗后小杨对 n 种武器的熟练度的最大值最大是多少。
输入样例
2 2 9 9 1 -1
输出样例
10
一种最优的选择方案为，第一场战斗小杨选择第一种武器，第二场战斗小杨选择第二种武器。
对于全部数据，保证有 1≤n,m≤105,−104≤ci,ai≤104。
【知识点】 CCF—GESP C++五级
挑战怪物
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨正在和一个怪物战斗，怪物的血量为 h ，只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
物理攻击。假设当前为小杨第 i 次使用物理攻击，则会对怪物造成 2i−1点伤害。
魔法攻击。小杨选择任意一个质数 x （x 不能超过怪物当前血量），对怪物造成 x 点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
输入格式
第一行包含一个正整数 t ，代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例，第一行包含一个正整数 h ，代表怪物血量。
输出格式
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，输出−1。
输入样例
3 6 188 9999
输出样例
2 4 -1
对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 5 造成 5 点伤害，之后对怪物使用第 1 次物理攻击，造成21−1=1 点伤害，怪物血量恰好为 0 ，小杨成功击败怪物。
对于全部数据，保证有 1≤t≤10,1≤h≤105。
【知识点】 CCF—GESP C++五级
