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

2025年9月GESP编程能力认证C++等级考试六级真题(含答案和解析)一、单选题（每题2分，共30分）。1.下列关于类的说法，错误的是（）。A.构造函数不能声明为虚函数，但析构函数可以。B.函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。C.静态方法属于类而不是某个具体对象，因此推荐用——类名::方法(…)调用。D.不管基类的析构函数是否是虚函数，都可以通过基类指针/引用正确删除派生类对象。答案：D。解析：若基类析构函数非虚函数，基类指针/引用删除派生类对象时，仅会调用基类析构函数，派生类的成员无法释放，导致内存泄漏，因此必须将基类析构函数声明为虚函数才能正确删除。2.假设变量veh是类Car的一个实例，我们可以调用veh.move()，是因为面向对象编程有（）性质。classVehicle{private:stringbrand;public:Vehicle(stringb):brand(b){}voidsetBrand(conststring&b){brand=b;}stringgetBrand()const{returnbrand;}voidmove()const{cout<<brand<<"ismoving…"<<endl;}};classCar:publicVehicle{private:intseatCount;public:Car(stringb,intseats):Vehicle(b),seatCount(seats){}voidshowInfo()const{cout<<"Thiscarisa"<<getBrand()<<"with"<<seatCount<<"seats."<<endl;}};A.继承(Inheritance)B.封装(Encapsulation)C.多态(Polymorphism)D.链接(Linking)答案：A。解析：Car类通过publicVehicle实现公有继承，会自动继承Vehicle类的非私有。3.下面代码中v1和v2调用了相同接口move()，但输出结果不同，这体现了面向对象编程的（）特性。classVehicle{private:stringbrand;public:Vehicle(stringb):brand(b){}voidsetBrand(conststring&b){brand=b;}stringgetBrand()const{returnbrand;}virtualvoidmove()const{cout<<brand<<"ismoving…"<<endl;}};classCar:publicVehicle{private:intseatCount;public:Car(stringb,intseats):Vehicle(b),seatCount(seats){}voidshowInfo()const{cout<<"Thiscarisa"<<getBrand()<<"with"<<seatCount<<"seats."<<endl;}voidmove()constoverride{cout<<getBrand()<<"carisdrivingontheroad!"<<endl;}};classBike:publicVehicle{public:Bike(stringb):Vehicle(b){}voidmove()constoverride{cout<<getBrand()<<"bikeiscyclingonthepath!"<<endl;}};intmain(){Vehicle*v1=newCar("Toyota",5);Vehicle*v2=newBike("Giant");v1->move();v2->move();deletev1;deletev2;return0;}A.继承(Inheritance)B.封装(Encapsulation)C.多态(Polymorphism)D.链接(Linking)答案：C。解析：由于Vehicle::move()声明为virtual（虚函数），派生类Car、Bike重写该方法后，基类指针v1、v2调用move()时会动态绑定到实际指向的派生类对象的方法，导致相同接口输出不同结果，这是“多态”的核心特性。4.栈的操作特点是（）。A.先进先出B.先进后出C.随机访问D.双端进出答案：B。解析：栈是一种“后进先出”（LIFO，LastInFirstOut）或“先进后出”的线性数据结构，仅允许在一端（栈顶）进行插入（push）和删除（pop）操作。5.循环队列常用于实现数据缓冲。假设一个循环队列容量为5（即最多存放4个元素，留一个位置区分空与满），依次进行操作：入队数据1，2，3，出队1个数据，再入队数据4和5，此时队首到队尾的元素顺序是（）。A.[2,3,4,5]B.[1,2,3,4]C.[3,4,5,2]D.[2,3,5,4]答案：A。解析：设循环队列数组下标为0~4，front指向队首，rear指向队尾的下一个位置，初始front=0，rear=0。入队1、2、3：rear依次变为1、2、3，队列元素为[1,2,3]（front=0，rear=3）。出队1：front变为1，队列元素为[2,3]（front=1，rear=3）。入队4：rear=4，元素为[2,3,4]。入队5：rear=(4+1)%5=0，此时队列满（(rear+1)%5==front），元素为[2,3,4,5]。因此队首（front=1）到队尾的顺序是2、3、4、5。6.以下函数createTree()构造的树是什么类型（）。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};TreeNode*createTree(){TreeNode*root=newTreeNode(1);root->left=newTreeNode(2);root->right=newTreeNode(3);root->left->left=newTreeNode(4);root->left->right=newTreeNode(5);returnroot;}A.满二叉树B.完全二叉树C.二叉排序树D.其他都不对答案：B。解析：完全二叉树定义——除最后一层外，每一层的节点数均为最大值；最后一层的节点从左到右连续排列，无空缺。createTree()的构造规则完全符合该定义。满二叉树要求所有层节点数均为最大值（最后一层无空缺），本题未满足。二叉排序树要求左子树节点值<根节点值<右子树节点值，本题未提及值的大小关系，因此排除。7.已知二叉树的“中序遍历”是[D,B,E,A,F,C]，“先序遍历”是[A,B,D,E,C,F]。请问该二叉树的后序遍历结果是（）。A.[D,E,B,F,C,A]B.[D,B,E,F,C,A]C.[D,E,B,C,F,A]D.[B,D,E,F,C,A]答案：A。解析：通过先序和中序遍历重构二叉树，再求后序遍历。（1）先序遍历首元素为根节点：根是A。（2）中序遍历中A左侧为左子树[D,B,E]，右侧为右子树[F,C]。（3）左子树的先序是[B,D,E]，根为B；中序B左侧是D（左子树），右侧是E（右子树）。（4）右子树的先序是[C,F]，根为C；中序C左侧是F（左子树），右侧无节点。（5）后序遍历顺序为“左→右→根”：D→E→B→F→C→A。8.完全二叉树可以用数组连续高效存储，如果节点从1开始编号，则对有两个孩子节点的节点i，（）。A.左孩子位于2i，右孩子位于2i+1。B.完全二叉树的叶子节点可以出现在最后一层的任意位置C.所有节点都有两个孩子D.左孩子位于2i+1，右孩子位于2i+2。答案：A。解析：完全二叉树节点从1编号时，节点i的左孩子索引为2i，右孩子为2i+1（如根节点1的左孩子2、右孩子3，节点2的左孩子4、右孩子5）。9.设有字符集{a,b,c,d,e,f}，其出现频率分别为{5,9,12,13,16,45}。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作0，右边分支记作1，左右互换不影响正确性）。A.a:00；b:01；c:10；d:110；e:111；f:0。B.a:1100；b:1101；c:100；d:101；e:111；f:0。C.a:000；b:001；c:01；d:10；e:110；f:111。D.a:10；b:01；c:100；d:101；e:111；f:0。答案：B。解析：哈夫曼编码构造原则——每次选频率最小的两个节点合并，父节点频率为两者之和，左分支记0、右分支记1（左右可互换，编码不唯一但长度最优）。初始节点：5(a)、9(b)、12(c)、13(d)、16(e)、45(f)。第一次合并5+9=14，节点：12(c)、13(d)、14(a,b)、16(e)、45(f)。第二次合并12+13=25，节点：14(a,b)、16(e)、25(c,d)、45(f)。第三次合并14+16=30，节点：25(c,d)、30(a,b,e)、45(f)。第四次合并25+30=55，节点：45(f)、55(a,b,c,d,e)。第五次合并45+55=100，哈夫曼树完成。编码结果（左0右1）。f(45)：根→左，编码0。e(16)：根→右→右，编码111。d(13)：根→右→左→右，编码101。c(12)：根→右→左→左，编码100。b(9)：根→右→右→左→右，编码1101。a(5)：根→右→右→左→左，编码1100。与选项B完全匹配。10.下面代码生成格雷编码，则横线上应填写（）。答案：B。解析：格雷编码的核心步骤是“扩展”。1位格雷码：[0,1]。2位格雷码：[00,01]+反转[00,01]并加1→[00,01,11,10]。3位格雷码：[000,001,011,010]+反转后加1→[000,001,011,010,110,111,101,100]。可见，扩展时需从后往前遍历前一轮的格雷码（prev），反转顺序后加1。因此循环条件应为i从prev.size()-1递减到0，对应选项B。11.请将下列树的深度优先遍历代码补充完整，横线处应填入（）。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};A.vectorB.listC.queueD.stack答案：D。解析：DFS的核心是“深度优先”，需优先访问子节点再回溯，其底层依赖“先进后出”的结构，递归实现调用栈。12.令n是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（）。A.O(n)B.O(logn)C.O(n2)D.O(2n)答案：A。解析：BFS遍历树时，每个节点仅入队1次、出队1次（访问1次），每个边仅处理1次（将子节点入队）。树的边数为n-1，因此总操作次数为O(n+(n-1))，时间复杂度为线性阶O(n)。13.在二叉排序树（BinarySearchTree,BST）中查找元素50，从根节点开始：若根值为60，则下一步应去。搜索：（）。A.左子树B.右子树C.随机D.根节点答案：A。解析：BST的核心性质——左子树所有节点值<根节点值<右子树所有节点值。查找50时，根值60>50，根据规则应前往左子树继续查找（左子树的节点值均小于60，可能包含50）；右子树节点值均大于60，无需搜索。14.删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（），其中findMax和findMin分别为寻找树的最大值和最小值的函数。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};TreeNode*deleteNode(TreeNode*root,intkey){if(!root)returnnullptr;if(key<root->val){root->left=deleteNode(root->left,key);}elseif(key>root->val){root->right=deleteNode(root->right,key);}else{if(!root->left)returnroot->right;if(!root->right)returnroot->left;TreeNode*temp=____________;//在此处填写代码。root->val=temp->val;root->right=deleteNode(root->right,temp->val);}returnroot;}A.root->leftB.root->rightC.findMin(root->right)D.findMax(root->left)答案：C。解析：删除有两个孩子的BST节点，选择右子树的最小值节点（findMin(root->right)）或左子树的最大值节点（findMax(root->left)）替换待删除节点；对比后面的代码，右子树的最小值节点无左孩子，删除该节点后仅需处理其右子树，因此横线处应填入findMin(root->right)，对应选项C。15.给定n个物品和一个最大承重为W的背包，每个物品有一个重量wt[i]和价值val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过，则横线上应填写（）。intknapsack(intW,vector<int>&wt,vector<int>&val,intn){vector<int>dp(W+1,0);for(inti=0;i<n;++i){for(intw=W;w>=wt[i];--w){________________________//在此处填写代码。}}returndp[W];}A.dp[w]=max(dp[w],dp[w]+val[i]);B.dp[w]=dp[w-wt[i]]+val[i];C.dp[w]=max(dp[w-1],dp[w-wt[i]]+val[i]);D.dp[w]=max(dp[w],dp[w-wt[i]]+val[i]);答案：D。解析：01背包的核心是“每个物品仅选或不选”，状态转移需比较两种情况。不选第i个物品：dp[w]保持不变。选第i个物品：dp[w-wt[i]]+val[i]（承重w-wt[i]的最大价值+第i个物品的价值）。因此状态转移方程为dp[w]=max(不选的价值,选的价值)，即dp[w]=max(dp[w],dp[w-wt[i]]+val[i])，对应选项D。二、判断题（每题2分，共20分）。16.当基类可能被多态使用，其析构函数应该声明为虚函数。（）。答案：正确。解析：若基类析构函数非虚函数，删除指针时仅调用基类析构函数，派生类独有的成员（如动态分配的内存）无法释放，导致内存泄漏。声明为虚函数可实现“动态绑定”，确保派生类析构函数被调用，因此该说法正确。17.哈夫曼编码是最优前缀码，且编码结果唯一。（）。答案：错误。解析：哈夫曼编码是“最优前缀码”（平均编码长度最短），但编码结果不唯一。原因是：当两个节点频率相同时，合并时的左右子树可互换（左0右1或左1右0），导致对应字符的编码不同，但平均长度仍最优。例如频率{2,2}的字符，编码可是“0”和“1”，也可是“1”和“0”，因此该说法错误。18.一个含有100个节点的完全二叉树，高度为8。（）。答案：错误。解析：完全二叉树高度h满足公式2^(h-1)-1<n≤2^h-1（n为节点数）。当h=7时：2^6-1=63，2^7-1=127，63<100≤127，满足。因此100个节点的完全二叉树高度为7，该说法错误。19.在C++STL中，栈（std::stack）的pop操作返回栈顶元素并移除它。（）。答案：错误。解析：std::stack的pop()函数仅移除栈顶元素，不返回任何值。若需获取栈顶元素并移除，需先调用top()（获取栈顶元素），再调用pop()（移除）。20.循环队列通过模运算循环使用空间。（）。答案：正确。解析：普通队列存在“假溢出”问题（队尾到达数组末尾但队首有空闲空间），循环队列通过“模运算”（(rear+1)%maxSize、(front+1)%maxSize）让队首和队尾指针在数组中循环移动，复用队首空闲空间，因此该说法正确。21.一棵有n个节点的二叉树一定有n-1条边。（）。答案：正确。解析：树是“连通且无环”的无向图，其核心性质是“节点数n=边数e+1”，即e=n-1。22.以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是425136。（）。structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};答案：正确。解析：中序遍历顺序为“左子树→根节点→右子树”，对题目中的树中序遍历的结果是425136。23.下面代码实现的二叉排序树的查找操作时间复杂度是O(h)，其中h为树高。（）。TreeNode*searchBST(TreeNode*root,intval){while(root&&root->val!=val){root=(val<root->val)?root->left:root->right;}returnroot;}答案：正确。解析：代码中，查找从根节点开始，每次比较后仅向左或右子树移动（排除一半路径），直到找到目标或为空。最坏情况下需遍历从根到叶子的所有节点，路径长度等于树高h，因此时间复杂度为O(h)（理想情况h=logn，最坏情况h=n），该说法正确。24.下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是O(2n)。（）。intfib_dp(intn){if(n<=1)returnn;vector<int>dp(n+1);dp[0]=0;dp[1]=1;for(inti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}答案：错误。解析：代码中，dp[0]和dp[1]初始化后，循环从2到n，共执行n-1次操作（每次计算dp[i]=dp[i-1]+dp[i-2]），总操作次数与n成正比，因此时间复杂度为O(n)，该说法错误。25.有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。（）。//bananas：香蕉的甜度。答案：正确。解析：动态规划阶段，dp[i]=max(dp[i-1],dp[i-2]+bananas[i])，dp[i]表示前i个香蕉的最大甜度。若dp[i]==dp[i-1]，说明未选第i个香蕉（选i-1更优），i--；否则选第i个香蕉，i-=2（跳过相邻），能找到最大甜度对应的香蕉组合，因此该说法正确。三、编程题（每题25分，共50分）。26.试题名称：划分字符串。时间限制：1.0s。内存限制：512.0MB。题目描述：小A有一个由n个小写字母组成的字符串s。他希望将s划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串street来说，str+e+e+t是满足条件的划分；而s+tree+t不是，因为子串tree中e出现了两次。额外地，小A还给出了价值a1,a2……an，表示划分后长度为i的子串价值为ai。小A希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？输入格式：第一行，一个正整数n，表示字符串的长度。第二行，一个包含n个小写字母的字符串s。第三行，n个正整数a1,a2……an，表示不同长度的子串价值。输出格式：一行，一个整数，表示划分后子串价值之和的最大值。数据范围：对于40%的测试点，保证1≤n≤103。对于所有测试点，保证1≤n≤105，1≤ai≤109。参考程序。#include<algorithm>#include<cstdio>#include<vector>usingnamespacestd;constintN=1e5+5;intn;chars[N];inta[N];longlongf[N];intmain(){scanf("%d",&n);scanf("%s",s+1);for(inti=1;i<=n;i++)scanf("%d",&a[i]);for(inti=1;i<=n;i++){intmask=0;for(intj=i;j;j--){intcur=1<<(s[j]-'a');if(mask&cur)break;mask|=cur;f[i]=max(f[i],f[j-1]+a[i-j+1]);}}printf("%lld\n",f[n]);return0;}解析：（1）动态规划定义——设f[i]为前i个字符（s[0…i-1]）的最大价值，目标是f[n]。（2）初始化：f[0]=0（空字符串价值为0）。（3）状态转移：对每个i（前i个字符），找到最大的左边界left，使得s[left…i-1]无重复字符（避免无效划分）。遍历j从left到i-1，f[i]=max(f[i],f[j-1]+a[i-j-1])（i-j是子串长度，对应价值a[i-j-1]）。27.试题名称：货物运输。时间限制：1.0s。内存限制：512.0MB。题目描述：A国有n座城市，依次以1,2……n编号，其中1号城市为首都。这n座城市由n-1条双向道路连接，第i条道路（1≤i<n）连接编号为ui,vi的两