2024年6月CCF—GESP（C++五级）编程能力等级认证试卷
五级
2024
2025-05-15 16:09:36
37次
一、单选题
下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是( )。
#include <iostream>
using namespace std;
#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值，单位相同
int coins_used[N_COINS];
void find_coins(int money) {
for (int i = 0; i < N_COINS; i++) {
coins_used[i] = money / coins[i];
money = money % coins[i];
}
return;
}
int main() {
int money;
cin >> money; //输入要换算的金额
find_coins(money);
for (int i = 0; i < N_COINS; i++)
cout << coins_used[i] << endl;
return 0;
} | A． 枚举算法 |
B． 贪心算法 |
| C． 迭代算法 |
D． 递归算法 |
【知识点】 CCF—GESP C++五级
根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79，81，90，96 中查找数值82，和82比较的数组元素分别是（ ）。
int binary_search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 如果找不到目标元素，返回-1
} | A． 52, 61, 81, 90 |
B． 52, 79, 90, 81 |
| C． 39, 79, 90, 81 |
D． 39, 79, 90 |
【知识点】 CCF—GESP C++五级
小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。
void insert(dl_node *head, string my_song) {
p = new dl_node;
p->song = my_song;
p->prev = nullptr;
p->next = head;
if (head != nullptr) {
________________________________ // 在此处填入代码
}
head = p;
} | A． head->next->prev = p; |
B． head->next = p; |
| C． head->prev = p; |
D． 触发异常，不能对空指针进行操作。 |
【知识点】 CCF—GESP C++五级
要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。
//假设a和b均为正数，且a表示的数比b大
vector<int> minus(vector<int> a, vector<int> b) {
vector<int> c；
int len1 = a.size();
int len2 = b.size();
int i, t;
for (i = 0; i < len2; i++) {
if (a[i] < b[i]) { //借位
_____________ // 在此处填入代码
a[i] += 10;
}
t = a[i] - b[i];
c.push_back(t);
}
for (; i < len1; i++)
c.push_back(a[i]);
len3 = c.size();
while (c[len3 - 1] == 0) {//去除前导0
c.pop_back();
len3--;
}
return c;
} | A． a[i + 1]–; |
B． a[i]–; |
| C． b[i + 1]–; |
D． b[i]–; |
【知识点】 CCF—GESP C++五级
小杨采用如下双链表结构保存他喜欢的歌曲列表：
struct dl_node {
string song;
dl_node* next;
dl_node* prev;
};小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。
dl_node* search(dl_node* head, string my_song) {
dl_node* temp = head;
while (temp != nullptr) {
if (temp->song == my_song)
return temp;
temp = temp->next;
}
return nullptr;
} | A． O(1) |
B． O(n) |
| C． O(logn) |
D． O(n2) |
【知识点】 CCF—GESP C++五级
下面C++代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数fibo()属于( )。
int fibo(int n) {
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
int a = 1，b = 1, next;
for (int i = 3; i <= n; i++) {
next = a + b;
a = b;
b = next;
}
return next;
} | A． 枚举算法 |
B． 贪心算法 |
| C． 迭代算法 |
D． 递归算法 |
【知识点】 CCF—GESP C++五级
为了正确实现快速排序，下面横线上的代码应为（ ）。
void qsort(vector<int>& arr, int left, int right) {
int i, j, mid;
int pivot;
i = left;
j = right;
mid = (left + right) / 2; // 计算中间元素的索引
pivot = arr[mid]; // 选择中间元素作为基准值
do {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]); // 交换两个元素
i++; j--;
}
} ________________________________; // 在此处填入代码
if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
} | A． while (i <= mid) |
B． while (i < mid) |
| C． while (i < j) |
D． while (i <= j) |
【知识点】 CCF—GESP C++五级
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
________________________________ { // 在此处填入代码
is_prime[i * primes[j]] = 0;
if (i % primes[j] == 0)
break;
}
}
return primes;
} | A． or (int j = 0; j < primes.size() && i * primes[j] <= n; j++) |
B． for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++) |
| C． for (int j = 0; j <= n; j++) |
D． for (int j = 1; j <= sqrt(n); j++) |
【知识点】 CCF—GESP C++五级
二、判断题
三、编程题
黑白格
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数n,m,k，含义如题面所示。
之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。
输出格式
输出一个整数，代表至少包含k个黑色格子的最小子矩形包含格子的数量，如果不存在则输出0。
输入样例
4 5 5 00000 01111 00011 00011
输出样例
6
样例解释
对于样例1，假设(i,j) 代表第i 行第j列，至少包含5个黑色格子的最小子矩形的四个顶点为(2,4)，(2,5)，(4,4)，(4,5)，共包含6个格子。
数据范围
对于全部数据，保证有1≤n,m≤100,1≤k≤n×m。
【知识点】 CCF—GESP C++五级
小杨的幸运数字
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2×2×3 的质因子有2,3，恰好为两种不同的质因子，因此12是幸运数字，而30=2×3×5 的质因子有2,3,5，不符合要求，不为幸运数字。
小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数n，代表正整数个数。
之后n行，每行一个正整数。
输出格式
输出n行，对于每个正整数，如果是幸运数字，输出1，否则输出0。
输入样例
3 7 12 30
输出样例
0 1 0
样例解释
7的质因子有7，只有一种。
12的质因子有2,3，恰好有两种。
30的质因子有2,3,5，有三种。
数据范围
对于全部数据，保证有1≤n≤104，每个正整数ai满足2≤ai≤106。
【知识点】 CCF—GESP C++五级
