2024年12月CCF—GESP（C++六级）编程能力等级认证试卷
六级
2024
2025-06-03 12:18:26
102次
一、单选题
阅读以下代码，下面哪一项是正确的？
void processData() {
stack<int> s;
queue<int> q;
for (int i = 1; i <= 5; ++i) {
s.push(i);
q.push(i);
}
while (!s.empty()) {
cout << "Stack pop: " << s.top() << endl;
s.pop();
}
while (!q.empty()) {
cout << "Queue pop: " << q.front() << endl;
q.pop();
}
} | A． 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 5 4 3 2 1 。 |
B． 栈 s 的输出顺序是 5 4 3 2 1 ，队列 q 的输出顺序是 1 2 3 4 5 。 |
| C． 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 1 2 3 4 5 。 |
D． 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 1 2 3 4 5 ，程序不会正常执行。 |
【知识点】 CCF—GESP C++六级
以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。
#include <iostream>
using namespace std;
class MyClass {
public:
MyClass() {
cout << "Constructor called!" << endl;
}
void display() {
cout << "Display function called!" << endl;
}
};
int main() {
MyClass* obj = NULL;
obj->display();
return 0;
} | A． NULL 在C++中无法用于指针初始化，应使用 nullptr 。 |
B． obj 的定义应该是 MyClass obj; 而不是指针类型。 |
| C． obj->display() 语句存在空指针访问错误， obj 应该初始化为一个有效的对象。 |
D． obj->display() 语句会调用 display() 函数，但它没有输出任何内容。 |
【知识点】 CCF—GESP C++六级
阅读以下二叉树的广度优先搜索的代码，横线上应填写（ ）。
#include <queue>
void bfs(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
———————————————————————— // 在此处填入代码
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
} | A． TreeNode* node = q.top(); |
B． TreeNode* node = q.top(); q.pop(); |
| C． TreeNode* node = q.front(); |
D． TreeNode* node = q.front(); q.pop(); |
【知识点】 CCF—GESP C++六级
阅读以下二叉树的深度优先搜索算法，横线上应填写（ ）。
void dfs(TreeNode* root) {
if (root == nullptr)
return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
———————————————————————— // 在此处填入代码
cout << node->value << " ";
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
} | A． TreeNode* node = s.top(); |
B． TreeNode* node = s.top(); s.pop(); |
| C． TreeNode* node = s.front(); |
D． TreeNode* node = s.front(); s.pop(); |
【知识点】 CCF—GESP C++六级
根据下面二叉树和给定的代码，
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int val) {
cout << root->val << " ";
if (root == NULL || root->val == val) return root;
if (val < root->val)
return search(root->left, val);
else
return search(root->right, val);
}给定以下二叉搜索树，调用函数 search(root,7) 时，输出的结果是（ ）。
5 / \ 3 7 / \ / \ 2 4 6 8
| A． 5 3 7 |
B． 5 7 |
| C． 2 3 4 5 6 7 |
D． 8 7 |
【知识点】 CCF—GESP C++六级
二、判断题
在解决简单背包问题时，动态规划的状态转移方程如下：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
该方程表示：在考虑第 i 个物品时，当前背包容量为 w ，如果不放物品 i ，则最大价值是 dp[i-1][w] ；如果放入物品 i ，则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1] ，其中数组 weights 和 values 分别表示所有物品的重量和价值，数组下标从 0 开始。
| A．正确 | B．错误 |
【知识点】 CCF—GESP C++六级
下面代码构建的树一定是完全二叉树：
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
TreeNode* buildCompleteBinaryTree() {
TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};
root->left->right = new TreeNode{5};
root->right->left = new TreeNode{6};
return root;
} | A．正确 | B．错误 |
【知识点】 CCF—GESP C++六级
三、编程题
运送物资
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨管理着 m 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 0，B 市的坐标为 x ，运输站点的坐标为 p 且有 0<p<x，货车每次去 A 市运送物资的总行驶路程为 2p，去 B 市运送物资的总行驶路程为 2(x−p)。
对于第 i 个运输站点，其位置为 pi且至多作为 ci辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
输入格式
第一行包含三个正整数 n,m,x，代表运输站点数量，货车数量和两市距离。
之后 n 行，每行包含两个正整数 pi,ci，代表第 i 个运输站点的位置和最多容纳车辆数。
之后 m 行，每行包含两个正整数 ai,bi，代表第 i 辆货车每天需要向 A 市运送 ai次物资，向 B 市运送 bi次物资。
输出格式
输出一个正整数，代表所有货车每天的最短总行驶路程。
输入样例
3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000
输出样例
40186
样例解释
第 1 辆车的初始运输站点为站点 3，第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1，第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短，为 40186。
对于全部数据，保证有 1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证∑ci≥m。
【知识点】 CCF—GESP C++六级
树上游走
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为 1，对于节点 i ，其左儿子的编号为 2×i，右儿子的编号为 2×i+1。
小杨会从节点 s 开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：
第1种移动方式： 如果当前节点存在父亲节点，向上移动到当前节点的父亲节点，否则不移动；
第2种移动方式： 移动到当前节点的左儿子；
第3种移动方式： 移动到当前节点的右儿子。
小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 1012。
输入格式
第一行包含一个正整数 n,s，代表移动次数和初始节点编号。
第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串，代表每次移动的方式，其中 U 代表第1种移动方式，L 代表第2种移动方式，R代表第3种移动方式。
输出格式
输出一个正整数，代表最后所处的节点编号。
输入样例
3 2 URR
输出样例
7
样例解释
小杨的移动路线为 2-1-3-7。
对于全部数据，保证有 1≤n≤106,1≤s≤1012。
【知识点】 CCF—GESP C++六级
