2026年3月GESP编程能力等级认证C++八级真题(含答案和解析)

2026年3月GESP编程能力等级认证C++八级真题(含答案和解析)一、单选题（每题2分，共30分）。1.某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（）种。A.112B.168C.224D.288答案：D。解析：总选法数为从14人中选3人：C(14,3)=364。减去全男生和全女生的情况：C(8,3)+C(6,3)=56+20=76。所以一共是:364-76=288种。2.在杨辉三角中，从第0行开始计数，第10行的所有数之和为（）。A.512B.1024C.2048D.4096答案：B。解析：杨辉三角第n行所有数之和为2ⁿ。因此第10行的和为：210=1024。3.下列代码实现了快速幂算法，其时间复杂度为（）。longlongfastPow(longlongb,longlonge,longlongmod){longlongresult=1;while(e>0){if(e&1)result=result*b%mod;b=b*b%mod;e>>=1;}returnresult;}A.O(logb)B.O(loge)C.O(logmod)D.O(e)答案：B。解析：快速幂每次循环都把指数e右移一位，因此循环次数是O(loge)。4.从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（）种。A.60B.74C.80D.84答案：C。解析：总选法为：C(9,3)=84。去掉3本全是物理书的情况：C(4,3)=4。所以答案为：84-4=80。5.在二叉搜索树（BST）中，若中序遍历的序列为{1,2,3,4,5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（）。A.该树一定是一棵完全二叉树B.元素4和5不可能是兄弟节点C.元素1所在节点的深度可能大于3（根节点深度为1）D.元素2一定是元素1的父节点答案：B。解析：先序遍历的开头为根，因此根是3，右子树只包含4和5。在BST里，右子树的中序必须还是4,5。这两个点只能形成一条链：要么4是5的父亲，要么5是4的父亲，不可能分居某个父节点的左右孩子，因此不可能是兄弟节点。6.在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（）。A.O(V2)B.O(V˙E)C.O((V+E)logV)D.O(V2logV)答案：C。解析：堆优化后,每个logv的复杂度得到某个点的最短路，配合邻接表，点和边都遍历一遍,总复杂度为O((V+E)logV)。7.对于含n个顶点（n≥2）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（）条边。A.nB.n-1C.n+1D.无法确定，取决于图的具体边数。答案：B。解析：无负环时，最短路为简单路径，每个点最多经过一次，最短路最多为n-1条边。8.在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(V3)。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组。如果此时继续对该dist数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist数组内的值（）。A.会发生改变，因为Floyd又做了一次松弛。B.不会发生改变C.可能变大，因为未针对已有最短路优化。D.可能在某些负权图中陷入死循环答案：B。解析：Floyd的每一步只是在尝dist[i][j]>dist[i][k]+dist[k][j],是否成立；现在dist[i][j]已经求得最短路，值已经固定，所以Floyd整轮跑完以后dist数组不变。9.关于图论中的最短路径算法，下列说法中严格正确的是（）。A.Dijkstra算法能够高效处理包含负权边的有向图。B.Floyd算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。C.单源最短路径算法无法用于无向图，无向图只能通过BFS求解。D.Dijkstra算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。答案：B。解析：Floyd可以处理负权边，只要图里没有负权环，因此B正确。A错在Dijkstra不能直接处理负权边。C错在单源最短路当然也能做无向图。DDijkstra每次取的是当前距离最近的未确定点。10.有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（）种。A.120B.144C.192D.240答案：C。解析：第一处：需要将基准值放到正确位置，即交换a[l]和a[j]（因为j是最后一个小于基准值的位置）,第二处：返回基准值的最终位置j。先把甲乙看成一个整体，并考虑内部顺序，共有2种。这样一共变成5个对象，排列数为：2×5!=240再减去丙站在排头的情况。此时剩下5人，其中甲乙仍要相邻，排法数为：2×4!=48。所以一共是:240-48=192。11.下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（）。voidfloyd(intn,intdist[][MAXN]){for(intk=0;k<n;k++)for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(__________)//在此处填入选项。dist[i][j]=dist[i][k]+dist[k][j];}A.dist[i][k]+dist[k][j]<dist[i][j]B.dist[i][k]!=INF&&dist[k][j]!=INFC.dist[i][k]!=INF&&dist[k][j]!=INF&&dist[i][k]+dist[k][j]<dist[i][j]D.dist[i][j]==INF答案：C。解析：只有当两段路径都存在，并且经过k后更短时，才应更新dist[i][j]。12.用数字0、1、2、3、4组成无重复数字的五位偶数，共有（）个。A.48B.60C.72D.96答案：B。解析：1.末位为0：前四位用1,2,3,4排列，共4!=24种。（2）末位为2或4：共2种选择。首位不能为0，从剩余4个数字中选首位有3种，其余3位全排列有3!=6种，共2×3×6=36种。总数为：24+36=60。13.在一个无向带权图中，若使用Prim算法从顶点0开始构造最小生成树（边权均为正整数，且graph[u][v]==0表示无边），下列代码中横线处应填入（）。intprim(vector<vector<int>>&graph,intn){vector<bool>inMST(n,false);vector<int>minEdge(n,INT_MAX);minEdge[0]=0;intresult=0;for(inti=0;i<n;i++){intu=-1;for(intj=0;j<n;j++)if(!inMST[j]&&(u==-1||minEdge[j]<minEdge[u]))u=j;inMST[u]=true;result+=minEdge[u];for(intv=0;v<n;v++)if(__________)//在此处填入选项。minEdge[v]=graph[u][v];}returnresult;}A.graph[u][v]&&!inMST[v]&&graph[u][v]<minEdge[v]B.!inMST[v]&&graph[u][v]<minEdge[v]C.graph[u][v]>0&&!inMST[v]D.!inMST[v]&&minEdge[v]>0答案：A。解析：因为θ表示无边，所以必须先保证graph[u][v]非零；同时v不能已在生成树中，而且新边权要更小。14.已知三个点A(x1,y1),B(x2,y2),C(x3,y3)在平面直角坐标系中的坐标。下列C++表达式中，在精度误差范围1e-8内能正确计算判断这三个点是三点共线的表达式是（）。A.(x2-x1)/(y2-y1)==(x3-x1)/(y3-y1)B.(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)==0C.fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))<1e-8D.fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1))<1e-8答案：C。解析：三点共线可通过二维叉积为0判断。考虑浮点误差，应使用绝对值小于某个容许误差的形式。A、D可能出现除零问题。15.在64位操作系统下（LP64/LLP64模型），下面代码的输出结果是（）。#include<iostream>usingnamespacestd;intmain(){inta[4]={1,2,3,4};int(*p)[4]=&a;int*q=a;cout<<sizeof(a)<<"";cout<<sizeof(p)<<"";cout<<sizeof(p+1)<<"";cout<<sizeof(q+1)<<"";cout<<(p+1)-p<<"";cout<<(q+1)-q<<endl;}A.1688811B.16816811C.1688441D.1688841答案：A。解析：a是4个int，总大小为16字节；p和q都是指针，64位下大小都为8字节；sizeof(p+1)、sizeof(q+1)依旧是指针大小8。指针相减得到跨过的元素个数，因此(p+1)-p=1，(q+1)-q=1。二、判断题（每题2分，共20分）。16.在C++中，若结构体中包含一个static成员变量，则该变量的存储空间属于结构体对象的一部分。（）。答案：错误。解析：static成员变量属于类或结构体本身，不属于某个对象实例的内部存储空间。17.对于任意正整数n，二项式(a+b)n展开式中各项的二项式系数之和等于2n。（）。答案：正确。解析：令a=1,b=1，则展开式系数和就是(1+1)ⁿ=2ⁿ。18.在C++中，若函数参数类型为constint&，则该参数既可以绑定左值，也可以绑定右值。（）。答案：正确。解析：常量左值引用既能绑定普通左值，也能绑定右值或临时对象。19.若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。（）。答案：错误。解析：边权有重复时，最小生成树仍可能唯一。比如本就是有相同边权的无向联通树。20.使用快速排序对n个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为O(nlogn)。（）。答案：错误。解析：快速排序的时间复杂度通常情况下是O(nlogn)，最差情况下会退化成O(n²)。21.若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。（）。答案：错误。解析：欧拉回路图必须是连通的。仅度数全为偶数不能保证联通(比如单独的点)。22.使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(nlogn)，查询的时间复杂度为O(1)。（）。答案：正确。解析：这是稀疏表（ST表）处理RMQ的经典复杂度。23.如果将一个连通无向图G1中所有边的权值都统一增加同一个正整数常数G，形成图G2。则G1的最小生成树中每条边在G2中对应的边组成的树，一定是G2的最小生成树。（）。答案：正确。解析：任意生成树都恰有n-1条边，统一加常数后每棵生成树总权值都增加相同的(n-1)c，相对大小不变，因此最小生成树保持不变。24.在图论算法中，Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（）。答案：正确。解析：最小生成树不唯一，不同算法可能求出不同的最小生成数，但它们的总边权和必定相同，否则与最小生成树定义中的“最小”相矛盾。25.在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。（）。答案：错误。解析：它们常常对应同一组状态，但复杂度可能存在区别（实现细节、访问状态范围、常数因素等都可能不同），特别是当状态转移方程中涉及的正反操作（例如：求倍数vs求因子）的时间复杂度不同的情况，时间复杂度可能差别巨大。三、编程题（每题25分，共50分）。26.试题名称：消息查找。时间限制：1.0s。内存限制：512.0MB。题目描述。小A的消息记录中有n条消息，依次以1,2，…，n编号。编号小的消息发送时间早于编号大的消息。一条消息可以引用一条编号小于它的消息，也可以不引用消息。小A注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是。（1）【消息1】小A：有人做了今天的第一题吗？（2）【消息2】小A：我第一题WA了，可能是什么原因？（3）【消息3：引用消息1】小B：我我我。（4）【消息4：引用消息2】小C：我也WA了。（5）【消息5：引用消息2】小B：是不是没开longlong？（6）【消息6：引用消息5】小A：改了就AC了，太厉害了！对于消息i（1≤i≤n），小A以ri标记消息i是否有引用，以及所引用的消息编号。如果ri>0，则消息i为引用了消息；如果ri=0，则消息i没有引用消息。消息记录里有非常多条消息。为了快速查找所需要的消息，小A准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息i（1≤i≤n），那么接下来可以选择以下两种操作之一。（1）定位到消息i-1。（2）如果消息i引用了消息ri，定位到消息ri。以上操作可以执行任意次（包括零次）。小A有q次询问。在第k（1≤k≤q）次询问中，小A给出消息编号xk,yk（yk<xk）。小A想知道，如果当前消息查找工具位于xk，至少需要多少次操作才能定位到消息yk。输入格式。第一行，两个正整数n，q，分别表示消息条数与询问次数。第二行，n个非负整数r1,r2,…rn，表示消息的引用关系，具体含义见题目描述。接下来q行中的第k行（1≤k≤q）包含两个正整数xk,yk，表示一次询问。保证至多只有1000条引用消息。输出格式。输出q行，每行一个整数，表示将界面从消息xk切换到消息yk所需的最少操作次数。输入样例1。输出样例1。输入样例2。输出样例2。数据范围。对于40%的测试点，保证1≤n≤2000，1≤q≤2000。对于所有测试点，保证1≤n≤105，1≤q≤105，0≤ri≤i，1≤yk<xk≤n，保证至多有1000条引用消息。参考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintN=1e5+5;constintC=2e3+5;constintoo=1e9;intn,q;intr[N],mark[N],pos[N];intp[C],cnt;intd[C][C];intpre[N],suf[N];intmain(){scanf("%d%d",&n,&q);for(inti=1;i<=n;i++){scanf("%d",&r[i]);if(r[i])mark[i]=mark[r[i]]=1;}for(inti=1;i<=n;i++)if(mark[i]){p[++cnt]=i;pos[i]=cnt;}for(inti=1;i<=cnt;i++){for(intj=1;j<=i;j++)d[i][j]=oo;d[i][i]=0;for(intj=i;j>1;j--){d[i][j-1]=min(d[i][j-1],d[i][j]+p[j]-p[j-1]);if(r[p[j]]){intk=pos[r[p[j]]];d[i][k]=min(d[i][k],d[i][j]+1);}}}for(inti=1;i<=n;i++){pre[i]=pre[i-1];if(mark[i])pre[i]=i;}suf[n+1]=n+1;for(inti=n;i;i--){suf[i]=suf[i+1];if(mark[i])suf[i]=i;}while(q--){intx,y;scanf("%d%d",&x,&y);if(pre[x]<suf[y])printf("%d\n",x-y);elseprintf("%d\n",x-pre[x]+d[pos[pre[x]]][pos[suf[y]]]+suf[y]-y);}return0;}解析：普通消息其实没什么可研究的，因为它只能老老实实往前走一步。真正会改变最短路的，只有两类消息：自己引用了别人，或者被别人引用过。只有走到这些位置，路径才有机会“抄近道”。题目保证这样的消息总数不多，所以参考程序先把它们全挑出来，当成关键点。后面真正预处理的，不是全部n条消息之间的关系，而是这些关键点之间的最短代价。设全部关键点按编号从小到大排成p1<p2<……<pc,程序里的p[i]就是这里的pi。接下来做一个预处理动态规划。它的目标是：对于每个起点关键点pi，求出走到更早关键点pj的最少操作数。把状态记为di,j，表示“当前从关键点pi出发，走到关键点pj的最少操作数”，其中1≤j≤i≤C。程序里的d[i][j]对应的就是这个量。初始状态很：di,i=0从pi到自己不需要操作。接下来按j=i,i-1,……2倒着转移。倒着枚举的原因是：操作只会让消息编号变小，所以从较大的关键点向前推，后继状态一定已经算过。对于当前状态di,j，只有两种决策。第一种决策：不用引用，直接一步一步往前退，直到前一个关键点pj-1。这中间没有别的关键点，所以必须走pj-pj-1步，转移方程是di,j-1=min(di,j-1,di,j+di,j+pj-pj-1)。第二种决策：如果消息pj本身引用了更早的消息，也就是rpi>0，那么可以直接用一次引用操作跳到消息rpi。由于被引用的消息也被算作关键点，设它在关键点序列中的下标是k，即pk=rpj，那么转移方程是：di,k=min(di,k,di,j+di,j+1)。这两类转移已经包含了所有可能操作，因为题目允许的动作只有“退到上一条消息”和“沿引用跳转”两种。于是，一轮预处理结束后，任意两个关键点之间的最少操作数就都求出来了。回答询问时，再把路径拆成三段看：（1）先从x一步一步退到左边最近的关键点pre[x]。（2）在关键点之间按预处理结果走到y右边最近的关键点suf[y]。（3）最后再一步一步退到y。如果记a=pre[x],b=suf[y],那么只要中间确实存在关键点可用，也就是a≥b，答案就是(x-a)+dpos(a),pos(b)+(b-y)。这里pos(a)表示关键点a在关键点序列里的下标，程序里用pos[a]保存。如果中间根本碰不到关键点，那就直接走x-y步，连预处理结果都用不上。设关键点个数是C，那么预处理规模主要是关键点之间的转移，复杂度大约是O(C2)；每次询问只需要代公式，时间是O(1)。这也是这题能在大数据范围下通过的原因。27.试题名称：子图最短路。时间限制：1.0s。内存限制：512.0MB。题目描述。给定包含n个结点m条边的带权无向图G，结点依次以1，2，…，n编号。第i（1≤i≤m）条边连接编号为ui与vi的两个结点，权值为Wi。对于指定的1≤t≤r≤n，按以下方式构造图G的子图G(t,r)。（1）保留G中编号在区间[t,r]中的结点。删去其它编号不在[t,r]中的结点以及与之相连的边。剩余的结点和边构成子图G(t,r)。对于G(t,r)中的任意结点u，v应有t≤u,v≤r。记u,v在子图G(t,r)上的最短距离为d(t,r,u,v)。特殊地，若u,v在子图G(t,r)上不连通，则认为d(t,r,u,v)=0。你需要求出t=1nr=tn输入格式。第一行，两个正整数n,m，表示结点数与边数。接下来m行，第i（1≤i≤m）行包含三个正整数ui,vi,wi，表示一条连接结点ui,vi的权值为wi的边。输出格式。输出一行，一个整数，表示t=1nr=tn输入样例1。输出样例1。输入样例2。输出样例2。数据范围。对于40%的测试点，保证2≤n≤20。对于所有测试点，保证2≤n≤100，2≤m≤n(n−1)2，1≤ui,vi≤n，1≤wi≤106。参考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintN=105;constintmod=1e9;intn,m;intf[N][N];intg[N][N];intans;intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)f[i][j]=mod;f[i][i]=