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

2024年3月GESP编程能力认证C++等级考试六级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.在构建哈夫曼树时，每次应该选择（）合并。A.最小权值的节点B.最大权值的节点C.随机节点D.深度最深的节点2.面向对象的编程思想主要包括以下哪些原则（）？A.贪心、动态规划、回溯。B.并发、并行、异步。C.递归、循环、分治。D.封装、继承、多态。3.在队列中，元素的添加和删除是按照（）原则进行的。A.先进先出B.先进后出C.最小值先出D.随机进出4.给定一个简单的类定义如下，（）语句在类的外部正确地创建了一个Circle对象并调用了getArea函数？classCircle{private:doubleradius;public:Circle(doubler):radius(r){}doublegetArea(){return3.14*radius*radius;}};A.Circlec=Circle(5.0);c.getArea(c);B.Circlec(5.0);getArea(c);C.Circlec=newCircle(5.0);c.getArea();D.Circlec(5.0);c.getArea();5.以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（），使其能正确实现相应功能。TreeNode*search(TreeNode*root,inttarget){if(root==NULL||root->val==target){returnroot;}if(_______________){returnsearch(root->left,target);}else{returnsearch(root->right,target);}}A.target<root->leftB.target<root->valC.target>root->valD.target>root->left6.题3位格雷编码的正确顺序是（）。A.000,001,010,011,100,101,110,111B.000,001,011,010,110,111,101,100C.000,010,001,011,100,110,101,111D.000,010,110,100,111,101,011,0017.以下动态规划算法的含义与目的是（）。intfunction(vector<int>&nums){intn=nums.size();if(n==0)return0;if(n==1)returnnums[0];vector<int>dp(n,0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(inti=2;i<n;++i){dp[i]=max(dp[i-1],nums[i]+dp[i-2]);}returndp[n-1];}A.计算数组nums中的所有元素的和B.计算数组nums中相邻元素的最大和C.计算数组nums中不相邻元素的最大和D.计算数组nums中的最小元素8.阅读以下广度优先搜索的代码，使用以上算法遍历以下这棵树，可能的输出是（）。voidbfs(TreeNode*root){if(root==NULL){return;}queue<TreeNode*>q;q.push(root);while(!q.empty()){TreeNode*current=q.front();q.pop();cout<<current->val<<"";if(current->left){q.push(current->left);}if(current->right){q.push(current->right);}}}A.1289453671011B.1234567891011C.1238964571011D.12389456710119.给定一个空栈，执行以下操作序列，push(1),push(2),push(3),pop(),pop(),push(4),push(5),pop()，最终栈中的元素是（）。A.1,2B.1,4,5C.1,2,5D.1,410.一个有124个叶子节点的完全二叉树，最多有（）个结点。A.247B.248C.249D.25011.在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（）。A.重叠子问题B.分治法C.贪心策略D.回溯算法12.若一棵二叉树的先序遍历为A,B,D,E,C,F，中序遍历为D,B,E,A,F,C，它的后序遍历为（）。A.D,E,B,F,C,AB.E,D,B,F,C,AC.D,E,B,C,F,AD.E,D,B,C,F,A13.线性筛法与埃氏筛法相比的优势是（）。A.更容易实现B.更节省内存C.更快速D.更准确14.以下代码使用了辗转相除法求解最大公因数，请在横线处填入（），使其能正确实现相应功能。intgcd(inta,intb){while(b!=0){______________________}returna;}A.inttemp=b;b=a/b;a=temp;B.inttemp=a;a=b/a;b=temp;C.inttemp=b;b=a%b;a=temp;D.b=a%b;a=b;15.下面的代码片段用于反转单链表，请进行（）修改，使其能正确实现相应功能。ListNode*reverseLinkedList(ListNode*head){ListNode*prev=nullptr;ListNode*current=head;while(current!=nullptr){ListNode*next=current->next;current->next=next;prev=current;current=next;}returnprev;}A.current->next=next;应该改为current->next=prev;B.ListNode*next=current->next;应该改为ListNode*next=prev->next;C.current!=nullptr应该改为current->next!=nullptrD.ListNode*prev=nullptr;应该改为ListNode*prev=head;二、判断题（每题2分，共20分）。16.哈夫曼树是一种二叉树。（）。A.正确B.错误17.在动态规划中，状态转移方程的作用是定义状态之间的关系。（）。A.正确B.错误18.继承是将已有类的属性和方法引入新类的过程。（）。A.正确B.错误19.完全二叉树的任意一层都可以不满。（）。A.正确B.错误20.删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。（）。A.正确B.错误21.在宽度优先搜索中，通常使用队列来辅助实现。（）。A.正确B.错误22.哈夫曼编码的主要应用领域是有损数据压缩。（）。A.正确B.错误23.二叉搜索树的查找操作的时间复杂度是O(N)。（）。A.正确B.错误24.栈的基本操作包括入栈（push）和出栈（pop）。（）。A.正确B.错误25.使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。（）。A.正确B.错误三、编程题（每题25分，共50分）。26.试题名称：游戏。题面描述：你有四个正整数n，a，b，c，并准备用它们玩一个简单的小游戏。在一轮游戏操作中，你可以选择将n减去a，或是将n减去b。游戏将会进行多轮操作，直到当n≤c时游戏结束。你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n减去a，而另一种操作序列选择将n减去b。如果a=b，也认为将n减去a与将n减去b是不同的操作。由于答案可能很大，你只需要求出答案对1000000007取模的结果。输入格式：一行四个正整数n，a，b，c。保证1≤a，b，c≤n。输出格式：一行一个整数，表示不同的游戏操作序列数量对1000000007取模的结果。数据范围：对于20的测试点，保证a=b=c=1，n≤30。对于40的测试点，保证c=1，n<103。对于所有测试点，保证1≤n≤2×105。27.试题名称：好斗的牛。问题描述：你有109个牛棚，从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第i头牛的攻击范围是(ai，bi)，这意味着，如果他的左边ai个牛棚或右边bi个牛棚里有其他牛，他就会去挑事。你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里，且没有牛会挑事。输入描述：第一行1个正整数N。接下来一行N个用空格隔开的正整数a1…aN。接下来一行N个用空格隔开的正整数b1…bN。输出描述：输出一行一个整数，表示你最少需要留下多少牛棚。特别提醒：在常规程序中，输入和输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入和输出中附带任何提示信息。样例解释1：你可以留下4个牛棚，并如此安排你的牛。数据规模：对于20的测试点，保证N=2。对于另外20的测试点，保证N=3。对于80的测试点，保证N≤8。对于所有测试点，保证N≤9，ai，bi≤1000。答案解析如下。1.答案：A。解析：根据哈夫曼树的定义——带权路径长度最小。可得权值越大的点离根越近，权值越小的离根越远，故每次拿两个权值最小的节点合并。2.答案：D。解析：面向对象类的三大特性分别为——封装、继承、多态。3.答案：A。解析：队列是一个元素具有先进先出限制的线性表。4.答案：D。解析：getArea是Circle的一个成员函数，且参数表为空，故调用语句应为c.getArea()；创建Circle对象c的语句中，Circlec(5.0);和Circlec=Circle(5.0);是正确的；Circlec=newCircle(5.0);错误的原因是new语句的返回值Circle*，而不是Circle。5.答案：B。解析：二叉排序树中，左子树的元素小于根，由于第6行中代码表示访问左子树，故第5行应为判断目标元素是否小于根节点元素。6.答案：B。解析：格雷码中相邻两个编码只有刚好一位不同。7.答案：C。解析：在第11行的转移方程中，dp[i-1]代表不取用nums[i]的情况，而nums[i]+dp[i-2]表示取用nums[i]的情况，且可以发现此时nums[i-1]一定不为和的一部分，故选C。8.答案：C。解析：代码为广度优先搜索，且从根节点1开始搜索，故输出顺序中节点的深度一定单调递增。9.答案：D。解析：对栈操作进行手动模拟。每一步之后栈内从底到顶的元素分别为：1；1,2；1,2,3；1,2；1；1,4；1,4,5；1,4。10.答案：B。解析：假设二叉树内儿子个数为0,1,2的节点个数分别为n0,n1,n2；则有n2=n0-1。且由于该树为完全二叉树，则n1只能为0或者1。此题中n0=124，所以树上节点的最多个数为124+1+123=248。11.答案：A。解析：最优化问题的两个重要性质为最优子结构和重叠子问题。因为在DP转态转移的过程中，需要多次取出同一个子问题的答案。12.答案：A。解析：对于还原二叉树的算法，首先从先/后序遍历取出根，然后从中序遍历中求出左右子树的大小，由此得到左右子树的先/后序遍历和中序遍历，整体上是一个递归过程。13.答案：C。解析：线性筛法的时间复杂度关于问题规模n呈线性O(n)；但是埃氏筛法的复杂度为O(nlogn)。14.答案：C。解析：gcd(a,b)=gcd(b,a%b)。只有C选项可以正确地进行赋值。15.答案：A。解析：prev在代码中一直指的是原单链表中元素current的上一个元素，所以current->next应该赋值为prev。16.答案：正确。解析：无。17.答案：正确。解析：无。18.答案：正确。解析：无。19.答案：错误。解析：只有最深的那一层可以不满。20.答案：错误。解析：删除当前节点，需要将其前一个节点的next指向当前节点的next节点。21.答案：正确。解析：宽度优先搜索的过程刚好符合队列的特性，故可以使用队列辅助实现。22.答案：错误。解析：哈夫曼编码是根据字符出现频率来编码的，并不主要用于有损的数据中。23.答案：错误。解析：二叉排序树的查找操作的时间复杂度跟树的深度直接相关，一般认为二叉排序树的平均深度为O(logn)级别。24.答案：正确。解析：无。25.答案：错误。解析：根据哈夫曼编码的构造方式，两个字符的频率差异最大，长度差距也会最大，若它们的编码出现了相同的前缀，说明所有字符的编码都会有同样的非空前缀，此时可以考虑删除这个前缀使得各字符所对应的编码长度更短（这里不考虑前缀为空的情况，不然无论如何都会有前缀了）。26.参考程序。#include<cstdio>usingnamespacestd;constintN=2e5+5;constintmod=1e9+7;intn,a,b,c;intf[N<<1];intans;intmain(){scanf("%d%d%d%d",&n,&a,&b,&c);f[N+n]=1;for(inti=n;i>c;i--){f[N+i-a]=(f[N+i-a]+f[N+i])%mod;f[N+i-b]=(f[N+i-b]+f[N+i])%mod;}for(inti=0;i<=N+c;i++)ans=(ans+f[i])%mod;printf("%d\n",ans);return0;}解析：可以定义f[i]为在游戏中出现i这个数字时不同的操作序列个数。有。递推式：f[i]=f[i+a]+f[i+b]。边界条件：f[n]=1。【答案】f[c]+f[c-1]+f[c-2]+…+f[c-b+1]。由于答案中的下标可能会出现负数，在代码实现时可以将数组改为map或者将数组下标整体调大（可以看一下参考程序，参考程序中的f[N+i]可以和思路内的f[i]对应）。27.参考程序。#include<iostream>#include<vector>#include<algorithm>using