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

2026年6月GESP编程能力认证C++等级考试七级真题(含答案)单项选择题（每题2分，共20道，合计40分）1.某算法的核心逻辑如下，n为正整数，该算法的时间复杂度为（）```cppintres=0;for(inti=1;i<=n;i++){for(intj=i;j<=n;j+=i){for(intk=0;k<n;k++){res++;}}}cout<<res;```A.O(n³)B.O(n²logn)C.O(n²)D.O(nlog²n)2.对于一个包含1000个节点、10000条边的无向无权图，若要频繁查询任意两个节点之间的最短路径长度，以下存储结构和算法组合中效率最优的是（）A.邻接矩阵存储+Floyd算法预处理全源最短路径B.邻接表存储+对每个节点单独执行Dijkstra算法C.邻接矩阵存储+对每个节点单独执行BFS预处理D.邻接表存储+SPFA算法针对每个节点计算最短路径3.下列关于Dijkstra算法的描述中，错误的是（）A.传统的暴力实现Dijkstra算法时间复杂度为O(N²)，适合节点数较少的稠密图B.堆优化的Dijkstra算法可以在边数远小于节点数平方的稀疏图中获得远高于暴力实现的效率C.Dijkstra算法天然支持边权为负数的场景，只要图中不存在负环即可得到正确结果D.若图中所有边的边权为正，Dijkstra算法可以保证第一次弹出目标节点的堆顶元素时，就已经得到了起点到该节点的最短路径4.下列关于无向图最小生成树（MST）的性质描述中，正确的是（）A.任意一个无向连通图的最小生成树一定是唯一的B.若图中所有边的边权互不相同，则该图的最小生成树一定唯一C.同一个无向连通图的所有不同最小生成树，边权的总和一定完全相同，但边权的集合一定互不相同D.最小生成树包含图中任意两个节点之间的最短路径5.01背包问题的空间优化实现中，遍历背包容量时需要从大到小逆序遍历，该操作的核心目的是（）A.减少遍历的总次数，降低时间复杂度B.保证每件物品只会被选择一次，避免同一物品被重复累加计入背包价值C.防止数组下标越界D.让状态转移的计算顺序符合“后续状态不会修改当前轮次的前置状态”的要求，保证滚动数组的正确性6.C++STL中的priority_queue优先队列默认底层实现采用的容器和堆结构类型分别是（）A.vector、小顶堆B.deque、小顶堆C.vector、大顶堆D.list、大顶堆7.Floyd算法求多源最短路径的经典三维实现中，定义dist[k][i][j]的含义是“节点i到节点j的最短路径上，所有中间节点的编号都不超过k”，若要将空间复杂度从O(N³)优化为O(N²)，核心的操作是（）A.按照k从大到小的顺序遍历覆盖二维dist数组B.按照k从小到大的顺序遍历覆盖二维dist数组，保证计算dist[i][j]时用到的dist[i][k]和dist[k][j]都是上一轮k-1迭代的结果C.直接去掉第一维，任意顺序遍历所有节点即可得到正确结果D.对所有边执行松弛操作N轮，不需要按节点顺序遍历8.KMP字符串匹配算法中，预处理模式串next数组的时间复杂度和整体完成一次主串与模式串匹配的总时间复杂度分别是（主串长度为n，模式串长度为m）（）A.O(m)、O(n+m)B.O(n)、O(nm)C.O(m²)、O(nm)D.O(n)、O(n+m)9.Tarjan算法求解有向图的强连通分量时，dfn数组和low数组的正确含义是（）A.dfn[x]表示节点x到起点的最短距离，low[x]表示节点x能到达的最小节点编号B.dfn[x]表示节点x在深度优先搜索过程中被第一次访问的时间戳，low[x]表示节点x或其后代节点能够通过非回溯边到达的栈中节点的最小dfn值C.dfn[x]表示节点x的入度大小，low[x]表示节点x的出度大小D.dfn[x]表示节点x所在强连通分量的总节点数，low[x]表示该强连通分量中编号最小的节点10.对于一棵节点总数为N的普通二叉树，采用深度优先遍历实现树形动态规划求解所有节点的最大独立集（选中的任意两个节点不直接相邻的最大权值和），该算法的时间复杂度为（）A.O(N²)B.O(NlogN)C.O(N)D.O(logN)判断题（每题2分，共10道，合计20分）1.SPFA算法是基于队列优化的Bellman-Ford算法，可以处理所有带负权边的图的单源最短路径计算，即使图中包含负环也能得到正确结果。（）2.Kruskal算法求解最小生成树的核心步骤是将所有边按边权从小到大排序，之后依次尝试加入并查集判断是否连通，其整体时间复杂度为O(ElogE)，主要开销来自边的排序操作。（）3.动态规划算法求解问题的核心前提是问题的状态必须满足无后效性，即某个状态一旦被确定，其后续的状态转移过程不会影响已经确定的前置状态的取值。（）4.对于n个节点的完全无向图，采用邻接表进行存储时，总的存储空间复杂度为O(n)。（）5.C++STL中的std::map容器底层采用红黑树实现，所有元素按照键值自动排序，单次插入、删除、查询操作的时间复杂度均为O(logK)，其中K为容器中已存储的元素总个数。（）6.任意一个无向图，只要节点数大于等于2，就一定存在至少一棵最小生成树。（）7.朴素实现的多重背包问题时间复杂度为O(N*K*S)，其中N为物品总数，K为背包容量，S为单类物品的最大可用数量，采用二进制拆分将每类物品拆分为若干01背包物品之后，可将时间复杂度优化为O(N*K*logS)，在大部分场景下计算效率获得明显提升。（）8.采用斐波那契堆作为优先队列实现的Dijkstra算法，其理论时间复杂度可以达到O(M+NlogN)，其中M为图的总边数，N为节点总数。（）9.Tarjan算法求解无向图的割点时，根节点的判定规则与非根节点完全一致，只要满足low[v]>=dfn[u]就可以判定u是割点，不需要统计根节点的子树数量。（）10.对有向无环图执行拓扑排序操作的过程中，若最终得到的拓扑序列长度小于图的总节点数，则可以判定该图中一定存在至少一个有向环。（）编程题（每题30分，合计60分）编程题1：城市通勤优化【题目背景】小杨居住在A市，A市的公共交通系统共有n个站点，编号从1到n，站点之间共有m条单向行驶的公交线路，每条公交线路连接两个不同的站点u和v，乘坐这条线路需要花费w元。小杨现在从站点s出发，想要前往站点t，他的交通卡提供一次特殊福利：在整个行程中，他可以选择任意一条公交线路免费乘坐一次，不需要支付该线路对应的费用。请你帮小杨计算，他从站点s到达站点t所需要的最小花费是多少。【输入格式】第一行四个正整数n、m、s、t，分别代表站点总数、公交线路总数、起点站点编号、终点站点编号。接下来m行，每行三个正整数u、v、w，代表存在一条从u指向v的单向公交线路，乘坐费用为w。【输出格式】输出一个整数，代表小杨从s到t的最小花费。数据保证至少存在一条路径可以从s到达t。【样例输入1】5615122233351134257451【样例输出1】3【数据范围】对于30%的测试点，n<=100，m<=1000；对于60%的测试点，n<=1000，m<=10000；对于100%的测试点，1<=n<=100000，1<=m<=200000，1<=w<=1000。编程题2：果园采摘规划【题目背景】小杨承包了一片果园，果园里总共有n棵果树，这些果树的分布恰好构成一棵以1号节点为根的树形结构。每棵果树上都结有一定数量的果实，采摘第i棵果树的果实可以获得a[i]的收益。但是果园有一个特殊的规则：如果想要采摘某一棵子树节点上的果树，必须先采摘这棵子树对应的父节点的果树，否则该子树的果实在未经过父节点所有者允许的情况下不能采摘。现在小杨总共召集了k名工人，每名工人一次只能采摘一棵完整的果树，且同一棵果树不能被多名工人重复采摘。请你帮小杨计算，在上述规则约束下，他安排k名工人最多可以获得多少总收益。【输入格式】第一行两个正整数n、k，分别代表果树的总数量和工人的总人数。第二行n个正整数a[1],a[2],...,a[n]，分别代表采摘每一棵果树可以获得的收益。接下来n-1行，每行两个正整数u、v，代表编号u的果树和编号v的果树之间存在连接边，保证整体构成以1为根的树。【输出格式】输出一个整数，代表小杨可以获得的最大总收益。【样例输入1】5310572612132425【样例输出1】22【数据范围】对于30%的测试点，n<=20，k<=20；对于60%的测试点，n<=100，k<=100；对于100%的测试点，1<=n<=200，1<=k<=200，a[i]<=1000。参考答案一、单项选择题答案与解析1.答案：B。解析：外层循环i遍历范围是1到n，中间层变量j的步长为i，对于每个确定的i，j的循环次数等于从i到n中i的倍数的数量，为floor(n/i)，两层循环的总迭代次数为Σ_{i=1}^nfloor(n/i)，该求和是调和级数求和，总复杂度为O(nlogn)。最内层k循环的迭代次数固定为n，因此三层循环的总操作数为n*O(nlogn)=O(n²logn)，对应选项B。2.答案：C。解析：该图节点数1000，邻接矩阵的存储空间仅为1000*1000=1e6，完全可以接受，且图是无权图，BFS求单源最短路径的时间复杂度是O(N+M)，每个节点做一次BFS总复杂度是O(N*(N+M))=1e3*(1e3+1e4)=1.1e7，远优于邻接表做Dijkstra的O(N*(M+NlogN))，而Floyd的复杂度是O(N³)=1e9，运算量太大会超时，因此最优组合是邻接矩阵存储加BFS预处理，选C。3.答案：C。解析：Dijkstra算法的核心前提是所有边权非负，存在负边时算法可能得到错误的最短路径结果，只有SPFA/Bellman-Ford可以处理带负边且无负环的场景，因此C选项描述错误。其余选项描述均符合Dijkstra算法的特性。4.答案：B。解析：当图中所有边权互不相等时，不可能存在两棵不同的生成树，满足所有边权之和最小，因此最小生成树一定唯一，B正确。A选项错误，存在多条边权相等时MST不唯一；C选项错误，不同的MST的边权集合是完全相同的，只是选的边的具体连接节点可能不同；D选项错误，最小生成树中的路径不一定是原图的最短路径。5.答案：D。解析：01背包的逆序遍历核心目的是滚动数组优化时，保证更新dp[j]用到的dp[j-w[i]]是上一轮也就是未选择当前物品时的旧值，确保每个物品只被选一次，B选项是表面现象，D选项是核心本质，因此选D。6.答案：C。解析：STL的priority_queue默认使用vector作为底层存储容器，默认实现的是大顶堆，每次top返回最大值，对应选项C。7.答案：B。解析：Floyd的空间优化核心是按照k从小到大的顺序遍历，每次用中间节点k去松弛所有i到j的路径，此时更新dist[i][j]用到的dist[i][k]和dist[k][j]都没有经过k节点，属于k-1轮的正确结果，因此可以直接原地覆盖二维数组，得到正确的全源最短路径结果，选B。8.答案：A。解析：KMP算法预处理next数组的时间复杂度是O(m)，匹配主串的过程中指针不会回退，总匹配时间复杂度是O(n)，整体总复杂度为O(n+m)，选A。9.答案：B。解析：Tarjan算法中的dfn代表节点第一次被访问的时间戳，low代表节点或其子树通过非父节点的回边能到达的栈中节点的最小dfn值，对应选项B的描述。10.答案：C。解析：求解最大独立集的树形DP，只需要对每个节点做一次后序遍历，遍历所有子树合并状态即可，总时间复杂度为O(N)，选C。二、判断题答案与解析1.错误。解析：SPFA算法一旦检测到某个节点入队次数超过N次，就说明图中存在负环，此时不存在从起点到该节点的有限短路径，无法得到正确的计算结果。2.正确。解析：Kruskal的核心开销是边的排序，排序E条边的时间复杂度为O(ElogE)，整体算法复杂度和该排序复杂度相当。3.正确。解析：无后效性是动态规划算法成立的三大核心条件之一，保证状态转移的过程不会出现循环依赖。4.错误。解析：n个节点的完全无向图的边数为n(n-1)/2，邻接表需要存储所有边，总存储空间复杂度为O(n²)，而非O(n)。5.正确。解析：STL的map底层为红黑树，是平衡二叉搜索树，所有操作的时间复杂度均为O(logn)。6.错误。解析：非连通的无向图不存在生成树，自然也不存在最小生成树，只有连通无向图才有生成树。7.正确。解析：二进制拆分将每类物品拆分为logS份，将多重背包转化为等价的01背包，大幅降低了朴素实现的时间开销，是多重背包的经典优化方案。8.正确。解析：Dijkstra算法的理论最优时间复杂度就是采用斐波那契堆实现得到的O(M+NlogN)，远优于普通二叉堆优化的O(MlogN)。9.错误。解析：Tarjan算法求割点时，根节点需要特殊判定，只有当根节点的子树数量大于等于2时，根节点才是割点，否则不满足割点条件。10.正确。解