2026年6月GESP编程能力认证C++等级考试八级真题(含答案)

2026年6月GESP编程能力认证C++等级考试八级真题(含答案)一、单项选择题（共15题，每题2分，总计30分）1.某同学为求解小规模旅行商问题编写了如下C++代码片段，核心循环如下：for(intmask=0;mask<(1<<n);mask++){for(intu=0;u<n;u++){if(!(mask&(1<<u)))continue;for(intv=0;v<n;v++){if(mask&(1<<v))continue;}}不考虑常数优化，该算法的时间复杂度为（）A.O(n^3)B.O(n^2*2^n)C.O(n*2^n)D.O(2^n)2.使用Tarjan算法求解有向图强连通分量时，需要维护两个数组dfn和low，其中low[u]的准确含义是（）A.节点u在DFS遍历过程中的访问时间戳B.节点u所在强连通分量的节点总数C.节点u的DFS子树中，所有节点通过至多一条非树边能够到达的节点的最小dfn值D.节点u在DFS树中的深度3.使用矩阵快速幂求解k阶线性齐次递推数列的第n项（n可取到1e9级别），忽略矩阵维度带来的常数因子，算法的时间复杂度为（）A.O(n)B.O(logn)C.O(sqrt(n))D.O(1)4.使用树形DP求解“没有上司的舞会”问题，即树上每个节点有一个权值，相邻节点不能同时选取，求选取节点的最大权值和，定义dp[u][0]表示以u为根的子树中不选取u时的最大权值和，dp[u][1]表示选取u时的最大权值和，则dp[u][1]的正确转移方程是（）A.dp[u][1]=val[u]+Σmax(dp[v][0],dp[v][1])（v是u的所有子节点）B.dp[u][1]=val[u]+Σdp[v][0]（v是u的所有子节点）C.dp[u][1]=max(dp[v][0],dp[v][1])（v是u的所有子节点）D.dp[u][1]=val[u]+Σdp[v][1]（v是u的所有子节点）5.使用区间DP求解相邻石子合并的最小代价问题时，定义dp[i][j]为将第i堆到第j堆石子合并为一堆的最小代价，sum[i][j]为第i到j堆石子的总重量，则下列状态转移方程正确的是（）A.dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[i][j]（k遍历i到j-1）B.dp[i][j]=dp[i+1][j-1]+sum[i][j]C.dp[i][j]=max(dp[i][k]+dp[k+1][j])+sum[i][j]（k遍历i到j-1）D.dp[i][j]=dp[i][i]+dp[i+1][j]6.Kruskal算法求解无向连通图最小生成树的过程中，核心用到的数据结构是（）A.栈B.并查集C.优先队列D.线段树7.根据欧拉函数的定义，φ(18)的值为（）（欧拉函数φ(n)表示1到n中与n互质的正整数的个数）A.6B.9C.3D.128.下列关于拓扑排序的说法，正确的是（）A.有向图存在环时，仍然可以得到合法的拓扑排序结果B.拓扑排序结果中，任意一条有向边u→v的起点u一定排在终点v的前面C.任意有向无环图的拓扑排序结果是唯一的D.拓扑排序只能应用于边权为1的有向图9.常规算法竞赛环境下，单秒可完成约1e8次基本运算，若某状压DP算法的时间复杂度为O(n*2^n)，则n取以下哪个值时，算法的运算量在单秒时间限制内最稳妥（）A.20B.25C.30D.3510.下列关于Dijkstra单源最短路径算法的描述，错误的是（）A.堆优化的Dijkstra算法在边权为正的图中时间复杂度为O(mlogn)B.Dijkstra算法无法正确处理存在负权边的图的最短路径求解C.Dijkstra算法可以用于求解带负权环的图的最短路径D.朴素Dijkstra算法的时间复杂度为O(n²)，适用于稠密图11.若模数p=1e9+7（是质数），根据费马小定理，整数3在模p下的乘法逆元为（）A.333333336B.3C.0D.112.使用树上倍增法求解树的最近公共祖先（LCA）时，预处理每个节点向上走2^k步的祖先节点的时间复杂度为（）A.O(n)B.O(nlogn)C.O(logn)D.O(n²)13.若需要在C++中维护一个动态集合，支持插入任意整数、快速取出集合中的最大值、删除最大值，要求平均单次操作的时间复杂度为O(logn)，下列STL容器中最适合直接使用的是（）A.vectorB.priority_queue<int>C.listD.deque14.一个包含n个节点的有向图是强连通图的充要条件是（）A.任意两个节点之间至少存在一条单向可达的路径B.从任意节点出发可以到达所有其他节点C.图中不存在环D.图的边数大于等于n-115.使用区间DP求解最长回文子序列长度问题时，算法的时间复杂度为（）A.O(n^3)B.O(n^2)C.O(nlogn)D.O(2^n)二、判断题（共10题，每题2分，总计20分）1.使用Kruskal算法求解最小生成树时，将所有边按权值从大到小排序后依次加边，通过并查集避免环，最终得到的生成树是最小生成树。（）2.对于质数模数p，任意不被p整除的整数a都存在模p下的乘法逆元，可以通过费马小定理用快速幂求解，时间复杂度为O(logp)。（）3.任意有向无环图的拓扑排序结果都是唯一的。（）4.求解树的直径时，两次深度优先搜索的方法仅适用于所有边权非负的树，而树形DP方法可以正确处理存在负权边的树的直径求解。（）5.Tarjan算法求解无向图割点时，若DFS树的根节点拥有至少2个不同的子树，则该根节点一定是割点。（）6.n个节点的无向完全图的生成树数量为n^(n-2)（Cayley公式）。（）7.当n=20时，时间复杂度为O(n²*2^n)的状压DP算法在单秒时间限制下可以无压力通过。（）8.Bellman-Ford算法求解单源最短路径时，若经过n-1轮松弛操作后，仍然存在可以松弛的边，则说明图中存在从源点可达的负权环。（）9.并查集数据结构同时使用路径压缩和按秩合并优化时，单次查找操作的平均时间复杂度为反阿克曼函数级别，可近似认为是常数时间。（）10.Floyd算法求解任意两点间最短路径的时间复杂度为O(n^3)，可以处理存在负权边但无负权环的图。（）三、编程题（共2题，每题25分，总计50分）1.DAG最短路径计数题目描述：给定一个有n个节点、m条边的有向无环图，节点编号从1到n，所有边的权值均为正整数。请你计算从节点1出发到节点n的最短路径长度，以及长度等于最短路径的不同路径的数量，结果对1000000007取模。注：两条路径不同当且仅当经过的边序列不同，题目保证图中从节点1可以到达节点n。输入格式：第一行输入两个正整数n,m（1≤n≤10000，1≤m≤100000），分别表示节点数和边数。接下来m行，每行输入三个正整数u,v,w（1≤u,v≤n，1≤w≤1000），表示存在一条从u指向v、权值为w的有向边。输出格式：输出一行两个整数，第一个整数表示从1到n的最短路径长度，第二个整数表示最短路径的数量模1000000007的结果。样例输入：44121132243343样例输出：412.旅行商最短环游题目描述：有n个城市，编号从0到n-1，任意两个城市之间都有双向道路直达，给定城市之间的道路长度。一个旅行商从城市0出发，需要经过每个城市恰好一次，最后返回城市0，请问他需要走的最短总路程是多少。输入格式：第一行输入一个正整数n（1≤n≤16），表示城市数量。接下来n行，每行输入n个非负整数dist[i][j]（0≤dist[i][j]≤1000），表示城市i到城市j的道路长度，保证dist[i][j]=dist[j][i]，dist[i][i]=0。输出格式：输出一个整数，表示旅行商完成环游的最短总路程。样例输入：40133104234013210样例输出：7参考答案及解析一、单项选择题答案与解析1.答案：B解析：代码中第一层循环枚举所有状态mask，共有2^n个不同的状态；第二层循环枚举当前所在节点u，共n个取值；第三层循环枚举下一个要到达的节点v，共n个取值。三层循环的总运算量级为n*n*2^n=n²·2^n，因此时间复杂度为O(n²·2^n)。2.答案：C解析：dfn数组存储节点u在DFS遍历中的访问时间戳；low数组存储u的DFS子树中所有节点，通过至多一条反向回边（非树边）能够到达的节点的最小dfn值，是Tarjan算法判定强连通分量、割点、桥的核心依据。3.答案：B解析：k阶线性递推可以构造大小为k*k的转移矩阵，通过快速幂将n次转移拆解为logn次矩阵乘法，当k为固定常数时，矩阵乘法的耗时为常数，因此整体时间复杂度为O(logn)，可高效求解n为1e9级别的递推项。4.答案：B解析：当节点u被选取时，其所有直接相邻的子节点都不能被选取，因此每个子树只能贡献不选子节点时的最大权值dp[v][0]，累加所有子树的结果后加上u自身的权值，即为dp[u][1]的取值。选项A是dp[u][0]的转移方程，即不选u时子节点可选可不选，取每个子节点两种状态的最大值。5.答案：A解析：相邻石子合并时，合并区间[i,j]必须先将其拆分为两个相邻的子区间[i,k]和[k+1,j]分别合并，再将两堆合并为一堆，本次合并的代价为区间[i,j]的石子总重量sum[i][j]，需要枚举所有合法分割点k取最小代价值。选项C取最大值对应最大合并代价问题，其余选项的转移逻辑不符合石子合并的规则。6.答案：B解析：Kruskal算法的核心流程是将所有边按权值从小到大排序，依次尝试加入边，若边的两个端点属于不同连通分量则将边加入生成树、合并两个连通分量，该过程需要并查集支持近常数时间的连通性查询与合并操作。7.答案：A解析：欧拉函数的计算公式为φ(n)=n*Π(1-1/p)，其中p是n的所有不同质因数。18的质因数为2和3，因此φ(18)=18*(1-1/2)*(1-1/3)=6，对应1到18中与18互质的数为1、5、7、11、13、17，共6个。8.答案：B解析：拓扑排序是有向无环图的节点线性排列，满足任意有向边u→v的起点u一定排在终点v之前；存在环的有向图无法得到合法拓扑序；当图中存在多个入度为0的节点时，拓扑排序结果不唯一；拓扑排序的过程仅与边的方向有关，与边权无关联。9.答案：A解析：代入计算各选项的运算量：n=20时，n*2^n=20*1048576≈2e7，远低于单秒1e8次运算的阈值，可以稳定通过；n=25时运算量为25*33554432≈8.4e8，超出单秒负载；n=30、35时运算量呈指数增长，完全无法在单秒内完成。10.答案：C解析：Dijkstra算法基于贪心策略，每次选取当前已知距离最小的未访问节点进行松弛，节点一旦被选中就不再更新其最短距离，因此无法处理存在负权边的图，更无法处理带有负权环的图（负权环不存在有限最短路径）；堆优化Dijkstra复杂度为O(mlogn)，朴素Dijkstra复杂度为O(n²)，适合稠密图场景。11.答案：A解析：质数模下，a的乘法逆元为满足a*x≡1modp的x值，根据费马小定理x=a^(p-2)modp。代入a=3、p=1e9+7计算可得x=333333336，验证：3*333333336=1000000008，模1e9+7的结果为1，符合逆元定义。12.答案：B解析：树上倍增法需要预处理每个节点向上走2^0、2^1……2^logn步的祖先节点，每个节点需要存储logn个祖先信息，因此总预处理时间复杂度为O(nlogn)，单次LCA查询的时间复杂度为O(logn)。13.答案：B解析：C++STL中的priority_queue默认是大根堆实现的优先队列，支持O(logn)时间插入元素、O(1)时间获取堆顶最大值、O(logn)时间删除堆顶元素，符合题目要求；vector、list、deque均为线性序列结构，无法直接高效获取最大值。14.答案：B解析：强连通图的定义是任意两个节点u、v之间，既存在u到v的路径，也存在v到u的路径，等价于从任意节点出发都可以到达所有其他节点；选项A仅保证单向可达，不满足强连通要求；无环的有向图是有向无环图，不可能强连通；n-1条边的有向图若为树形结构，无法形成强连通。15.答案：B解析：最长回文子序列的区间DP状态dp[i][j]表示子串s[i..j]的最长回文子序列长度，转移时仅需判断s[i]与s[j]是否相等：若相等则dp[i][j]=dp[i+1][j-1]+2，否则dp[i][j]=max(dp[i+1][j],dp[i][j-1])，无需枚举区间分割点，因此仅需两层循环枚举区间长度和起点，时间复杂度为O(n²)。二、判断题答案与解析1.答案：错误解析：Kruskal算法求解最小生成树需要将边按权值从小到大排序，每次选取不形成环的最小权边加入生成树；若从大到小排序加边，得到的是最大生成树，而非最小生成树。2.答案：正确解析：质数模数下，所有不被p整除的整数都与p互质，因此存在唯一的乘法逆元；根据费马小定理a^(p-1)≡1modp，可得逆元为a^(p-2)modp，通过快速幂求解的时间复杂度为O(logp)。3.答案：错误解析：当有向无环图中存在多个入度为0的节点时，这些节点在拓扑序中的相对顺序可以任意调整，因此拓扑排序结果不一定唯一。4.答案：正确解析：两次DFS求解直径的贪心策略为：从任意点出发找最远点u，再从u出发找最远点v，u到v的路径即为直径，该策略的正确性依赖边权非负的条件，若存在负权边，第一次找到的最远点不一定是直径端点；树形DP通过记录每个节点向下的最长、次长路径进行转移，不受边权正负影响，可以正确计算含负权边的树的直径。5.答案：正确解析：无向图中，若DFS树的根节点存在2个及以上独立子树，删除根节点后这些子树会分裂为互不连通的独立分量，因此根节点一定是割点。6.答案：正确解析：Cayley公式是图论中的经典结论，指出n个带标号节点构成的无向完全图中，共存在n^(n-2)棵不同的生成树。7.答案：错误解析：n=20时，n²*2^n=400*1048576≈4.2e8次运算，超过常规单秒1e8次运算的负载阈值，若无额外优化无法在单秒内稳定通过。8.答案：正确解析：不存在负权环的图中，任意两点间的最短路径最多包含n-1条边，因此经过n-1轮松弛后所有节点的最短距离会收敛；若n-1轮松弛后仍存在可松弛的边，说明存在从源点可达的负权环，可以无限绕环缩短路径长度。9.答案：正确解析：路径压缩优化将查找路径上的节点直接指向根节点，按秩合并将小树合并到大树上避免树结构退化，两种优化结合后，单次操作的时间复杂度为反阿克曼函数α(n)，其增长速度极慢，对于常规算法竞赛的数据范围可近似为常数时间。10.答案：正确解析：Floyd算法基于动态规划思想，通过枚举中间节点松弛所有点对的路径，时间复杂度为O(n³)，只要图中不存在负权环，即使存在负权边也可以正确计算所有点对的最短路径。三、编程题参考解析与代码1.DAG最短路径计数解题思路：由于图是有向无环图，可先通过拓扑排序得到节点的线性处理顺序，保证处理任意节点u时，所有能到达u的前驱节点的最短路径都已计算完成。维护两个数组：dis[u]存储节点1到u的最短路径长度，初始化为无穷大，dis[1]=0；cnt[u]存储节点1到u的最短路径数量，初始化为0，cnt[1]=1。按照拓扑序遍历每个节点u，遍历u的所有出边u→v（权值w）：若dis[v]>dis[u]+w，说明找到更短的路径，更新dis[v]为dis[u]+w，同时将cnt[v]设为cnt[u]；若dis[v]==dis[u]+w，说明找到等长的最短路径，将cnt[v]累加cnt[u]并对1e9+7取模。该算法时间复杂度为O(n+m)，可满足题目数据范围要求。参考代码：usingnamespacestd;constintMOD=1000000007;constintINF=0x3f3f3f3f;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<vector<pair<int,int>>>g(n+1);vector<int>in_deg(n+1,0);for(inti=0;i<m;i++){intu,v,w;cin>>u>>v>>w;g[u].emplace_back(v,w);in_deg[v]++;}queue<int>q;vector<int>topo;for(inti=1;i<=n;i++){if(in_deg[i]==0)q.push(i);}while(!q.empty()){intu=q.front();q.pop();topo.push_back(u);for(auto&e:g[u]){intv=e.first;if(--in_deg[v]==0)q.push(v);}}vector<int>dis(n+1,INF);vect