2024年03月CCF-GESP编程能力等级认证C++编程六级真题
一、单选题（每题 2 分，共 30 分）
第 1 题 在构建哈夫曼树时，每次应该选择（ ）合并。
A. 最小权值的节点
B. 最大权值的节点
C. 随机节点
D. 深度最深的节点
答案：A
第 2 题 面向对象的编程思想主要包括以下哪些原则（ ）？
A. 贪心、动态规划、回溯
B. 并发、并行、异步
C. 递归、循环、分治
D. 封装、继承、多态
答案：D
第 3 题 在队列中，元素的添加和删除是按照（ ）原则进行的。
A. 先进先出
B. 先进后出
C. 最小值先出
D. 随机进出
答案：A
第 4 题 给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 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©;
B. Circle c(5.0); getArea©;
C. Circle c = new Circle(5.0); c.getArea();
D. Circle c(5.0); c.getArea();
答案：D
第 5 题 以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。
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
答案：B
第 6 题 3 位格雷编码的正确顺序是（ ）。
A. 000, 001, 010, 011, 100, 101, 110, 111
B. 000, 001, 011, 010, 110, 111, 101, 100
C. 000, 010, 001, 011, 100, 110, 101, 111
D. 000, 010, 110, 100, 111, 101, 011, 001
答案：B
第 7 题 以下动态规划算法的含义与目的是（ ）。
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 中的最小元素
答案：C
第 8 题 阅读以下广度优先搜索的代码：
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
答案：C
第 9 题 给定一个空栈，执行以下操作序列： 操作序列： push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()最终栈中的元素是（ ）。
A. 1, 2
B. 1, 4, 5
C. 1, 2, 5
D. 1, 4
答案：D
第 10 题 一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。
A. 247
B. 248
C. 249
D. 250
答案：B
第 11 题 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。
A. 重叠子问题
B. 分治法
C. 贪心策略
D. 回溯算法
答案：A
第 12 题 若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。
A. D, E, B, F, C, A
B. E, D, B, F, C, A
C. D, E, B, C, F, A
D. E, D, B, C, F, A
答案：A
第 13 题 线性筛法与埃氏筛法相比的优势是（ ）。
A. 更容易实现
B. 更节省内存
C. 更快速
D. 更准确
答案：C
第 14 题 以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。
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;
答案：C
第 15 题 下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。
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;
答案：A
二、判断题（每题 2 分，共 20 分）
第 16 题 哈夫曼树是一种二叉树。
答案：正确
第 17 题 在动态规划中，状态转移方程的作用是定义状态之间的关系。
答案：正确
第 18 题 继承是将已有类的属性和方法引入新类的过程。
答案：正确
第 19 题 完全二叉树的任意一层都可以不满。
答案：错误
第 20 题 删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。
答案：错误
第 21 题 在宽度优先搜索中，通常使用队列来辅助实现。
答案：正确
第 22 题 哈夫曼编码的主要应用领域是有损数据压缩。
答案：错误
第 23 题 二叉搜索树的查找操作的时间复杂度是 O(N)。
答案：错误
第 24 题 栈的基本操作包括入栈（push）和出栈（pop）。
答案：正确
第 25 题 使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。
答案：错误
三、编程题（每题 25 分，共 50 分）
第 26 题 游戏
第 27 题 好斗的牛