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

2026年3月GESP编程能力等级认证C++七级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.假设一个算法时间复杂度的递推式是T(n)=2T(n-1)+1（n为正整数），且T(0)=1，那么这个算法的时间复杂度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(2n)2.下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（）。A.如果预处理出n以内每个数的最小质因子，那么可以在O(logn)时间内完成任意一个不超过n的整数的质因数分解。B.线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。C.唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。D.唯一分解定理是埃氏筛时间复杂度为O(nloglogn)的根本原因。3.若字符串A与字符串B的最长公共子序列（LCS）长度为5，则（）。A.它们的编辑距离为5B.它们至少有5个公共字符C.它们最长公共子串长度为5D.它们一定长度相等4.对于一棵包含n个顶点（n≥2）的树，其所有顶点的度数之和必定等于（）。A.n-1B.2n-2C.2nD.n25.关于哈希表（HashTable）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（）。A.装载因子越大，发生冲突的概率通常越高。B.开放定址法在删除元素时实现相对复杂C.链地址法在最坏情况下查找时间复杂度为O(n)D.查找哈希表的时间复杂度总是O(1)6.深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择一个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前一顶点继续搜索。该算法主要运用了（）。A.分治B.贪心C.动态规划D.回溯7.下面程序的运行结果为（）。#include<iostream>#include<algorithm>boolcheck(intn,inta[],intk,intdist){intcnt=1;intlast=a[0];for(inti=1;i<n;i++){if(a[i]-last>=dist){cnt++;last=a[i];}}returncnt>=k;}intsolve(intn,inta[],intk){std::sort(a,a+n);intl=0;intr=a[n-1]-a[0];while(l<r){intmid=(l+r+1)/2;if(check(n,a,k,mid))l=mid;elser=mid-1;}returnl;}intmain(){inta[]={1,2,8,4,9};intn=5;intk=3;std::cout<<solve(n,a,k)<<std::endl;return0;}A.2B.3C.4D.58.下面程序的时间复杂度是（），假设数组a的值域范围是D。#include<iostream>#include<algorithm>boolcheck(intn,inta[],intk,intdist){intcnt=1;intlast=a[0];for(inti=1;i<n;i++){if(a[i]-last>=dist){cnt++;last=a[i];}}returncnt>=k;}intsolve(intn,inta[],intk){std::sort(a,a+n);intl=0;intr=a[n-1]-a[0];while(l<r){intmid=(l+r+1)/2;if(check(n,a,k,mid))l=mid;elser=mid-1;}returnl;}intmain(){inta[]={1,2,8,4,9};intn=5;intk=3;std::cout<<solve(n,a,k)<<std::endl;return0;}A.O(nlogn+nlogD)B.O(nlognlogD)C.O(nlogn)D.O(nlogD)9.某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：ABDHIECFJG，中序遍历序列为：HDIBEAFJCG，则该二叉树的后序遍历序列是（）。A.HIDEBJFGCAB.HIDBEJFGCAC.IHDEBJFGCAD.HIDEBFJGCA10.下面哪一个可能是下图的深度优先遍历序列（）。A.1,5,4,8,7,9,6,3,2B.1,5,8,4,7,9,6,3,2C.2,5,8,7,9,6,3,4,1D.8,9,6,3,2,5,1,4,711.下面这个有向图的强连通分量的个数是（）。A.3B.4C.5D.612.关于泛洪算法（FloodFill）的说法，正确的是（）。A.泛洪算法只适用于二维网格中的四连通或八连通问题。B.泛洪算法必须使用递归方式实现。C.泛洪算法本质上是对图进行一次从起点出发的搜索。D.泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。13.有6个字符，它们出现的次数分别为：{2,3,3,4,6,8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL（每个字符的出现次数×它的编码长度，再把每个字符结果加起来）的值为（）。A.58B.60C.62D.6414.关于单链表、双链表和循环链表，下列说法正确的是（）。A.在单链表中，若已知某结点的指针，则可以在O(1)时间内删除该结点。B.循环链表中一定不存在空指针。C.在循环双链表中，尾结点的next指针一定为NULL。D.在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。15.下列关于树的遍历的说法中，正确的一项是（）。A.对任意一棵树进行深度优先遍历，所得序列一定唯一。B.已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。C.已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。D.一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。二、判断题（每题2分，共20分）。16.题C++语言中，表达式4^2的结果类型为int，值为6。（）。A.正确B.错误17.题C++中引用可以重新绑定。（）。A.正确B.错误18.在C++中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。（）。A.正确B.错误19.如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。（）。A.正确B.错误20.使用归并排序对n个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为O(nlogn)。（）。A.正确B.错误21.在无向连通图中删除一条边，该图就一定变成非连通图。（）。A.正确B.错误22.在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。（）。A.正确B.错误23.若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。（）。A.正确B.错误24.使用math.h或cmath头文件中的函数，表达式sin(90)的结果为1。（）。A.正确B.错误25.在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的DFS生成树一定包含图中的所有顶点。（）。A.正确B.错误三、编程题（每题25分，共50分）。26.试题名称：拆分。时间限制：1.0s。内存限制：512.0MB。题目描述：小A想将正整数n拆分成若干个正整数之和，并最大化拆分后的正整数之积。小A希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对109取模的结果。形式化地，n的拆分是满足a1+…+ak=n的若干个正整数a1,…,ak，其中1≤k≤n。你需要求出n的所有拆分中a1×…×an的最大值对109取模的结果。输入格式。第一行，一个正整数t，表示数据组数。对于每组数据：一行，一个整数n，表示给定的正整数。输出格式：对于每组数据：输出一行，一个整数，表示n拆分后正整数之积的最大值对109取模的结果。输入样例。输出样例。数据范围。对于40%的测试点，保证n≤50。对于所有测试点，保证1≤t≤104，1≤n≤106。27.试题名称：物流网络。时间限制：1.0s。内存限制：512.0MB。题目描述：一个物流网络由n个城市和m条双向公路组成。每条公路都有两个属性。（1）运输费用Wi。（2）景观评分bi。当一辆运输车从城市1运送货物到城市n时，需要支付经过道路的运输费用之和。为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。请你计算，从城市1到城市n的最小运输费用。输入格式。第一行两个整数n，m，分别表示城市数量和公路数量。接下来m行，每行四个整数u，v，w，b，表示存在一条连接城市u和城市v的双向公路，其中w为运输费用，b为景观评分。输出格式。输出一个整数，表示从城市1到城市n的最小费用。如果无法到达，输出-1。输入样例。输出样例。样例解释。路径1→2→3：费用10+20，最大美丽值6(边2-3)。免除20，总花费10。路径1→3：费用100，最大美丽值1(边1-3)。免除100，总花费0。最小费用为0。数据范围：1≤n≤5000，1≤m≤5000，1≤w,b≤109。答案解析如下。1.答案：D。解析：时间复杂度是算法执行的指令数目。该时间复杂度的递推式是典型的指数级算法（如：汉诺塔）的递推式，其时间复杂度为O(2^n)。2.答案：D。解析：A正确：预处理最小质因子后，每次除以最小质因子即可分解，次数为O(logn)。B正确：线性筛的核心就是利用唯一分解定理保证每个合数只被其最小质因子筛掉。C正确：如果一个数没有被不超过其平方根的质数整除，那么它一定是质数（这是试除法判断素数的原理，由唯一分解定理保证）。D错误：埃氏筛的时间复杂度为O(nloglogn)是因为每个质数要筛掉它的倍数，这与唯一分解定理无直接关系；唯一分解定理是数论基本定理，并不决定筛法的时间复杂度。3.答案：B。解析：LCS长度为5意味着两个字符串中存在一个长度为5的公共子序列，因此它们至少有5个公共字符（但字符位置不一定连续）。4.答案：B。解析：树有n个顶点，则边数为n-1。所有顶点的度数之和等于边数的两倍，即2(n-1)=2n-2。5.答案：D。解析：A正确：装载因子越大，冲突概率越高。B正确：开放定址法删除元素时不能直接置空，否则影响查找，需要特殊标记。C正确：链地址法在最坏情况下（所有元素哈希到同一位置）查找时间复杂度为O(n)。D错误：哈希表在理想情况下查找是O(1)，但最坏情况可能退化为O(n)，且受哈希函数和冲突解决影响，并非总是O(1)。6.答案：B。解析：题目强调的是“选择一个相邻的未访问顶点”这一步的局部决策，是贪心思想的体现（每次都选一个方向走下去，不全局规划）。而回溯只是实现DFS的手段，不是算法的主要思想归类。7.答案：B。解析：程序实现的是“在有序数组中选取k个数，使得相邻两数的最小距离最大”的经典问题（类似“进击的奶牛”）。输入数组排序后为{1,2,4,8,9}，二分查找最大最小距离。check函数判断能否选出至少k个数使得相邻距离≥dist。初始l=0，r=8，mid从4开始。当dist=4时，从1开始，可选出1,8（距离7≥4）或1,9（距离8≥4），但只能选出2个数（cnt=2）<3，不满足。调整后最终得到答案为3（可选出1,4,8或1,4,9，最小距离3）。8.答案：A。解析：排序是O(nlogn),二分是O(nlogD)，所以选A。9.答案：A。解析：在先序遍历中找根，在中序遍历中确定父子关系。10.答案：B。解析：其它选项都没有施行一条道走到黑的DFS的算法思想。A选项，1、5、4后仍可访问7，不能回溯访问到8；C选项，2、5、8、7、9、6、3后仍可访问1，不能回溯访问到4；D选项，8、9、6、3、2、5后仍可访问4和8，不能回溯访问1。11.答案：B。解析：{1，2，6，9，10，11，12，5}、{3，4}、{7，8}、{13，14，16，15}。12.答案：C。解析：泛洪算法本质是从起点出发的图搜索（DFS或BFS），可用于二维网格连通区域，也可用于图连通分量。A错误：不仅限于二维网格。B错误：可以用递归或非递归实现。C正确。D错误：可以统计面积、周长等。13.答案：D。解析：根据题目模拟即可，2*3+3*3+6*2+3*3+4*3+8*2=64。14.答案：D。解析：A错误：单链表中已知结点指针，无法直接删除，还需要找到前驱结点的指针。B错误：过于绝对，因为空链表可能头指针为空。C错误：循环双链表中尾结点的next指向头结点，不为NULL。D正确：带头结点的循环单链表，判断空的条件是头结点的next指向自身。15.答案：C。解析：A错误：树的DFS序列不唯一（如孩子顺序）。B错误：先序和后序不能唯一确定二叉树（需中序）。C正确：先序+中序可唯一确定。D错误：中序单调递增只能说明是二叉搜索树，不一定是平衡树。16.答案：正确。解析：C++中4^2是按位异或，4（100）异或2（010）得110（6），结果为int，值为6。17.答案：错误。解析：C++引用一旦初始化，就不能再重新绑定到其他对象。说法错误。18.答案：正确。解析：引用作为形参，函数内修改即修改实参。正确。19.答案：错误。解析：动态规划可解的问题不一定存在贪心策略，贪心往往需要最优子结构和贪心选择性质，并非所有DP问题都能贪心。错误。20.答案：正确。解析：归并排序的最好、平均、最坏时间复杂度均是O(nlogn)。21.答案：错误。解析：在无向连通图中，删除一条边后图是否仍然连通，取决于这条边是不是桥（割边）。如果删除的是桥→图会变成非连通图（分成两个部分）。如果删除的是环上的边→图仍然连通（可以通过环的另一条路径绕过）。22.答案：正确。解析：因为规则规定“每次都选编号最小的邻居”，所以从起点开始，每一步该走哪个点都是确定的，没有第二种选择，因此整个遍历序列只有一种。23.答案：错误。解析：字符频率相同时，哈夫曼树可能不是完全二叉树。完全二叉树要求最后一层的叶节点都在左侧，哈夫曼树合并过程中并不保证这一点。例如，5个字符时，只有叶节点深度为3、3、2、2、2的树是完全二叉树（下图左），但哈夫曼树可能得到叶节点深度为2、2、3、3、2的二叉树（下图右）。所以说法错误。24.答案：错误。解析：sin(90)中的90是弧度，不是角度。90弧度约等于5157度，sin值不是1。正确应使用sin(90*M_PI/180)。错误。25.答案：正确。解析：在无向连通图中，从任意顶点出发进行DFS，可以访问所有顶点，因此DFS生成树包含所有顶点。正确。26.参考程序。#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintN=1e6+5;constintmod=1e9;constdoubleln2=log(2);constdoubleln3=log(3);intf[N];doublelnf[N];intmain(){f[0]=f[1]=1;for(inti=0;i<N;i++){if(i+2<N&&lnf[i]+ln2>lnf[i+2]){lnf[i+2]=lnf[i]+ln2;f[i+2]=2ll*f[i]%mod;}if(i+3<N&&lnf[i]+ln3>lnf[i+3]){lnf[i+3]=lnf[i]+ln3;f[i+3]=3ll*f[i]%mod;}}intt;scanf("%d",&t);while(t--){intn;scanf("%d",&n);printf("%d\n",f[n]);}return0;}解析：之所以尽量拆出3，是因为如果拆分中存在一个大于等于5的数x，那么把它拆成3和x-3后，乘积会从x变成3×(x-3)，并且当x≥5时有3×(x-3)>x，所以继续拆出一个3一定能使乘积变大。因此最优拆分中不会保留大于等于5的数，只会剩下2、3、4这几种情况。而在相同总和下，3通常比2更优，例如3+3的乘积为9，大于2+2+2的乘积8，所以应尽量拆成3。但需要注意，拆分后不应该单独留下1。因为1乘到结果中不会增加乘积，反而会浪费一部分和。具体来说，如果最后得到3和1，那么它们的乘积是3；而把这两个数重新合并并拆成2和2，和仍然是4，但乘积变成4，更大。因此当n除以3的余数为1时，应少拆出一个3，把这部分3+1改成2+2。27.参考程序。#include<algorithm>#include<iostream>#include<queue>#include<vector>usingnamespacestd;structHighway{intu,v;intfee,b;booloperator<(constHighway&other)const{returnb==other.b?fee<other.fee:b<other.b;}};voidsolve(){intn,m;cin>>n>>m;vector<Highway>highways(m);for(inti=0;i<m;i++)cin>>highways[i].u>>highways[i].v>>highways[i].fee>>highways[i].b;sort(highways.begin(),highways.end());vector<vector<constHighway*>>network(n+1);vector<longlong>dp1(n+1,(longlong)1e18);vector<longlong>dpn(n+1,(longlong)1e18);dp1[1]=0,dpn[n]=0;longlonganswer=(longlong)1e18;for(intri=0;ri<m;ri++){constHighway&r=highways[ri];answer=min(answer,min(dp1[r.u]+dpn[r.v],dp1[r.v]+dpn[r.u]));network[r.u].push_back(&r);network[r.v].push_back(&r);vector<int>cur;cur.push_back(r.u),cur.push_back(r.v);for(intt=0;t<cur.size();t++){inti=cur[t];for(intt2=0;t2<network[i].size();t2++){constHighway*j=network[i][t2];intk=(i==j->u?j->v:j->u);if(dp1[i]+j->fee<dp1[k]){dp1[k]=dp1[i]+j->fee;cur.push_back(k);}}}cur.clear();cur.push_back(r.u),cur.push_back(r.v);for(intt=0;t<cur.size();t++){inti=cur[t];for(intt2=0;t2<network[i].size();t2++){constHighway*j=network[i][t2];intk=(i==j->u?j->v:j->u);if(dpn[i]+j->fee<dpn[k]){dpn[k]=dpn[i]+j->fee;cur.push_back(k);}}}cur.clear();}cout<<(answer==(longlong)1e18?-1:answer)<<'\n';}intmain(){solve();return0;}参考程序2。#include<algorithm>#include<cstring>#include<iostream>#include<queue>#include<vector>usingnamespacestd;structRoad{intu,v,w,b;booloperator<(constRoad&other)const{returnb==other.b?w<other.w:b<other.b;}};voidsolve(){intn,m;cin>>n>>m;vector<Road>roads(m);for(auto&road:roads){cin>>road.u>>road.v>>road.w>>road.b;}sort(roads.begin(),roads.end());vector<vector<constRoad*>>graph(n+1);constautorelax=[&](vector<longlong>&dist,queue<int>&q){while(!q.empty()){intu=q.front();q.pop();for(autoroad:graph[u]){intv=u==road->u?road->v:road->u;if(dist[u]+road->w<dist[v]){dist[v]=dist[u]+road->w;q.push(v);}}}};vector<longlo