GESP 2024年 9月认证 C++ 六级真题

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B A C A B B B A C C A A B B C C++　六级 2024 年 09 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 以下（ ）没有涉及 C++ 语⾔的⾯向对象特性⽀持。 A. C++ 中构造⼀个 class 或 struct B. C++ 中调⽤ printf 函数 C. C++ 中调⽤⽤户定义的类成员函数 D. C++ 中构造来源于同⼀基类的多个派⽣类 第 2 题 关于以下C++代码，（ ）⾏代码会引起编译错误。 A. Line 1 B. Line 2 C. Line 3 #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 1 cout << b << endl; // Line 2 cout << c << endl; // Line 3 } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 D. 没有编译错误 第 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 第 4 题 采⽤如下代码实现检查输⼊的字符串括号是否匹配，横线上应填⼊的代码为（ ）。 A. top = st.top(); st.pop(); B. st.pop(); top = st.top(); C. st.pop(); top = st.front(); D. top = st.front(); st.pop(); 第 5 题 下⾯代码判断队列的第⼀个元素是否等于 ，并删除该元素，横向上应填写（ ）。 #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(); // 栈为空则说明所有括号匹配成功 } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 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); 第 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 第 7 题 以下C++代码实现 位的格雷码，则横线上应填写（ ）。 #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; } 1 2 3 4 5 6 7 8 9 10 11 #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++) { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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]; 第 8 题 给定⼀棵⼆叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历 结果是（ ）。 A. EDBGFCA B. EDGBFCA C. DEBGFCA D. DBEGFCA 第 9 题 ⼀棵有 个结点的完全⼆叉树⽤数组进⾏存储与表⽰，已知根结点存储在数组的第 个位置。若存储在数组第 个位置的结点存在兄弟结点和两个⼦结点，则它的兄弟结点和右⼦结点的位置分别是（ ）。 A. 8, 18 B. 10, 18 C. 8, 19 D. 10, 19 第 10 题 ⼆叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于⼆叉树的深度优先搜索实现的 深度计算函数中横线上应填写（ ）。 ———————————————————————— // 在此处填入代码 } } return graycode_list; } 25 26 27 28 29 30 // 定义二叉树的结点结构 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); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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; 第 11 题 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。以下基于⼆叉树的⼴度优先搜索实现 的深度计算函数中横线上应填写（ ）。 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; 第 12 题 ⼆叉搜索树中的每个结点，其左⼦树的所有结点值都⼩于该结点值，右⼦树的所有结点值都⼤于该结点 值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造⼀个对应的⼆叉搜索树，横线上应填写（ ）: ———————————————————————— // 在此处填入代码 } 18 19 20 #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; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 A. B. C. D. // 定义二叉树的结点结构 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; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 if (val < root->val) root->left = insert(root->left, val); else root->right = insert(root->right, val); 1 2 3 4 if (val > root->val) root->left = insert(root->left, val); else root->right = insert(root->right, val); 1 2 3 4 if (val < root->val) root->left = insert(root, val); else root->right = insert(root, val); 1 2 3 4 第 13 题 对上题中的⼆叉搜素树，当输⼊数组为 时，构建⼆叉搜索树，并采⽤如下代码实现的遍历⽅式，得到 的输出是（ ）。 A. B. C. D. 第 14 题 动态规划通常⽤于解决（ ）。 A. ⽆法分解的问题 B. 可以分解成相互依赖的⼦问题的问题 C. 可以通过贪⼼算法解决的问题 D. 只能通过递归解决的问题 第 15 题 阅读以下⽤动态规划解决的0-1背包问题的函数，假设背包的容量 是10kg，假设输⼊4个物品的重量 分别为 （单位为kg），每个物品对应的价值 分别为 ，则函数的输出为（ ）。 if (val > root->val) root->left = insert(root, val); else root->right = insert(root, val); 1 2 3 4 #include <iostream> using namespace std; // 遍历二叉搜索树，输出结点值 void traversal(tree_node* root) { if (root == nullptr) { return; } traversal(root->left); cout << root->val << " "; traversal(root->right); } 1 2 3 4 5 6 7 8 9 10 11 12 13 #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) { 1 2 3 4 5 6 7 8 9 10 11 题号 1 2 3 4 5 6 7 8 9 10 答案 A. 90 B. 100 C. 110 D. 140 2 判断题（每题 2 分，共 20 分） 第 1 题 C++、Python和JAVA等都是⾯向对象的编程语⾔。 第 2 题 在C++中，类的静态成员变量只能被该类对象的成员函数访问。 第 3 题 栈是⼀种线性结构，可通过数组或链表来实现。⼆者相⽐，数组实现占⽤的内存较少，链表实现的⼊队和出 队操作的时间复杂度较低。 第 4 题 运⾏以下C++代码，屏幕将输出“derived class”。 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]; } 12 13 14 15 16 17 18 19 20 21 22 #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; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 第 5 题 如下列代码所⽰的基类（base）及其派⽣类（derived），则⽣成⼀个派⽣类的对象时，只调⽤派⽣类的构造 函数。 第 6 题 哈夫曼编码本质上是⼀种贪⼼策略。 第 7 题 如果根结点的深度记为 ，则⼀棵恰有 个叶结点的⼆叉树的深度最少是 。 第 8 题 在⾮递归实现的树的⼴度优先搜索中，通常使⽤栈来辅助实现。 第 9 题 状态转移⽅程是动态规划的核⼼，可以通过递推⽅式表⽰问题状态的变化。 第 10 题 应⽤动态规划算法时，识别并存储重叠⼦问题的解是必须的。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：⼩杨和整数拆分 时间限制：1.0 s 内存限制：512.0 MB 3.1.1 题面描述 ⼩杨有⼀个正整数 ，⼩杨想将它拆分成若⼲完全平⽅数的和，同时⼩杨希望拆分的数量越少越好。 ⼩杨请你编写程序计算出总和为 的完全平⽅数的最少数量。 b->show(); return 0; } 22 23 24 #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; } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 子任务编号 数据点占比 1 20% 2 40% 3 40% 3.1.2 输入格式 第⼀⾏包含⼀个正整数 ，含义如题⾯所⽰。 3.1.3 输出格式 输出⼀个整数，代表总和为 的完全平⽅数的最少数量。 3.1.4 样例1 ，其中最少需要 个完全平⽅数。 对于全部数据，保证有 。 3.1.5 参考程序 3.2 编程题 2 试题名称：算法学习 时间限制：1.0 s 内存限制：512.0 MB 3.2.1 题面描述 ⼩杨计划学习 种算法，为此他找了 道题⽬来帮助⾃⼰学习，每道题⽬⾄多学习⼀次。 ⼩杨对于 种算法的初始掌握程度均为 。第 道题⽬有对应的知识点 ，即学习第 道题⽬可以令⼩杨对第 种 算法的掌握程度提⾼ 。⼩杨的学习⽬标是对 种算法的掌握程度均⾄少为 。 181 21 #include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int n; int dp[N]; int main(){ cin>>n; for(int i=1;i<=n;i++){ dp[i]=i; for(int j=1;j<=sqrt(i);j++){ dp[i] =min(dp[i-j*j]+1,dp[i]); } } cout<<dp[n]<<" "; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 子任务编号 数据点占比 1 30% 2 30% 3 40% ⼩杨认为连续学习两道相同知识点的题⽬是不好的，⼩杨想请你编写程序帮他计算出他最少需要学习多少道题⽬才 能使得他在完成学习⽬标的同时避免连续学习两道相同知识点的题⽬。 3.2.2 输入格式 第⼀⾏三个正整数 ，代表算法种类数，题⽬数和⽬标掌握程度。 第⼆⾏ 个正整数 ，代表每道题⽬的知识点。 第⼆⾏ 个正整数 ，代表每道题⽬提升的掌握程度。 3.2.3 输出格式 输出⼀个整数，代表⼩杨最少需要学习题⽬的数量，如果不存在满⾜条件的⽅案，输出 -1。 3.2.4 样例1 3.2.5 样例2 对于样例1，⼀种最优学习顺序为第⼀道题，第三道题，第四道题，第⼆道题。 对于全部数据，保证有 。 3.2.6 参考程序 3 5 10 1 1 2 3 3 9 1 10 10 1 1 2 3 41 2 4 10 1 1 1 2 1 2 7 10 1 2 3 -11 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int inf = 0x3f3f3f3f; int f[N]; vector<int> score[N + 2], a, b; bool cmp(int i, int j) { return i > j; } int main() { int n, m, k; cin >> m >> n >> k; a.resize(n), b.resize(n); 1 2 3 4 5 6 7 8 9 10 11 12 13 for (int i = 0; i < n; i ++) cin >> a[i]; for (int i = 0; i < n; i ++) { cin >> b[i]; score[a[i]].emplace_back(b[i]); } vector<int> need(m + 2); int ans = 0, mx_meed = 0, mx_need_i = -1; for (int i = 1; i <= m; i ++) { sort(score[i].begin(), score[i].end(), cmp); int sum = 0; for (int j = 0; j < (int) score[i].size(); j ++) { sum += score[i][j]; if (sum >= k) { need[i] = j + 1; break ; } } if (sum < k) { puts("-1"); return 0; } ans += need[i]; if (need[i] > mx_meed) mx_meed = need[i], mx_need_i = i; } if (mx_meed - 1 <= ans - mx_meed) { cout << ans << endl; return 0; } int last = 0; for (int i = 1; i <= m; i ++) if (i != mx_need_i) last += score[i].size() - need[i]; cout << (mx_meed - 1 <= ans - mx_meed + last ? 2 * mx_meed - 1 : -1) << endl; return 0; } 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51