2024年9月GESP编程能力认证C++等级考试六级真题(含答案和解析-在末尾)

2024年9月GESP编程能力认证C++等级考试六级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.以下（）没有涉及C++语言的面向对象特性支持。A.C++中构造一个class或structB.C++中调用printf函数C.C++中调用用户定义的类成员函数D.C++中构造来源于同一基类的多个派生类2.关于以下C++代码，（）行代码会引起编译错误。#include<iostream>usingnamespacestd;classBase{private:inta;protected:intb;public:intc;Base():a(1),b(2),c(3){}};classDerived:publicBase{public:voidshow(){cout<<a<<endl;//Line1。cout<<b<<endl;//Line2。cout<<c<<endl;//Line3。}};A.Line1B.Line2C.Line3D.没有编译错误3.有6个元素，按照6,5,4,3,2,1的顺序进入栈S，下列（）的出栈序列是不能出现的（）。4.采用如下代码实现检查输入的字符串括号是否匹配，横线上应填入的代码为（）。5.下面代码判断队列的第一个元素是否等于，并删除该元素，横向上应填写（）。#include<iostream>#include<queue>usingnamespacestd;boolis_front_equal(std::queue<int>&q,inta){boolis_equal=false;if(!q.empty()){________________________//在此处填入代码。}returnis_equal;}6.假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符abcdef分别对应的一组哈夫曼编码的长度分别为（）。7.以下C++代码实现n位的格雷码，则横线上应填写（）。#include<iostream>#include<vector>#include<string>usingnamespacestd;//生成n位的格雷码。vector<string>generate_graycode(intn){vector<string>graycode_list;if(n<=0){returngraycode_list;}//初始1位格雷码。graycode_list.push_back("0");graycode_list.push_back("1");//迭代生成n位的格雷码。for(inti=2;i<=n;i++){intcurrent_size=graycode_list.size();for(intj=current_size-1;j>=0;j--){graycode_list.push_back("1"+graycode_list[j]);}for(intj=0;j<current_size;j++){________________________//在此处填入代码。}}returngraycode_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];8.给定一棵二叉树，其前序遍历结果为ABDECFG,中序遍历结果为DEBACFG，则这棵树的正确后序遍历结果是（）。A.EDBGFCAB.EDGBFCAC.DEBGFCAD.DBEGFCA9.一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。10.二叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写（）。//定义二叉树的结点结构。structtree_node{intval;tree_node*left;tree_node*right;tree_node(intx):val(x),left(nullptr),right(nullptr){}};//计算二叉树的深度。intmax_depth(tree_node*root){if(root==nullptr){return0;//如果根结点为空，则深度为0。}intleft_depth=max_depth(root->left);intright_depth=max_depth(root->right);________________________//在此处填入代码。}A.returnleft_depth+right_depth;B.returnmax(left_depth,right_depth);C.returnmax(left_depth,right_depth)+1;D.returnleft_depth+right_depth+1;11.上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写（）。#include<queue>intmax_depth_bfs(tree_node*root){if(root==nullptr){return0;//如果树为空，深度为0。}queue<tree_node*>q;q.push(root);intdepth=0;//使用队列进行层序遍历。while(!q.empty()){________________________//在此处填入代码。for(inti=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);}}}returndepth;}A.intlevel_size=q.size();depth++;B.intlevel_size=2;depth++;C.intlevel_size=q.size();depth+=level_size;D.intlevel_size=2;depth+=level_size;12.二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造一个对应的二叉搜索树，横线上应填写（）。//定义二叉树的结点结构。structtree_node{intval;tree_node*left;tree_node*right;tree_node(intx):val(x),left(nullptr),right(nullptr){}};//插入结点到二叉搜索树中。tree_node*insert(tree_node*root,intval){if(root==nullptr){returnnewtree_node(val);}________________________//在此处填入代码。returnroot;}//根据给定数组构造二叉搜索树。tree_node*constructBST(constintarr[],intsize){tree_node*root=nullptr;for(inti=0;i<size;++i){root=insert(root,arr[i]);}returnroot;}A.B.C.D.13.对上题中的二叉搜素树，当输入数组为[5,3,7,2,4,6,8]时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到的输出是（）。#include<iostream>usingnamespacestd;//遍历二叉搜索树，输出结点值。voidtraversal(tree_node*root){if(root==nullptr){return;}traversal(root->left);cout<<root->val<<"";traversal(root->right);}A.B.C.D.14.动态规划通常用于解决（）。A.无法分解的问题B.可以分解成相互依赖的子问题的问题C.可以通过贪心算法解决的问题D.只能通过递归解决的问题15.阅读以下用动态规划解决的0-1背包问题的函数，假设背包的容量W是10kg，假设输入4个物品的重量weights分别为1,3,4,6（单位为kg），每个物品对应的价值values分别为20,30,50,60，则函数的输出为（）。#include<iostream>#include<vector>usingnamespacestd;//0/1背包问题。intknapsack(intW,constvector<int>&weights,constvector<int>&values,intn){vector<vector<int>>dp(n+1,vector<int>(W+1,0));for(inti=1;i<=n;++i){for(intw=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];}}}returndp[n][W];}A.90B.100C.110D.140二、判断题（每题2分，共20分）。16.题C++、Python和JAVA等都是面向对象的编程语言（）。A.正确B.错误17.在C++中，类的静态成员变量只能被该类对象的成员函数访问（）。A.正确B.错误18.栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低（）。A.正确B.错误19.运行以下C++代码，屏幕将输出“derivedclass”。（）。A.正确B.错误20.如下列代码所示的基类（base）及其派生类（derived），则生成一个派生类的对象时，只调用派生类的构造函数（）。#include<iostream>usingnamespacestd;classbase{public:base(){cout<<"baseconstructor"<<endl;}~base(){cout<<"basedestructor"<<endl;}};classderived:publicbase{public:derived(){cout<<"derivedconstructor"<<endl;}~derived(){cout<<"deriveddestructor"<<endl;}};A.正确B.错误21.哈夫曼编码本质上是一种贪心策略（）。A.正确B.错误22.如果根结点的深度记为1，则一棵恰有2024个叶结点的二叉树的深度最少是12。（）。A.正确B.错误23.在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现（）。A.正确B.错误24.状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化（）。A.正确B.错误25.应用动态规划算法时，识别并存储重叠子问题的解是必须的（）。A.正确B.错误三、编程题（每题25分，共50分）。26.小杨和整数拆分。时间限制：1.0s。内存限制：512.0MB。题面描述：小杨有一个正整数n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。小杨请你编写程序计算出总和为n的完全平方数的最少数量。输入格式：第一行包含一个正整数n，含义如题面所示。输出格式：输出一个整数，代表总和为n的完全平方数的最少数量。样例1。18=9+9=16+1+1，其中最少需要2个完全平方数。对于全部数据，保证有1≤n≤105。27.算法学习。时间限制：1.0s。内存限制：512.0MB。题面描述：小杨计划学习m种算法，为此他找了n道题目来帮助自己学习，每道题目至多学习一次。小杨对于m种算法的初始掌握程度均为0。第i道题目有对应的知识点ai，即学习第i道题目可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习目标是对m种算法的掌握程度均至少为k。小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。输入格式：第一行三个正整数m,n,k，代表算法种类数，题目数和目标掌握程度。第二行a1,a2,a3,…,an个正整数，代表每道题目的知识点。第二行n个正整数b1,b2,b3,…,bn，代表每道题目提升的掌握程度。输出格式：输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出-1。样例1。样例2。对于样例1，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。对于全部数据，保证有1≤m,n≤105,1≤bi,k≤105,1≤ai≤m。答案如下。1.答案：B。解析：C++的面向对象特性主要包括类(class)与结构体(struct)的定义、继承(inheritance)、封装(encapsulation)以及多态(polymorphism)等。A项构造一个class或struct，这是面向对象编程的基本组成部分之一，它允许开发者定义自己的数据类型，这些类型可以包含数据成员和成员函数。因此，这显然涉及到C++的面向对象特性。B项调用printf函数，并不是面向对象特性的体现。printf是一个标准库函数，用于格式化输出到标准输出设备（如屏幕）。它并不属于任何类的一部分，也不涉及到类、继承或多态的概念。C项调用用户定义的类成员函数，这与面向对象编程密切相关，因为成员函数是类的一部分，用于操作类的数据成员或者实现类的行为。D项构造来源于同一基类的多个派生类，这是继承的一个典型例子，是面向对象编程中的一个重要特性，允许创建新的类来重用现有类的代码。因此，选项B，C++中调用printf函数，没有涉及C++语言的面向对象特性支持。2.答案：A。解析：这段代码中定义了两个类，Base和从Base继承的Derived。在Derived类中有一个show()成员函数，试图输出基类中定义的a,b,和c的值。根据C++的访问规则。私有(private)成员只能由声明它的类的成员函数访问。保护(protected)成员可以被该类及其派生类的成员函数访问。公有(public)成员可以被任何地方访问。具体来看。a是Base类中的私有成员，所以不能在派生类Derived中直接访问。b是Base类中的保护成员，所以在派生类Derived中是可以访问的。c是Base类中的公有成员，自然也是可以被派生类Derived访问的。根据上述分析，Line1会尝试访问Base类中的私有成员a，这会导致编译错误。因此，正确答案是A.Line1。3.答案：C。解析：模拟C，6，5，4，3进，3出，4出，5没出6是不能出的。选C。4.答案：A。解析：括号匹配问题，若是碰到左括号则入栈，碰到右括号要拿出左括号与之对比，若栈中没有左括号则配对失败，若左括号与之不匹配则配对失败，否则继续配对，最终返回栈是否为空，为空则匹配成功，否则匹配失败，这里询问的是拿出栈中首元素后删除的操作，选A是top=st.top;st.pop;front一般是队列中取出队头的操作。5.答案：B。解析：完美衔接上一题，取出队头是q.front(),去掉队头上q.pop(),所以选B。6.答案：B。解析：求哈夫曼编码需要先构建哈夫曼树。构建方法：①从频率表中取出最小的两个元素，构建出新元素，②将新元加入到频率表中，图示如下图片。所以很明显abcdef分别对应的一组哈夫曼编码长度为33222。7.答案：B。解析：格雷码（Graycode）是一种相邻两个代码之间只有单个比特不同的二进制数字系统。要生成n位的格雷码，可以通过迭代的方式生成更长的格雷码序列。在这段代码中，首先生成了1位的格雷码，即"0"和"1"。然后通过迭代，每次都将现有的格雷码列表翻倍，并且在新加入的格雷码前加上不同的前缀来保证相邻格雷码之间的差异性。在每一轮迭代中，首先将现有的格雷码序列反转并加上前缀"1"，然后原有的格雷码序列加上前缀"0"。仔细观察，可以看到第一个循环是从末尾向前遍历，将'1'添加到现有元素的前面。这意味着，对于第二个循环，我们应该从头部开始遍历，同样将'0'添加到现有元素的前面，所以选B而不是选A。8.答案：A。解析：在前序遍历中找根，在中序遍历中找根的左右子树，建好树后进行后序遍历。结果为EDBGFCA。9.答案：C。解析：完全二叉树兄弟结点一般是左偶右奇，9号结点的兄弟结点只能是8号，而右子结点即9*2+1=19，选C。10.答案：C。解析：代码的思路是计算出当前根结点左子树的深度，右子树的深度，那么以根结点为子树的深度即max(左子树，右子树)+1，+1即将根结点的深度也计算在内，所以选C。11.答案：A。解析：根据BST的性质，如果插入的值小于当前结点的值，则应该插入到当前结点的左子树；如果大于，则应该插入到当前结点的右子树。所以选A。12.答案：A。解析：二叉搜索树插入规则：（1）待插入值小于当前节点值→往左子树递归插入；（2）待插入值大于当前节点值→往右子树递归插入；（3）题目说明无重复元素，不用判相等。13.答案：B。解析：根据输入数组建BST为如下。然后根据“左根右”的遍历规则输出为:2345678，选B。14.答案：B。解析：一个问题是否能用DP来解决我们的考虑一般有两点，①最优子结构，②无后效性。最优子结构即，选项中B的可分解成相互依赖的子问题的问题，因此选B。15.答案：C。解析：01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值，4个物品的重量为1346，价值为20305060，背包容量为10，最大价值是136对应的110。16.答案：正确。解析：这三个语言都支持面向对象编程的关键特性，但是它们的使用场景和编程风格有所不同。C++更适合需要高性能和底层控制的应用，Python则因其易学性和代码的简洁性而在数据分析、科学计算等领域广泛应用，而Java因为其平台无关性和安全性，在企业级应用开发中有广泛的应用。17.答案：错误。解析：静态成员变量的特点如下。共享性：所有的类实例共享同一个静态成员变量的副本。这意味着无论创建多少个类的对象，静态成员变量只会有一个实例存在。访问性：静态成员变量可以在类的成员函数中访问，也可以通过类名直接访问，而不必创建类的对象。如何访问静态成员变量：通过类名直接访问、通过成员函数访问，通过友元函数访问。18.答案：错误。解析：数组实现的栈在不需要频繁调整大小的情况下，占用的内存通常较少。如果数组实现的栈需要频繁调整大小，可能会导致额外的空间开销，链表实现的栈由于每个节点需要存储额外的指针，总体内存开销可能高于数组实现，但在入队和出队操作上效率较高。所以认为数组实现占用内存较少是不正确，且栈只有入栈和出栈操作，没有入队出队一说。19.答案：正确。解析：这段代码演示了C++中的多态性。base类中定义了一个虚函数show()，而derived类继承自base类，并且覆盖（override）了show()函数。在主函数中，b是一个指向base类的指针，但它实际上指向的是一个derived类的对象。由于show()是虚函数，当通过基类指针b调用show()时，实际上调用的是派生类derived中覆盖的版本。因此，当执行b->show();时，输出将是derived类中定义的内容，即：“derivedclas”，所以说正确的。20.答案：错误。解析：创建一个派生类的对象时，会先调用基类的构造函数，再调用派生类的构造函数。因此，题目中的描述是不正确的。正确的构造顺序是如下。调用基类base的构造函数，输出"baseconstructor"。调用派生类derived的构造函数，输出"derivedconstructor"。因此，题目描述“生成一个派生类的对象时，只调用派生类的构造函数”是错误的。21.答案：正确。解析：哈夫曼编码是一种用于无损数据压缩的算法，它通过构建一棵特殊的二叉树——哈夫曼树（Huffmantree）来为字符分配编码。哈夫曼编码的目标是最小化加权路径长度（weightedpathlength），即编码后的总长度最短。在构建哈弗曼树时，每次选择局部最优解（即频率最小的两个节点进行合并），最终构建出全局最优的哈夫曼树。因此，题目描述是正确的。22.答案：正确。解析：考虑二叉树中第i层的叶结点数目最多为2i-1,,那10<i-1<11,11<i<12,因此深度为12是正确的。23.答案：错误。解析：通常使用队列来实现，而使用队列的本质是要区分结点遍历的先后顺序。24.答案：正确。解析：正确的。状态转移方程是动态规划中用来描述状态变化的重要工具。25.答案：正确。解析：正确，在应用动态规划算法时，识别并存储重叠子问题的解是动态规划的核心要素之一。动态规划通过将问题分解为更小的子问题，并存储这些子问题的解，避免了重复计算相同的子问题，从而提高了算法的效率。26.参考程序。#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intn;intdp[N];intmain(){cin>>n;for(inti=1;i<=n;i++){dp[i]=i;for(intj=1;j<=sqrt(i);j++){dp[i]=min(dp[i-j*j]+1,dp[i]);}}cout<<dp[n]<<"\n";}27.参考程序。