CCF编程能力等级认证GESP—C++6级—20240907

单选题（每题 2 分，共 30 分）

1、以下( )没有涉及 C++ 语言的面向对象特性支持。

A. C++ 中构造一个 class 或 struct
B. C++ 中调用 printf 函数
C. C++ 中调用用户定义的类成员函数
D. C++ 中构造来源于同一基类的多个派生类

正确答案：B

2、关于以下C++代码，( )行代码会引起编译错误。

#include <iostream>
using namespace std;
class Base {
private:int a;
protected:int b;
public:int c;Base() : a(1), b(2), c(3) {}
};
class Derived : public Base {
public:void show() {cout << a << endl; // Line 1cout << b << endl; // Line 2cout << c << endl; // Line 3} 
};

A. Line 1 
B. Line 2 
C. Line 3
D. 没有编译错误

正确答案：A

3、有6个元素，按照 6,5,4,3,2,1 的顺序进入栈S，下列( )的出栈序列是不能出现的( )。

A. 5,4,3,6,1,2 
B. 4,5,3,1,2,6 
C. 3,4,6,5,2,1 
D. 2,3,4,1,5,6

正确答案：C

4、采用如下代码实现检查输入的字符串括号是否匹配，横线上应填入的代码为( )。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool is_valid(string s) {stack<char> st;char top;for (char& ch : s) {if (ch == '(' || ch == '{' || ch == '[') {st.push(ch); // 左括号入栈 }else{if (st.empty())return false; ———————————————————————— // 在此处填入代码if ((ch == ')' && top != '(') ||(ch == '}' && top != '{') ||(ch == ']' && top != '[')) {return false;} }return st.empty(); 
}

A. top = st.top(); st.pop();
B. st.pop(); top = st.top();
C. st.pop(); top = st.front(); 
D. top = st.front(); st.pop();

正确答案：A

5、下面代码判断队列的第一个元素是否等于 ，并删除该元素，横向上应填写( )。

#include <iostream>
#include <queue>
using namespace std;
bool is_front_equal(std::queue<int>& q, int a) {bool is_equal = false;if (!q.empty()) {———————————————————————— // 在此处填入代码}return is_equal; 
}

A. is_equal = (q.front() == a);
B. is_equal = (q.front() == a); q.pop(); 
C. q.pop(); is_equal = (q.front() == a); 
D. q.pop(); is_equal = (q.top() == a);

正确答案：B

6、假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使用哈夫曼编码方 式对字母进行二进制编码，则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。

A. 4, 4, 1, 3, 2 
B. 3, 3, 2, 2, 2 
C. 3, 3, 1, 2, 1 
D. 4, 4, 1, 2, 2

正确答案：B

7、以下C++代码实现 位的格雷码，则横线上应填写( )。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 生成 n 位的格雷码
vector<string> generate_graycode(int n) {vector<string> graycode_list;if (n <= 0) {return graycode_list;}// 初始1位格雷码 graycode_list.push_back("0"); graycode_list.push_back("1");// 迭代生成 n 位的格雷码for (int i = 2; i <= n; i++) {int current_size = graycode_list.size();for (int j = current_size - 1; j >= 0; j--) {graycode_list.push_back("1" + graycode_list[j]);}for (int j = 0; j < current_size; j++) {———————————————————————— // 在此处填入代码 }}return graycode_list;
}

A. graycode_list.push_back("0" + graycode_list[j]); 
B. graycode_list[j] = "0" + graycode_list[j];
C. graycode_list.push_back("1" + graycode_list[j]); 
D. graycode_list[j] = "1" + graycode_list[j];

正确答案：B

8、给定一棵二叉树，其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG，则这棵树的正确后序遍历 结果是( )。

A. EDBGFCA 
B. EDGBFCA 
C. DEBGFCA 
D. DBEGFCA

正确答案：A

9、一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是( )。

A. 8, 18 
B. 10, 18 
C. 8, 19 
D. 10, 19

正确答案：C

10、二叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于二叉树的深度优先搜索实现的 深度计算函数中横线上应填写( )。

// 定义二叉树的结点结构 
struct tree_node {int val;tree_node* left;tree_node* right;tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 计算二叉树的深度
int max_depth(tree_node* root) {if (root == nullptr) {return 0; // 如果根结点为空，则深度为 0}int left_depth = max_depth(root->left);int right_depth = max_depth(root->right);________ //在此处填入代码
}

A. return left_depth + right_depth;
B. return max(left_depth, right_depth);
C. return max(left_depth, right_depth) + 1; 
D. return left_depth + right_depth + 1;

正确答案：C

11、上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现 的深度计算函数中横线上应填写( )。

#include <queue>
int max_depth_bfs(tree_node* root) {if (root == nullptr) {return 0; // 如果树为空，深度为 0}queue <tree_node*> q;q.push(root);int depth = 0;// 使用队列进行层序遍历 while (!q.empty()) {———————————————————————— // 在此处填入代码 for (int i = 0; i < level_size; ++i) {tree_node* node = q.front();q.pop();if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}} }return depth;
}

A. int level_size = q.size(); depth++;
B. int level_size = 2; depth++;
C. int level_size = q.size(); depth += level_size; 
D. int level_size = 2; depth += level_size;

正确答案：A

12、二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点 值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造一个对应的二叉搜索树，横线上应填写( ):

// 定义二叉树的结点结构 struct tree_node {int val;tree_node* left;tree_node* right;tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {if (root == nullptr) {return new tree_node(val);}———————————————————————— // 在此处填入代码 return root;
}
// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {tree_node* root = nullptr;for (int i = 0; i < size; ++i) {root = insert(root, arr[i]);}return root;
}

A
if (val < root->val)root->left = insert(root->left, val);
elseroot->right = insert(root->right, val);

B
if (val > root->val)root->left = insert(root->left, val);
elseroot->right = insert(root->right, val);```
```cpp
C
if (val < root->val)root->left = insert(root, val); 
elseroot->right = insert(root, val);```
```cpp
D
if (val > root->val)root->left = insert(root, val); 
elseroot->right = insert(root, val);```

正确答案：A

13、对上题中的二叉搜素树，当输入数组为[5,3,7,2,4,6,8]时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到 的输出是( )。

#include <iostream>
using namespace std;
// 遍历二叉搜索树，输出结点值
void traversal(tree_node* root) {if (root == nullptr) {return;}traversal(root->left);cout << root->val << " ";traversal(root->right);
}

A. 5 3 7 2 4 6 8
B. 2 3 4 5 6 7 8
C. 2 4 3 6 8 7 5
D. 2 4 3 5 6 7 8

正确答案：B

14、动态规划通常用于解决( )。

A. 无法分解的问题
B. 可以分解成相互依赖的子问题的问题 
C. 可以通过贪心算法解决的问题
D. 只能通过递归解决的问题

正确答案：B

15、 阅读以下用动态规划解决的0-1背包问题的函数，假设背包的容量w是10kg，假设输入4个物品的重量weights，分别为1,3,4,6(单位为kg)，每个物品对应的价值values分别为20,30,50,60，则函数的输出为( )。

#include <iostream>
#include <vector>
using namespace std;
// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (weights[i - 1] <= w) {dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);}else{dp[i][w] = dp[i - 1][w];} }}return dp[n][W];
}

A. 90 
B. 100 
C. 110 
D. 140

正确答案：C

判断题（每题 2 分，共 20 分）

1、C++、Python和JAVA等都是面向对象的编程语言。

正确答案：正确

2、在C++中，类的静态成员变量只能被该类对象的成员函数访问。

正确答案：错误

3、栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出 队操作的时间复杂度较低。

正确答案：错误

4、运行以下C++代码，屏幕将输出“derived class”。

#include <iostream>
using namespace std;
class base {
public:virtual void show() {cout << "base class" << endl;} 
};
class derived : public base {
public:void show() override {cout << "derived class" << endl;} 
};
int main() {base* b;derived d;b = &d;b->show();return 0; 
}

正确答案：正确

5、如下列代码所示的基类(base)及其派生类(derived)，则生成一个派生类的对象时，只调用派生类的构造 函数。

#include <iostream>
using namespace std;
class base {
public:base() {cout << "base constructor" << endl;}~base() {cout << "base destructor" << endl;} 
};
class derived : public base {public:derived() {cout << "derived constructor" << endl;}~derived() {cout << "derived destructor" << endl;}
};

正确答案：错误

6、哈夫曼编码本质上是一种贪心策略。

正确答案：正确

7、如果根结点的深度记为 ，则一棵恰有 个叶结点的二叉树的深度最少是 。

正确答案：正确

8、在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。

正确答案：错误

9、状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。

正确答案：正确

10、应用动态规划算法时，识别并存储重叠子问题的解是必须的。

正确答案：正确

编程题 (每题 25 分，共 50 分)

小杨和整数拆分

【问题描述】
小杨有一个正整数n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。 小杨请你编写程序计算出总和为n的完全平方数的最少数量。
【输入描述】
第一行包含一个正整数n，含义如题面所示。
【输出描述】
输出一个整数，代表总和为n的完全平方数的最少数量。
【样例输入 1】
18
【样例输出 1】
2

18 = 9 + 9 = 16 + 1 + 1， 其中最少需要2个完全平方数。

子任务编号	数据点占比	n
1	20%	<=20
2	40%	<=1000
3	40%	$<=10^5$

对于全部数据，保证有$1<=n<=10^5$。

算法学习

【问题描述】
小杨计划学习m种算法，为此他找了n道题目来帮助自己学习，每道题目至多学习一次。
小杨对于m种算法的初始掌握程度均为0。第i道题目有对应的知识点$a_i$，即学习第i道题目可以令小杨对第$a_i$种 算法的掌握程度提高$b_i$。小杨的学习目标是对m种算法的掌握程度均至少为k。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才
能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

【输入描述】
第一行三个正整数m,n,k，代表算法种类数，题目数和目标掌握程度。
第二行 个正整数$a_1,a_2,a_3,...,a_n$，代表每道题目的知识点。
第二行 个正整数$b_1,b_2,b_3,...,b_n$，代表每道题目提升的掌握程度。
【输出描述】
输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 -1。
【样例输入 1】
3 5 10
1 1 2 3 3
9 1 10 10 1
【样例输出 1】
4
【样例输入 2】
2 4 10
1 1 1 2
1 2 7 10
【样例输出 2】
-1
对于样例1，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。

子任务编号	数据点占比	m	n	$b_i$	k
1	30%	=2	<=9	<=10	<=10
2	30%	<=9	<=9	<=10	<=10
3	40%	$<=10^5$	$<=10^5$	$<=10^5$	$<=10^5$

对于全部数据，保证有$1<=m,n<=10^5,1<=b_i,k<=10^5,q<=a_i<=m$。