2025年3月GESP认证C++等级考试六级真题(含答案和解析-在末尾)

2025年3月GESP认证C++等级考试六级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（）。A.类是一个抽象的概念，用于描述具有相同属性和行为的对象集合。B.类可以包含属性和方法，属性用于描述对象的状态，方法用于描述对象的行为。C.类可以被实例化，生成具体的对象。D.类一旦定义后，其属性和方法不能被修改或扩展。2.哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（）。A.哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。B.在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。C.哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。D.哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀，因此可以实现唯一解码。3.以下代码实现了树的哪种遍历方式？（）。voidtraverse(TreeNode*root){if(root==nullptr)return;cout<<root->val<<"";traverse(root->left);traverse(root->right);}A.前序遍历B.中序遍历C.后序遍历D.层次遍历4.以下关于完全二叉树的代码描述，正确的是（）。boolisCompleteTree(TreeNode*root){if(root==nullptr)returntrue;queue<TreeNode*>q;q.push(root);boolhasNull=false;while(!q.empty()){TreeNode*node=q.front();q.pop();if(node==nullptr){hasNull=true;}else{if(hasNull)returnfalse;q.push(node->left);q.push(node->right);}}returntrue;}A.该代码用于判断一棵树是否为满二叉树B.该代码用于判断一棵树是否为完全二叉树C.该代码用于判断一棵树是否为二叉搜索树D.该代码用于计算树的高度5.以下代码实现了二叉排序树的哪种操作？TreeNode*op(TreeNode*root,intval){if(root==nullptr)returnnewTreeNode(val);if(val<root->val){root->left=op(root->left,val);}else{root->right=op(root->right,val);}returnroot;}A.查找B.插入C.删除D.遍历6.给定字符集{A,B,C,D}的出现频率分别为{5,1,6,2}，则正确的哈夫曼编码是（）。A.A:0,B:100,C:11,D:101B.A:11,B:100,C:0,D:101C.A:0,B:101,C:11,D:100D.A:10,B:101,C:0,D:1007.关于动态规划的描述，正确的是（）。A.动态规划算法的时间复杂度总是低于贪心算法。B.动态规划要求问题必须具有最优子结构和重叠子问题两个性质。C.动态规划通过递归实现时不需要存储中间结果。D.动态规划的核心思想是将问题分解为互不重叠的子问题。8.以下代码中，类的构造函数被调用了（）次。classMyClass{public:MyClass(){cout<<"Constructorcalled!"<<endl;}};intmain(){MyClassobj1;MyClassobj2=obj1;return0;}A.1B.2C.3D.09.以下代码实现了循环队列的哪种操作？classCircularQueue{int*arr;intfront,rear,size;public:CircularQueue(intk){size=k;arr=newint[k];front=rear=-1;}boolenQueue(intvalue){if(isFull())returnfalse;if(isEmpty())front=0;rear=(rear+1)%size;arr[rear]=value;returntrue;}};A.入队B.出队C.查看队首元素D.判断队列是否为空10.以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（）。intcountLeafNodes(TreeNode*root){if(root==nullptr)return0;stack<TreeNode*>s;s.push(root);intcount=0;while(!s.empty()){TreeNode*node=s.top();s.pop();if(node->left==nullptr&&node->right==nullptr){count++;}if(node->right)s.push(node->right);________________________//在此处填入代码。}returncount;}A.if(node->left)s.push(node->left);B.if(node->left)s.pop(node->left);C.if(node->left)s.front(node->left);D.if(node->left)s.push(node->right);11.以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（）。TreeNode*findNode(TreeNode*root,inttarget){if(root==nullptr)returnnullptr;queue<TreeNode*>q;q.push(root);while(!q.empty()){TreeNode*current=q.front();q.pop();if(current->val==target){returncurrent;//找到目标节点。}________________________//在此处填入代码。}returnnullptr;//未找到目标节点。}A.if(current->left)q.push(current->left);if(current->right)q.push(current->right);B.if(current->left)q.pop(current->left);if(current->right)q.pop(current->right);C.if(current->left)q.front(current->left);if(current->right)q.front(current->right);D.if(current->left)q.push(current->right);if(current->right)q.push(current->left);12.以下代码用于生成n位格雷编码。横线上应填写（）。vector<string>generateGrayCode(intn){if(n==0)return{"0"};if(n==1)return{"0","1"};vector<string>prev=generateGrayCode(n-1);vector<string>result;for(strings:prev){result.push_back("0"+s);//在前缀添加0。}for(inti=prev.size()-1;i>=0;i--){________________________//在此处填入代码。}returnresult;}A.result.push_back("1"+prev[i]);B.result.push_back("0"+prev[i]);C.result.push_back(prev[i]+"1");D.result.push_back(prev[i]+"0");13.以下代码实现了0/1背包问题的动态规划解法。假设物品重量为weights[]，价值为values[]，背包容量为W，横线上应填写（）。intknapsack(intW,vector<int>&weights,vector<int>&values){intn=weights.size();vector<vector<int>>dp(n+1,vector<int>(W+1,0));for(inti=1;i<=n;i++){for(intj=1;j<=W;j++){if(weights[i-1]>j){dp[i][j]=dp[i-1][j];//当前物品装不下。}else{dp[i][j]=max(_________________________);//在此处填入代码。}}}returndp[n][W];}A.dp[i-1][j],values[i-1]B.dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1]C.dp[i][j-1],values[i-1]D.dp[i-1][j-weights[i-1]]+values[i-1],dp[i][j-1]14.以下代码用于检查字符串中的括号是否匹配，横线上应填写（）。boolisBalanced(strings){stack<char>st;for(charc:s){if(c=='('||c=='['||c=='{'){st.push(c);}else{if(st.empty())returnfalse;//无左括号匹配。chartop=st.top();st.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')||(c=='}'&&top!='{')){returnfalse;}}}return________________;//在此处填入代码。}A.trueB.falseC.st.empty()D.!st.empty()15.关于下面代码，说法错误的是（）。classShape{protected:stringname;public:Shape(conststring&n):name(n){}virtualdoublearea()const{return0.0;}};classCircle:publicShape{private:doubleradius;//半径。public:Circle(conststring&n,doubler):Shape(n),radius(r){}doublearea()constoverride{return3.14159*radius*radius;}};classRectangle:publicShape{private:doublewidth;//宽度。doubleheight;//高度。public:Rectangle(conststring&n,doublew,doubleh):Shape(n),width(w),height(h){}doublearea()constoverride{returnwidth*height;}};intmain(){Circlecircle("MyCircle",5.0);Rectanglerectangle("MyRectangle",4.0,6.0);Shape*shapePtr=&circle;cout<<"Area:"<<shapePtr->area()<<endl;shapePtr=&rectangle;cout<<"Area:"<<shapePtr->area()<<endl;return0;}A.语句Shape*shapePtr=&circle;和shapePtr=&rectangle;出现编译错误B.Shape为基类，Circle和Rectangle是派生类。C.通过继承，Circle和Rectangle复用了Shape的属性和方法，并扩展了新的功能。D.Circle和Rectangle通过重写（override）基类的虚函数area和基类指针，实现了运行时多态。二、判断题（每题2分，共20分）。16.哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。（）。A.正确B.错误17.格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。（）。A.正确B.错误18.在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。（）。A.正确B.错误19.以下代码实现的是二叉树的中序遍历。（）。voidtraverse(TreeNode*root){if(root==nullptr)return;traverse(root->left);cout<<root->val<<"";traverse(root->right);}A.正确B.错误20.题C++支持构造函数重载，但默认无参数的构造函数只能有一个。（）。A.正确B.错误21.二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。（）。A.正确B.错误22.在动态规划解决一维硬币找零问题时，若硬币面额为[1,3,4]，目标金额为6，则最少需要2枚硬币（3+3）。（）。A.正确B.错误23.面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。（）。A.正确B.错误24.以下代码创建的树是一棵完全二叉树。（）。TreeNode*root=newTreeNode{1};root->left=newTreeNode{2};root->right=newTreeNode{3};root->left->left=newTreeNode{4};A.正确B.错误25.栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为O(1)。（）。A.正确B.错误三、编程题（每题25分，共50分）。26.树上漫步。题目描述：小A有一棵n个结点的树，这些结点依次以1，2，…，n标号。小A想在这棵树上漫步。具体来说，小A会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小A只会在偶数步（可以是零步）后结束漫步。现在小A想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。输入格式：第一行，一个正整数n。接下来n-1行，每行两个整数ui，vi，表示树上有一条连接结点ui和结点vi的边。输出格式：一行，n个整数，第i个整数表示从结点i出发开始漫步，能结束漫步的结点数量。数据范围：对于40%的测试点，保证1≤n≤103。对于所有测试点，保证1≤n≤2×105。27.环线。题目描述：小A喜欢坐地铁。地铁环线有n个车站，依次以1，2，…，n标号。车站i（1≤i＜n）的下一个车站是车站。特殊地，车站n的下一个车站是车站1。小A会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小A至少会经过一个车站。小A不会经过一个车站多次。当小A乘坐地铁环线经过车站i时，小A会获得ai点快乐值。请你安排小A的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。输入格式：第一行，一个正整数n，表示车站的数量。第二行，n个整数a1，a2，…，an，分别表示经过每个车站时获得的快乐值。输出格式：一行，一个整数，表示小A能获得的最大快乐值。数据范围：对于20%的测试点，保证1≤n≤200。对于40%的测试点，保证1≤n≤2000。对于所有测试点，保证1≤n≤2×105，-109≤ai≤109。答案解析如下。1.答案：D。解析：在面向对象编程领域，类的核心特征主要包括封装、继承与多态性。继承特性指的是一个类能够获取另一个类的属性与方法，被获取的类通常被称为基类或父类，而获取这些属性与方法的类则被称为派生类或子类。子类能够利用父类的代码，并且可以在其基础上扩展新的属性和方法，或者对父类的方法进行重写。2.答案：B。解析：在构建哈夫曼编码的过程中，较低频率的字符会被更早地合并，从而位于树结构的较深层级，即距离根节点较远；相对地，较高频率的字符则会在较晚的阶段被合并，因此它们处于树结构的较浅层级，更接近根节点。3.答案：A。解析：通过分析代码，可以发现其首先访问根节点，随后递归地访问左子树，最终递归地访问右子树，这一过程体现了先序遍历的顺序。4.答案：B。解析：分析代码，可以发现代码采用了queue队列结构，该结构通常用于实现广度优先搜索算法。程序首先对根节点进行访问，随后依次访问左子树和右子树。函数的返回类型为布尔值，即true或false，基于此可以排除选项D。二叉搜索树的特性与节点上的权值相关，在函数中并未设置记录节点数值的变量，因此选项C亦被排除。至于满二叉树，其定义要求除叶子节点外，每个节点都必须拥有左右两个子节点，但当前代码并未反映出这一特性，故选项A也不符合。综上所述，正确答案应为选项B。5.答案：B。解析：分析代码，root为空，会新建一个结点；root不为空，会根据val的大小，插入到左子树或者右子树，因此是插入操作，选B。6.答案：B。解析：通过构建哈夫曼树，依据字符集出现频率的不同赋予相应的权重，权重较低的节点一般位于左侧，并将其对应边的编码定为0，而右侧则为1。根据此方法生成的字符集哈夫曼编码，选择方案B。7.答案：B。解析：动态规划的基础知识，动态规划必须有最优⼦结构和重叠⼦问题两个性质。8.答案：A。解析：MyClassobj2=obj1;这行代码运用了拷贝初始化来创建对象，调用的是拷贝构造函数，而非重写默认构造函数。9.答案：A。解析：分析第13和14行代码，rear增加，是队尾增加新元素，选A。10.答案：A。解析：参照第15行代码，选择A项。第15行代码表明若存在右子节点，则将其加入队列；紧接着的下一行代码则意味着若存在左子节点，亦应将其加入队列。11.答案：A。解析：根据题意，左右子节点若是存在，则先入队，再判断值是否为答案，选A。12.答案：A。解析：在一组数字的编码过程中，若任意两个相邻的代码仅有一位二进制数存在差异，则该编码被定义为格雷码。编码的生成步骤如下所述：首先，生成两个基本字符串，即“0”和“1”。其次，在这两个字符串的基础上，于每个字符串的前端分别添加“0”和“1”。通过在第八行的循环中添加“0”，以及后续循环中添加“1”，从而完成了格雷码的生成过程。因此，正确选项为A。13.答案：B。解析：动态规划中的背包问题。else里完成的是当前物品能装下，能装下也分2种选择：装的时候和不装的时候哪种情况值最大。dp[i-1][j]表示不装该物品，dp[i-1][j-weights[i-1]]+values[i-1]表示装该物品，求最大值即可。选B。14.答案：C。解析：根据函数的定义，横线处应当返回“true”，但选项A并不正确。例如，字符串“(()”未能得到正确的匹配结果，原因是栈中尚有剩余元素。只有当栈为空时，才能表明匹配成功。因此，正确答案应为C。15.答案：A。解析：A选项中的2个赋值不会出现编译错误。Circle类和Rectangle类都继承自Shape类，基于面向对象编程中的多态特性，派生类对象的指针或引用可以转换为基类对象的指针或引用，这种转换是安全的。16.答案：正确。解析：构建哈夫曼树时，每次合并的都是权值最小的2个节点，这样最终树的带权路径长度最小。17.答案：错误。解析：在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。18.答案：错误。解析：深搜中，通常使用栈实现“后进先出”访问。19.答案：正确。解析：中序遍历是——左根右。该代码先访问左子树，再访问根节点，最后访问右子树。20.答案：正确。解析：默认⽆参数的构造函数只能有⼀个。21.答案：错误。解析：例如，右子树中，有个节点左子树为空，该节点不是树中最小值节点。22.答案：正确。解析：6可以由114、33构成，最小需要2枚3的硬币。23.答案：正确。解析：在面向对象编程里，封装就是把数据（属性）和操作这些数据的方法（行为）捆绑到一个单元（类）中，同时对外部隐藏对象的内部实现细节，只提供公共的接口来与对象进行交互。24.答案：正确。解析：前2层是满二叉树，最后1层节点从左到右连续排列，无间隔。25.答案：正确。解析：栈和队列均可以⽤双向链表实现，栈的插入和删除只在栈顶，队列的插入在队首，删除在队尾，只需要1次操作，时间复杂度是O（1）。26.参考程序。参考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintN=2e5+5;constintE=N<<1;intn;inth[N],to[E],nx[E],et;intcnt[N]