2024年3月CCF—GESP（C++六级）编程能力等级认证试卷
六级
2024
2024-04-17 13:53:56
90次
一、单选题
下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。
ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
current->next = next;
prev = current;
current = next;
}
return prev;
} | A． current->next = next; 应该改为 current->next = prev; |
B． ListNode* next = current->next; 应该改为 ListNode* next = prev->next; |
| C． current != nullptr 应该改为 current->next != nullptr |
D． ListNode* prev = nullptr; 应该改为 ListNode* prev = head; |
【知识点】 CCF—GESP C++六级
以下动态规划算法的含义与目的是（ ）。
int function(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
} | A． 计算数组 nums 中的所有元素的和 |
B． 计算数组 nums 中相邻元素的最大和 |
| C． 计算数组 nums 中不相邻元素的最大和 |
D． 计算数组 nums 中的最小元素 |
【知识点】 CCF—GESP C++六级
阅读以下广度优先搜索的代码：
void bfs(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->val << " ";
if (current->left) {
q.push(current->left);
}
if (current->right) {
q.push(current->right);
}
}
}使用以上算法遍历以下这棵树，可能的输出是（ ）。
| A． 1 2 8 9 4 5 3 6 7 10 11 |
B． 1 2 3 4 5 6 7 8 9 10 11 |
| C． 1 2 3 8 9 6 4 5 7 10 11 |
D． 1 2 3 8 9 4 5 6 7 10 11 |
【知识点】 CCF—GESP C++六级
以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。
TreeNode* search(TreeNode* root, int target) {
if (root == NULL || root->val == target) {
return root;
}
if (_______________) {
return search(root->left, target);
} else {
return search(root->right, target);
}
} | A． target < root->left |
B． target < root->val |
| C． target > root->val |
D． target > root->left |
【知识点】 CCF—GESP C++六级
以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。
int gcd(int a, int b) {
while (b != 0) {
______________________
}
return a;
} | A． int temp = b; b = a / b; a = temp; |
B． int temp = a; a = b / a; b = temp; |
| C． int temp = b; b = a % b; a = temp; |
D． b = a % b; a = b; |
【知识点】 CCF—GESP C++六级
给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数？
class Circle {
private:
double radius;
public:
Circle(double r) : radius(r) {}
double getArea() {
return 3.14 * radius * radius;
}
}; | A． Circle c = Circle(5.0); c.getArea(c); |
B． Circle c(5.0); getArea(c); |
| C． Circle c = new Circle(5.0); c.getArea(); |
D． Circle c(5.0); c.getArea(); |
【知识点】 CCF—GESP C++六级
二、判断题
三、编程题
好斗的牛
问题描述
你有109个牛棚，从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第i头牛的攻击范围是(ai,bi)，这意味着，如果他的左边ai个牛棚或右边bi个牛棚里有其他牛，他就会去挑事。
你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里，且没有牛会挑事？
输入描述
第一行 1 个正整数N。
接下来一行N个用空格隔开的正整数a1,...,aN。
接下来一行 个用空格隔开的正整数b1,...,bN。
输出描述
输出一行一个整数，表示你最少需要留下多少牛棚。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
2 1 2 1 2
样例输出 1
4
样例解释 1
你可以留下 个牛棚，并如此安排你的牛：
样例输入 2
3 1 2 3 3 2 1
样例输出 2
7
数据规模
对于20的测试点，保证N=2；
对于另外20的测试点，保证N=3；
对于80的测试点，保证N≤8；
对于所有测试点，保证N≤9，ai,bi≤1000。
【知识点】 CCF—GESP C++六级
游戏
题面描述
你有四个正整数n,a,b,c，并准备用它们玩一个简单的小游戏。
在一轮游戏操作中，你可以选择将n减去a，或是将n减去b。游戏将会进行多轮操作，直到当n≤c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n减去a，而另一种操作序列选择将n减去b。如果a=b，也认为将n减去a与将n减去b是不同的操作。
由于答案可能很大，你只需要求出答案对1000000007取模的结果。
输入格式
一行四个正整数n,a,b,c。保证1≤a,b,c≤n。
输出格式
一行一个整数，表示不同的游戏操作序列数量对1000000007取模的结果。
样例输入1
1 1 1 1
样例输出1
1
样例输入2
114 51 4 1
样例输出2
176
样例输入3
114514 191 9 810
样例输出3
384178446
数据范围
对于20的测试点，保证a=b=c=1，n≤30。
对于40的测试点，保证c=1，n≤103。
对于所有测试点，保证1≤n≤2×105。
【知识点】 CCF—GESP C++六级
