2025年12月GESP编程能力认证C++等级考试六级真题(含答案和解析)

2025年12月GESP编程能力认证C++等级考试六级真题(含答案和解析)一、单选题（每题2分，共30分）。1.在面向对象编程中，下列关于“虚函数”的描述中，错误的是（）。A.虚函数用于支持运行时多态B.通过基类指针调用虚函数时，会根据对象实际类型决定调用版本。C.构造函数可以声明为虚函数以支持多态D.基类析构函数常声明为虚函数以避免资源泄漏答案：C。解析：构造函数不能声明为虚函数，析构函数可以声明为虚函数，以确保通过基类指针删除派生类对象时能够正确调用派生类的析构函数，避免资源泄漏。2.执行如下代码，会输出“钢琴：叮咚叮咚”和“吉他：咚咚当当”。这体现了面向对象编程的（）特性。classInstrument{public:virtualvoidplay(){cout<<"乐器在演奏声音"<<endl;}virtual~Instrument(){}};classPiano:publicInstrument{public:voidplay()override{cout<<"钢琴：叮咚叮咚"<<endl;}};classGuitar:publicInstrument{public:voidplay()override{cout<<"吉他：咚咚当当"<<endl;}};intmain(){Instrument*instruments[2];instruments[0]=newPiano();instruments[1]=newGuitar();for(inti=0;i<2;++i){instruments[i]->play();}for(inti=0;i<3;++i){deleteinstruments[i];}return0;}A.继承B.封装C.多态D.链接答案：C。解析：代码中基类Instrument的play()方法声明为虚函数，派生类Piano和Guitar重写该方法。通过基类指针数组调用play()时，根据实际对象类型调用相应的派生类方法，体现了运行时多态。3.关于以下代码，说法正确的是（）。classInstrument{public:voidplay(){cout<<"乐器在演奏声音"<<endl;}virtual~Instrument(){}};classPiano:publicInstrument{public:voidplay()override{cout<<"钢琴：叮咚叮咚"<<endl;}};classGuitar:publicInstrument{public:voidplay()override{cout<<"吉他：咚咚当当"<<endl;}};intmain(){Instrument*instruments[2];instruments[0]=newPiano();instruments[1]=newGuitar();for(inti=0;i<2;++i){instruments[i]->play();}for(inti=0;i<3;++i){deleteinstruments[i];}return0;}A.执行代码会输出两行，内容分别为：钢琴：叮咚叮咚和吉他：咚咚当当。B.执行代码会输出两行，内容分别为：乐器在演奏声音和乐器在演奏声音。C.代码编译出现错误D.代码运行出现错误答案：C。解析：基类Instrument中的play()方法未声明为virtual，派生类中使用override关键字试图重写该方法会导致编译错误，因为override要求基类方法必须是虚函数。4.某文本编辑器把用户输入的字符依次压入栈S。用户依次输入A,B,C,D后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是？（）。A.ABB.ABCC.ABDD.BC答案：A。解析：输入顺序为A,B,C,D，栈顶为D。第一次撤销弹出D，栈中剩余A,B,C；第二次撤销弹出C，栈中剩余A,B。因此栈底到栈顶为AB。5.假设循环队列数组长度为N，其中队空判断条件为front==rear，队满判断条件为(rear+1)%N==front，出队对应的操作为front=(front+1)%N，入队对于的操作为rear=(rear+1)%N。循环队列长度N=6，初始front=1,rear=1，执行操作序列为：入队,入队,入队,出队,入队,入队，则最终(front,rear)的值是（）。A.(2,5)B.(2,0)C.(3,5)D.(3,0)答案：B。解析：初始：front=1,rear=1。入队×3：rear依次变为2,3,4。出队×1：front变为2。入队×2：rear依次变为5,0（模6）。最终：front=2,rear=0。注意：循环队列要浪费一个位置，避免队空/队满判断冲突。6.以下函数check()用于判断一棵二叉树是否为（）。boolcheck(TreeNode*root){if(!root)returntrue;queue<TreeNode*>q;q.push(root);boolhasNull=false;while(!q.empty()){TreeNode*cur=q.front();q.pop();if(!cur){hasNull=true;}else{if(hasNull)returnfalse;q.push(cur->left);q.push(cur->right);}}returntrue;}A.满二叉树B.完全二叉树C.二叉搜索树D.平衡二叉树答案：B。解析：该函数通过层序遍历判断二叉树是否为完全二叉树：若在遇到空节点之后又遇到非空节点，则不是完全二叉树。完全二叉树要求最后一层节点从左到右连续排列。7.以下代码实现了二叉树的（）。voidtraverse(TreeNode*root){if(!root)return;traverse(root->left);traverse(root->right);cout<<root->val<<"";}A.前序遍历B.中序遍历C.后序遍历D.层序遍历答案：C。解析：遍历顺序为：左子树→右子树→根节点，符合后序遍历的定义。8.下面代码实现了哈夫曼编码，则横线处应填写的代码是（）。structSymbol{charch;//字符。longlongfreq;//频率。stringcode;//哈夫曼编码。};structNode{longlongw;//权值。intl,r;//左右孩子（节点下标），-1表示空。intsym;//叶子对应符号下标；内部节点为-1。Node(longlong_w=0,int_l=-1,int_r=-1,int_sym=-1):w(_w),l(_l),r(_r),sym(_sym){}};//从A(leafIdx)和B(internalIdx)的队首取最小的一个节点下标。staticintPopMinNode(constvector<Node>&nodes,constvector<int>&leafIdx,intn,int&pA,constvector<int>&internalIdx,int&pB){if(pA<n&&(pB>=(int)internalIdx.size()||nodes[leafIdx[pA]].w<=nodes[internalIdx[pB]].w)){returnleafIdx[pA++];}else{returninternalIdx[pB++];}}//DFS生成编码（左0，右1）。staticvoidDFSBuildCodes(intu,constvector<Node>&nodes,Symbolsym[],string&path){if(u==-1)return;if(nodes[u].sym!=-1){//叶子。sym[nodes[u].sym].code=path;return;}path.push_back('0');DFSBuildCodes(nodes[u].l,nodes,sym,path);path.pop_back();path.push_back('1');DFSBuildCodes(nodes[u].r,nodes,sym,path);path.pop_back();}intBuildHuffmanCodes(Symbolsym[],intn){for(inti=0;i<n;i++)sym[i].code.clear();if(n<=0)return-1;//只有一个字符：约定编码为"0"。if(n==1){sym[0].code="0";return0;}vector<Node>nodes;nodes.reserve(2*n);//(1)建立叶子节点。vector<int>leafIdx(n);for(inti=0;i<n;i++){leafIdx[i]=(int)nodes.size();nodes.push_back(Node(sym[i].freq,-1,-1,i));}//(2)叶子按权值排序（A队列）。sort(leafIdx.begin(),leafIdx.end(),[&](inta,intb){if(nodes[a].w!=nodes[b].w)returnnodes[a].w<nodes[b].w;returnnodes[a].sym<nodes[b].sym;//稳定一下。});//B队列（内部节点下标队列）。vector<int>internalIdx;internalIdx.reserve(n);intpA=0,pB=0;//(3)合并n-1次。for(intk=1;k<n;k++){intx=PopMinNode(nodes,leafIdx,n,pA,internalIdx,pB);inty=PopMinNode(nodes,leafIdx,n,pA,internalIdx,pB);intz=(int)nodes.size();________________________//在此处填写代码。}introot=internalIdx.back();//(4)DFS生成编码。stringpath;DFSBuildCodes(root,nodes,sym,path);returnroot;}A.nodes.push_back(Node(nodes[x].w+nodes[y].w,x,y,-1));internalIdx.push_back(z);B.nodes.push_back(Node(nodes[x].w+nodes[y].w,x,y,-1));leafIdx.push_back(z);C.internalIdx.push_back(z);nodes.push_back(Node(nodes[x].w+nodes[y].w,x,y,x+y));D.nodes.push_back(Node(nodes[x].w+nodes[y].w,x,y,x+y));leafIdx.push_back(z);答案：A。解析：哈夫曼树构建过程中，合并两个节点生成的新节点，其权值为两子节点权值之和，左右孩子分别为x和y，新节点应加入内部节点队列internalIdx。9.以下关于哈夫曼编码的说法，正确的是（）。A.哈夫曼编码是定长编码B.哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀。C.哈夫曼编码一定唯一D.哈夫曼编码不能用于数据压缩答案：B。解析：哈夫曼编码是一种变长前缀编码，任一字符的编码都不是另一字符编码的前缀，因此解码时不会产生歧义。编码结果不唯一（合并顺序可调），但均为最优前缀码。10.以下函数实现了二叉排序树（BST）的（）操作。TreeNode*op(TreeNode*root,intx){if(!root)returnnewTreeNode(x);if(x<root->val)root->left=op(root->left,x);elseroot->right=op(root->right,x);returnroot;}A.查找B.插入C.删除D.遍历答案：B。解析：函数递归地在二叉排序树中查找插入位置，若当前节点为空则创建新节点并返回，否则根据值大小递归插入左子树或右子树，最终返回根节点，符合插入操作的逻辑。11.下列代码实现了树的深度优先遍历，则横线处应填入（）。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};voiddfs(TreeNode*root){if(!root)return;stack<TreeNode*>st;st.push(root);while(!st.empty()){TreeNode*node=st.top();st.pop();cout<<node->val<<"";if(node->right)st.push(node->right);________________________}}A.if(node->left)st.push(node->left);B.if(node->left)st.pop(node->left);C.if(node->left)st.front(node->left);D.if(node->left)st.push(node->right);答案：A。解析：本题考查二叉树的迭代式深度优先遍历(DFS)，为了实现遍历顺序是根→左→右，想要左子树优先于右子树被处理，就必须让「左子节点后入栈、右子节点先入栈」。这样出栈顺序是左孩子先于右孩子，符合前序遍历。12.给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为x的结点，则横线处应填入（）。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};TreeNode*bfsFind(TreeNode*root,intx){if(!root)returnnullptr;queue<TreeNode*>q;q.push(root);while(!q.empty()){TreeNode*cur=q.front();q.pop();if(cur->val==x)returncur;________________________}returnnullptr;}A.q.push(cur);B.if(cur->right)q.push(cur->right);C.if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);D.q.push(cur->left);q.push(cur->right);答案：C。解析：BFS遍历二叉树时，应将当前节点的左孩子和右孩子（若存在）依次入队，以保证层序访问所有节点。13.在二叉排序树（BinarySearchTree,BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（）。boolfind(Node*root,intx){while(root){if(root->val==x)returntrue;root=(x<root->val)?root->left:root->right;}returnfalse;}A.最坏情况下，访问结点数是O(logn)。B.最坏情况下，访问结点数是O(n)。C.无论如何，访问结点数都不超过树高的一半。D.一定比在普通二叉树中搜索快答案：B。解析：BST查找的平均时间复杂度为O(logn)，但在最坏情况下（树退化为链表），时间复杂度为O(n)。因此选项B正确。14.题0/1背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。foreachitem(w,v):for(intj=W;j>=w;--j)dp[j]=max(dp[j],dp[j-w]+v);A.内层j必须从小到大，否则会漏解。B.内层j必须从大到小，否则同一件物品会被用多次。C.j从大到小或从小到大都一样D.只要dp初始为0，方向无所谓。答案：B。解析：0/1背包中，物品只能选一次。若j从小到大遍历，则dp[j-w]可能已经包含当前物品，导致物品被重复使用，相当于完全背包。因此必须从大到小遍历。15.以下关于动态规划的说法中，错误的是（）。A.动态规划方法通常能够列出递推公式。B.动态规划方法的时间复杂度通常为状态的个数。C.动态规划方法有递推和递归两种实现形式。D.对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。答案：B。解析：动态规划的时间复杂度不仅与状态个数有关，还与状态转移的复杂度有关。例如，状态数为O(n)，每个状态转移需要O(m)时间，则总复杂度为O(n·m)，不一定等于状态个数。二、判断题（每题2分，共20分）。16.以下代码中，构造函数被调用的次数是1次。（）。classTest{public:Test(){cout<<"T";}};intmain(){Testa;Testb=a;}答案：错误。解析：Testb=a;调用的是复制构造函数，而非默认构造函数。若未定义复制构造函数，编译器会自动生成一个。因此输出为T一次（仅a的构造），总次数要加上复制构造函数被调用的一次。17.面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。（）。答案：正确。解析：封装是面向对象三大特性之一，指将数据（属性）和操作数据的方法（函数）封装在类中，通过访问控制（public、private、protected）隐藏内部实现，仅暴露必要接口。18.以下代码能够正确统计二叉树中叶子结点的数量。（）。intcountLeaf(TreeNode*root){if(!root)return0;if(!root->left&&!root->right)return1;returncountLeaf(root->left)+countLeaf(root->right);}答案：正确。解析：函数递归判断：若节点为空返回0；若节点左右孩子均为空则为叶子节点返回1；否则递归统计左右子树的叶子节点数。逻辑正确。19.广度优先遍历二叉树可用栈来实现。（）。答案：错误。解析：BFS使用队列实现（先进先出），以保证按层遍历；DFS才使用栈（先进后出）实现深度优先。因此该说法错误。20.函数调用管理可用栈来管理。（）。答案：正确。解析：函数调用栈（callstack）用于存储函数调用信息（返回地址、局部变量等），支持函数调用与返回的“后进先出”顺序。21.在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。（）。答案：错误。解析：若某节点左子树为空，不一定是整棵树的最小值。整棵树的最小值应从根节点一直向左遍历至叶子节点。22.下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。（）。boolisBST(TreeNode*root,intminVal,intmaxVal){if(!root)returntrue;if(root->val<=minVal||root->val>=maxVal)returnfalse;returnisBST(root->left,minVal,root->val)&&isBST(root->right,root->val,maxVal);}答案：正确。解析：函数通过传入当前节点值的上下界（minVal,maxVal）递归判断左右子树是否满足BST性质：左子树所有节点值应小于当前值，右子树所有节点值应大于当前值。23.格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。（）。答案：错误。解析：格雷编码的核心特性是相邻两个编码之间仅有一位不同，这有助于减少在数字电路或通信中因多位同时变化而产生的错误。24.小杨在玩一个闯关游戏，从第1关走到第4关。每一关的体力消耗如下（下标表示关卡编号）：cost=[0,3,5,2,4]，其中cost[i]表示到达第i关需要消耗的体力，cost[0]=0表示在开始状态，体力消耗为0。小杨每次可以从当前关卡前进1步或2步。按照上述规则，从第1关到第4关所需消耗的最小体力为7。（）。答案：错误。解析：设dp[i]表示到达第i关的最小体力消耗，则。dp[1]=cost[1]=3。dp[2]=min(dp[1]+cost[2],cost[2])=min(3+5,5)=5。dp[3]=min(dp[2]+cost[3],dp[1]+cost[3])=min(5+2,3+2)=5。dp[4]=min(dp[3]+cost[4],dp[2]+cost[4])=min(5+4,5+4)=9。因此最小体力为9，不是7。25.假定只有一个根节点的树的深度为1，则一棵有n个节点的完全二叉树，则树的深度为[log2(n)]+1。（）。答案：正确。解析：完全二叉树的深度（高度）公式为：h=[log2n]+1（根节点深度为1），该公式成立。三、编程题（每题25分，共50分）。26.试题名称：路径覆盖。时间限制：1.0s。内存限制：512.0MB。题目描述：给定一棵有n个结点的有根树T，结点依次以1,2…n编号，根结点编号为1。方便起见，编号为i的结点称为结点i。初始时T中的结点均为白色。你需要将T中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点i染为黑色需要代价ci，你需要在满足以上条件的情况下，最小化染色代价之和。叶子是指T中没有子结点的结点。输入格式：第一行，一个正整数n，表示结点数量。第二行，n-1个正整数，其中fi表示结点i的父结点的编号，保证fi<i。第三行，n个正整数c1,c2…cn，其中ci表示将结点i染为黑色所需的代价。输出格式：一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。输入样例1。输出样例1。输入样例2。输出样例2。数据范围：对于40%的测试点，保证2≤n≤16。对于另外20%的测试点，保证fi=i-1。对于所有测试点，保证2≤n≤105，1≤ci≤109。参考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintN=1e5+5;intn;intf[N],c[N],cnt[N];longlongans[N];intmain(){scanf("%d",&n);for(inti=2;i<=n;i++){scanf("%d",&f[i]);cnt[f[i]]++;}for(inti=1;i<=n;i++)scanf("%d",&c[i]);for(inti=n;i>=1;i--){if(cnt[i]==0)ans[i]=c[i];ans[i]=min(ans[i],1ll*c[i]);ans[f[i]]+=ans[i];}printf("%lld\n",ans[1]);return0;}解析：（1）问题转化：每个叶子到根的路径上至少有一个黑点，等价于所有叶子被某个祖先节点“覆盖”。（2）自底向上DP：从叶子节点向上递推，每个节点有两种状态。·染当前节点：代价为c[i]，所有子树均被覆盖。·不染当前节点：则每个子树必须自己提供覆盖（即子树