2025年12月GESP认证C++八级真题(含答案和解析-在末尾)

2025年12月GESP认证C++八级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.某平台生成“取件码”由6个字符组成：前4位为数字（0-9），后2位为大写字母（A-Z），其中字母不能为I、O。假设数字和字母均可重复使用，要求整个取件码中恰好有2个数字为奇数。共有多少种不同取件码？（）。A.1,440,000B.2,160,000C.2,535,000D.8,640,0002.下列代码实现了归并排序（MergeSort）的分治部分。为了正确地将数组a的[left,right]区间进行排序，横线处应该填入的是（）。voidmerge_sort(inta[],intleft,intright){if(left>=right)return;intmid=(left+right)/2;merge_sort(a,left,mid);________;//在此处填入选项。merge(a,left,mid,right);//合并操作。}A.merge_sort(a,mid,right)B.merge_sort(a,mid+1,right)C.merge_sort(a,left,mid+1)D.merge_sort(a,mid-1,right)3.某社团有男生8人、女生7人。现需选出1名队长（性别不限）、1名副队长（性别不限）、2名宣传委员（两人无角色区别，且必须至少1名女生）。假如一人不能兼任多职，共有多少种不同选法？（）。A.12012B.11844C.12474D.110254.二项式(2x-y)8的展开式中x5y3项的系数为（）。A.-7168B.7168C.-1792D.17925.下面是使用邻接矩阵实现的Dijkstra算法的核心片段，用于求单源最短路径。在找到当前距离起点最近的顶点u后，需要更新其邻接点j的距离。横线处应填入的代码是（）。for(intj=1;j<=n;j++){if(!visited[j]&&graph[u][j]<INF){if(________){//在此处填入选项。dis[j]=dis[u]+graph[u][j];}}}A.dis[j]<dis[u]+graph[u][j]B.dis[j]>dis[u]+graph[u][j]C.graph[u][j]>dis[u]+dis[j]D.dis[j]>graph[u][j]6.下面程序使用动态规划求两个字符串的最长公共子序列（LCS）长度，横线处应填入的是（）。#include<algorithm>#include<string>#include<vector>usingnamespacestd;intlcs_len(conststring&a,conststring&b){intn=(int)a.size(),m=(int)b.size();vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1;else________;//在此处填入选项。returndp[n][m];}A.dp[i][j]=dp[i-1][j]+dp[i][j-1];B.dp[i][j]=min(dp[i-1][j],dp[i][j-1]);C.dp[i][j]=max(dp[i-1][j],dp[i][j-1]);D.dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1;7.已知两个点A(x1,y1)和B(x2,y2)在平面直角坐标系中的坐标。下列C++表达式中，能正确计算这两点之间直线距离的是（）。A.sqrt((x1-x2)^2+(y1-y2)^2)B.sqrt(pow(x1-x2,2)+pow(y1-y2,2))C.pow(x1-x2,2)+pow(y1-y2,2)D.abs(x1-x2)+abs(y1-y2)8.已知inta=10;执行int&b=a;b=20;后，变量a的值是（）。A.10B.20C.30D.编译错误9.下列代码的时间复杂度（以n为自变量，忽略常数与低阶项）是（）。longlongs=0;for(inti=1;i<=n;i++){for(intj=1;j*j<=i;j++){s+=j;}}10.下列程序实现了线性筛法（欧拉筛），用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（）。for(inti=2;i<=n;i++){if(!not_prime[i])primes[++cnt]=i;for(intj=1;j<=cnt&&i*primes[j]<=n;j++){not_prime[i*primes[j]]=true;if(________)break;//在此处填入选项。}}A.i+primes[j]==nB.primes[j]>iC.i%primes[j]==0D.i%primes[j]!=011.在C++语言中，关于类的继承和访问权限，下列说法正确的是（）。A.派生类可以访问基类的private成员。B.基类的protected成员在私有继承（privateinheritance）后，在派生类中变为public。C.派生类对象在创建时，会先调用基类的构造函数，再调用派生类自己的构造函数。D.派生类对象在销毁时，会先调用基类的析构函数，再调用派生类自己的析构函数。12.当输入6时，下列程序的输出结果为（）。#include<iostream>usingnamespacestd;intf(intn){if(n<=3)returnn;returnf(n-1)+f(n-2)+2*f(n-3);}intmain(){intn;cin>>n;cout<<f(n)<<endl;return0;}A.14B.27C.28D.1513.从1到999这999个正整数中，十进制表示中数字5恰好出现一次的数有多少个？（）。A.243B.271C.300D.33314.当输入2023时，下列程序的输出结果为（）。#include<iostream>usingnamespacestd;intmain(){intx,ans=0;cin>>x;while(x!=0){x-=x&-x;ans++;}cout<<ans<<endl;return0;}A.7B.8C.9D.1115.对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中，(u,v)已在同一连通块内。关于边e的处理，下列说法正确的是（）。A.必须选入MST，否则可能不连通。B.一定不能选入MST（在此扫描顺序下）。C.若后续出现更大的边权，可以回溯改选e。D.只有当e是当前最小边时才能舍弃。二、判断题（每题2分，共20分）。16.若一项任务可用两种互斥方案完成：方案A有m种做法，方案B有n种做法，则总做法数为m+n。（）。17.在C++语言中，引用一旦被初始化，就不能再改为引用另一个变量。（）。18.快速排序和归并排序的平均时间复杂度都是O(nlogn)，但快速排序是不稳定的排序算法，归并排序是稳定的排序算法。（）。19.使用math.h或cmath头文件中的函数，表达式sqrt(4)的结果类型为double。（）。20.在杨辉三角形中，第n行（从0开始计数，即第n行有n+1个数）的所有数字之和等于2n。（）。21.使用二叉堆优化的Dijkstra最短路算法，在某些特殊情况下时间复杂度不如朴素实现的O(v2)。（）。22.题n个不同元素依次入栈的出栈序列数与将n个不同元素划分成若干非空子集的方案数相等。（）。23.快速排序在最坏情况下的时间复杂度为O(nlogn)，可以通过随机化选择基准值（pivot）的方法完全避免退化。（）。24.在C++语言中，一个类可以拥有多个构造函数，也可以拥有多个析构函数。（）。25.求两个序列的最长公共子序列（LCS）时，使用滚动数组优化空间后，仍然可以还原出具体的LCS序列。（）。三、编程题（每题25分，共50分）。26.试题名称：猫和老鼠。时间限制：1.0s。内存限制：512.0MB。题目描述：猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2…n编号，结点i（1≤i≤n）有价值为ci的奶酪。在m条带权无向边中，第i（1≤i≤m）条无向边连接结点ui与结点vi，边权wi表示猫和老鼠通过这条边所需的时间。猫窝位于结点a，老鼠洞位于结点b。对于老鼠而言，结点u是安全的当且仅当——老鼠能规划一条从结点u出发逃往老鼠洞的路径，使得对于路径上任意结点x（包括结点u与老鼠洞）都有：猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。输入格式：第一行，两个正整数n，m分别表示图的结点数与边数。第二行，两个正整数a，b分别表示猫窝的结点编号，以及老鼠洞的结点编号。第三行，n个正整数c1,c2…cn，表示各个结点的奶酪价值。接下来m行中的第i行（1≤i≤m）包含三个正整数ui，vi，wi表示图中连接结点ui与结点vi的边，边权为wi。输出格式：输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。输入样例1。输出样例1。输入样例2。输出样例2。数据范围：对于40%的测试点，保证1≤n≤500，1≤m≤500。对于所有测试点，保证1≤n≤105，1≤m≤105，1≤a,b≤n且a≠b，1≤ui,vi≤n，1≤wi≤109。27.试题名称：宝石项链。时间限制：1.0s。内存限制：512.0MB。题目描述：小A有一串包含n枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以1,2…n编号，第n枚宝石与第1枚宝石相邻。项链由m种宝石组成，其中第i枚宝石种类为ti。小A想将宝石项链分给他的好朋友们。具体而言，小A会将项链划分为若干连续段，并且需要保证每段都包含全部m种宝石。请帮小A计算在满足条件的前提下，宝石项链最多可以划分为多少段。输入格式：第一行，两个正整数n，m分别表示宝石项链中的宝石的数量与种类数。第二行，n个正整数t1,t2…tn，表示每枚宝石的种类。输出格式：输出一行，一个整数，表示宝石项链最多可以划分的段数。输入样例1。输出样例1。输入样例2。输出样例2。数据范围：对于40%的测试点，保证2≤n≤100。对于所有测试点，保证2≤n≤105，2≤m≤n，1≤ti≤m，保证1,2…m均在t1,t2…tn中出现。答案和解析如下。1.答案：B。解析：两位字母各有24种选择，从4位数字选出2位作为奇数，有C(4,2)=6种选法，这两位奇数各有5种选择，再算上剩余两位偶数各有5种选择，那么一共有24x24x6x5x5x5x5=2160000种。2.答案：B。解析：[left,mid]的待排序区间变为[left,mid],[mid+1,right]的区间。3.答案：A。解析：先利用容斥原理算出选2名宣传委员的方法:"总方法数"-"没有女生的方法数"，即C(15,2)-C(8,2)=77种。剩下15-2=13人，分步骤选出一个队长、一个副队长，有13*12=156种选法,因此总共的方法数是77*156=12012种。4.答案：C。解析：y是三次项，意味着总共八项里面要有其中三项是选择y的，有C(8,3)=56种选法。然后再把C()前面系数进行计算:2是五次项，且每项前面是2，那么系数是25=32;y每项前面是-1，那么系数是(-1)3=-1。因此，答案是56*32*(-1)=-1792。5.答案：B。解析：三角形不等式,当点j的原本距离dis[j比"从点u经过边(u,j)过来"的距离dis[u]+graph[u][j],j更长时更新dis。6.答案：C。解析：状态表示：DP[i][j]:由A序列的前i个字母，且由B序列的前j个字母中构成的LCS的长度。状态转移方程。①若Ai和Bj都位于公共子序列中，则必须满足Ai==Bj,也就是A的第i个元素与B的最第j元素相同。那么，只需要找LCS(A[i-1],B[j-1])，结果为LCS(A[i-1],B[j-1])的长度+1。②若Ai和Bj至少有一个不位于公共子序列中：（1）LCS可以在(a1,a2,…a[i-1])和(b1,b2,b3…b[j])中找，记为LCS(A[i-1],B[j])。（2）LCS可以在(a1,a2,…ai)和(b1,b2,b3…b[j-i])中找，记为LCS(A[i],B[j-1])。（3）LCS可以在(a1,a2,…a[i-1])和(b1,b2,b3…b[j-1])中找，记为LCS(A[i-1],B[j-1])。第三个一定不优于前两个,当前情况记为:max(LCS(A[i-1],B[j]),LCS(A[i],B[j-1]))。目标状态:DP[n][m]答案选C。7.答案：B。解析：平面上两点A(1,91),B(2,y2)的直线距离公式为L²=(x1-x2)²+(y1-y2)²，其中开根号可以sqrt()函数表示，平方可用自乘或者pow(a,2)函数来表示。8.答案：B。解析：变量b是一个C++引用变量，修改b的同时也会对a进行同样的修改。9.答案：C。解析：第一层循环显然是O(n)的，主要看第二层循环。循环条件是j²<i，我们将两边都开平方后可以得到j<=sqrt(i)。i在最坏情况下的量级是O(n)的，因此第二层循环是O(sqrt(n))的时间复杂度，总时间复杂度是O(nsqrt(n))。10.答案：C。解析：欧拉线性筛法,当i%primes[j]==0时及时跳出循环，保证primes[j]更新的是以自身为最小质因子的数。11.答案：C。解析：A项，在C++中，基类的private成员只能被基类自己访问，派生类是无法直接访问的。这是由C++的访问控制规则决定的，目的是保证封装性。如果派生类需要访问基类成员，应该使用protected或pub1ic权限。B项，在私有继承中，基类的pub1ic和protected成员在派生类中都会变成private权限。所以，基类的protected成员在派生类中是private，而不是pub1ic。D项，析构函数的调用顺序与构造函数相反:先调用派生类自己的析构函数，然后才调用基类的析构函数(如果有多个基类，顺序按继承列表从右到左)。这是为了保证派生类资源先清理，再清理基类资源避免资源泄漏。12.答案：B。解析：这个递归函数显然可以利用递推的方式进行计算。f(1)=1,f(2)=2,f(3)=3。f(4)=f(3)+f(2)+2*f(1)=7。f(5)=f(4)+f(3)+2*f(2)=14。f(6)=f(5)+f(4)+2*f(3)=27。13.答案：A。解析：分成"5在百位"、"5在十位"、"5在个位"三种情况分别去计算。当"5在百位"，由于我们限定5是恰好出现一次的，因此十位和个位只能取除了5之外的九个数字，一共是9*9=81个数字。对于"5在十位"和"5在个位"的情况也是一样，各有81个数字。至此，一共有3*81=243个数字出现恰好一个5。14.答案：C。解析：x&-x为lowbit运算，相当于去除二进制x中最低位的1,ans统计的为1的数量。15.答案：B。解析：MST是指最小生成树，而一棵树显然不存在环。如果(u，2)已经在同一连通块内，那么说明(u,0)两点一定是联通的，即存在一条u-v的路径。如果再加入一条边(u,0)，那么这条边必然与原本u-v的路径形成了一个环，与生成树的定义相违背。16.答案：正确。解析：加法原理就是将一项任务的多种互斥方法数相加进行计算。17.答案：正确。解析：一个引用变量相当于是另一个变量的别名，直接修改这个引用变量会同时更改原本的变量。因此，它不能同时是多个变量的别名，不然就不知道对应要修改原本的哪个变量了。18.答案：正确。解析：不稳定排序算法有:希尔排序,选择排序,快速排序,堆排序,除此之外基于比较的排序算法为稳定算法,正确。19.答案：正确。解析：sqrt(x)函数在头文件cmath中，其作用是返回的平方根，返回值类型是double。20.答案：正确。解析：结合杨辉三角和二项式定理可以得到杨辉三角第n行的和为2n。21.答案：正确。解析：在稠密图(边≈点数²)时,朴素的复杂度优于堆优化Dijkstra。22.答案：错误。解析：第一个问题是卡特兰数，第二个问题是贝尔数，两者问题不同且结果不同。23.答案：错误。解析：快速排序在最坏情况下的时间复杂度是O(n²)，随机化选择基准值并不能完全避免退化。24.答案：错误。解析：一个类可以有多个构造函数(即构造函数重载)，根据参数列表的不同，可以定义不同的初始化方式。一个类只能有一个析构函数，析构函数没有参数、不能重载、也不能被显式调用，它的形式是固定的。25.答案：错误。解析：最长公共子序列[解析]在滚动数组的实现中，我们只保留最近两行的数据，历史信息会被覆盖。还原序列需要完整的dp表或方向信息来进行回溯。26.参考程序。#include<cstdio>#include<algorithm>#include<vector>#include<queue>usingnamespacestd;constintN=1e5+5;constlonglongoo=1e18;intn,m;inta,b;intc[N];vector<pair<int,int>>e[N];longlongdis[N];priority_queue<pair<longlong,int>>q;longlongans;intmain(){scanf("%d%d",&n,&m);scanf("%d%d",&a,&b);for(inti=1;i<=n;i++)scanf("%d",&c[i]);for(inti=1;i<=m;i++){intu,v,w;scanf("%d%d%d",&u,&v,&w);e[u].emplace_back(make_pair(v,w));e[v].emplace_back(make_pair(u,w));}for(inti=1;i<=n;i++)dis[i]=oo;dis[b]=0;q.push(make_pair(-dis[b],b));while(!q.empty()){autop=q.top();q.pop();if(dis[p.second]!=-p.first)continue;intu=p.second;for(autor:e[u]){intv=r.first,w=r.second;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push(make_pair(-dis[v],v));}}}for(inti=1;i<=n;i++)if(dis[i]<dis[a])ans+=c[i];printf("%lld\n",ans);return0;}解析：猫想抓到老鼠，则它必须在老鼠经过的某个结点y处，不晚于老鼠到达该结点。由于老鼠最终必然到达洞口，所以猫的最优策略就是守洞口。又因为是无向图，所以从猫窝到老鼠洞的距离等于从老鼠洞到猫窝的距离。所以，从b开始，做Dijkstra即可。27.参考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintL=20;constintN=2e5+5;constintoo=1e9;intn,m;intt[N],jump[L][N];intcnt[N],tot;inta