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

2025年9月GESP编程能力认证C++等级考试七级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.已知小写字母b的ASCII码为98，下列C++代码的输出结果是（）。#include<iostream>usingnamespacestd;intmain(){chara='b'+1;cout<<a;return0;}A.bB.cC.98D.992.已知a为int类型变量，p为int*类型变量，下列表达式不符合语法的是（）。A.a*aB.p*pC.a&&aD.p&&p3.下列关于C++类的说法，错误的是（）。A.如果一个类包含纯虚函数，则它不能包含成员变量。B.如果一个类包含纯虚函数，则不能用它定义对象。C.派生类对象占用的内存总是不小于基类对象。D.派生类可以不实现基类的虚函数。4.已知数组a的定义inta[10]={-1};下列说法不正确的是（）。A.数组a至少占用10个int大小的内存，一般为40个字节。B.数组a的所有元素均被初始化为-1。C.语句a[-1]=0;不会产生编译错误，但会导致难以预测的运行结果。D.语句a[13]=0;不会产生编译错误，但会导致难以预测的运行结果。5.一棵完全二叉树有165个结点，则叶结点有多少个？（）。A.38B.82C.83D.846.下列关于二叉树的说法，错误的是（）。A.二叉排序树的中序遍历顺序与元素排序的顺序是相同的。B.自平衡二叉查找树（AVL树）是一种二叉排序树。C.n个元素的二叉排序树，其高一定为[log2n]。D.任意的森林，都可以映射为一颗二叉树进行表达和存储。7.下列关于树和图的说法，错误的是（）。A.保留树的所有节点，并把树的每个节点指向其父节点，则可以将树转换为一个有向弱连通图。B.保留树的所有节点，并把树的每个节点指向其子节点，则可以将树转换为一个有向无环图。C.每个连通图都存在生成树。D.每个存在生成树的有向图，都一定是强连通的。8.对一个包含V个顶点、E条边的图，执行广度优先搜索，其最优时间复杂度是（）。A.O(V+E)B.O(V)C.O(E)D.O(V2)9.以下哪个方案不能合理解决或缓解哈希表冲突（）。A.用新元素覆盖发生冲突的哈希表项。B.在每个哈希表项处，使用单链表管理该表项的冲突元素。C.建立额外的单链表，用来管理所有发生冲突的元素。D.使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。10.以下关于贪心法和动态规划的说法中，错误的是（）。A.对特定的问题，贪心法不一定适用。B.当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。C.对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。D.采用动态规划的算法一定具有多项式时间复杂度。11.下面程序的输出为（）。#include<iostream>usingnamespacestd;intfib(intn){if(n==0)return1;returnfib(n-1)+fib(n-2);}intmain(){cout<<fib(6)<<endl;return0;}A.8B.13C.21D.无法正常结束。12.下面程序的时间复杂度为（）。intrec_fib[MAX_N];intfib(intn){if(n<=1)returnn;if(rec_fib[n]!=0)returnrec_fib[n];returnfib(n-1)+fib(n-2);}A.B.O(2n)C.O(n2)D.O(n)13.下面init_sieve函数的时间复杂度为（）。intsieve[MAX_N];voidinit_sieve(intn){for(inti=1;i<=n;i++)sieve[i]=i;for(inti=2;i<=n;i++)for(intj=i;j<=n;j+=i)sieve[j]--;}A.O(n)B.O(nloglogn)C.O(nlogn)D.O(n2)14.下面count_triple函数的时间复杂度为（）。intgcd(intm,intn){if(m==0)returnn;returngcd(n%m,m);}intcount_triple(intn){intcnt=0;for(intv=1;v*v*4<=n;v++)for(intu=v+1;u*(u+v)*2<=n;u+=2)if(gcd(u,v)==1){inta=u*u-v*v;intb=u*v*2;intc=u*u+v*v;cnt+=n/(a+b+c);}returncnt;}A.O(n2)B.O(n2logn)C.O(nlogn)D.O(n)15.下列选项中，哪个不可能是下图的深度优先遍历序列（）。A.2,3,5,7,8,9,6,4,1B.5,7,8,9,1,2,4,3,6C.6,8,9,5,7,1,2,3,4D.8,5,7,9,1,2,3,6,4二、判断题（每题2分，共20分）。16.题C++语言中，表达式9&&12的结果类型为int、值为8。（）。A.正确B.错误17.题C++语言中，在有inta[10];定义的范围内，通过表达式a[-1]进行访问将导致编译错误。（）。A.正确B.错误18.选择排序一般是不稳定的。（）。A.正确B.错误19.题C++语言中，float和int类型一般都是4字节，因此float类型能够表达不同的浮点数值的数量，与int类型能够表达不同的整数值的数量是相同的。（）。A.正确B.错误20.使用math.h或cmath头文件中的对数函数，表达式log(256)的结果类型为double、值约为8.0。（）。A.正确B.错误21.一棵有N个节点的完全二叉树，则树的深度为[log2(N)]+1。（）。A.正确B.错误22.邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。（）。A.正确B.错误23.题C++语言中，类的构造函数可以声明为私有（private）。（）。A.正确B.错误24.泛洪算法的递归实现容易造成溢出，因此大的二维地图算法中，一般使用广度优先搜索实现。（）。A.正确B.错误25.很多游戏中为玩家设置多种可供学习的技能，要学习特定技能又往往需要先学习1个或以上的前置技能。尽管这样的技能间依赖关系常被玩家称为“技能树”，但它并不一定是树，更可能是有向无环图。（）。A.正确B.错误三、编程题（每题25分，共50分）。26.试题名称：连通图。时间限制：1.0s。内存限制：512.0MB。题目描述：给定一张包含n个结点与m条边的无向图，结点依次以1,2……n编号，第i条边（1≤i≤m）连接结点ui与结点vi。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。注意给出的图中可能包含重边与自环。输入格式：第一行，两个正整数n,m，表示图的点数与边数。接下来m行，每行两个正整数ui,vi，表示图中一条连接结点ui与结点vi的边。输出格式：输出一行，一个整数，表示使得图中任意两个结点连通所需加入的边的最少数量。数据范围：对于40%的测试点，保证1≤n≤100，1≤m≤100。对于所有测试点，保证1≤n≤105，1≤m≤105。27.试题名称：金币收集。时间限制：1.0s。内存限制：512.0MB。题目描述：小A正在游玩收集金币的游戏。具体来说，在数轴上将会出现n枚金币，其中第i枚（1≤i≤n）金币将会在时刻ti出现在数轴上坐标为xi的位置。小A必须在时刻ti恰好位于坐标，才可以获得第i枚金币。游戏开始时为时刻0，此时小A的坐标为0。正常来说，小A可以按游戏机的按键在数轴上左右移动，但不幸的是游戏机的左方向键失灵了。小A每个时刻只能选择保持不动，或是向右移动一个单位。换言之，如果小A在时刻t的坐标为x，那么他在时刻t+1的坐标只能是x或是x+1二者之一，分别对应保持不动和向右移动。小A想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗？输入格式：第一行，一个正整数n，表示金币的数量。接下来n行，每行两个正整数xi,ti，分别表示金币出现的坐标与时刻。输出格式：输出一行，一个整数，表示小A最多能收集的金币数量。数据范围：对于40%的测试点，保证1≤n≤8。对于另外30%的测试点，保证1≤n≤100，1≤xi≤100，1≤ti≤100。对于所有测试点，保证1≤n≤105，1≤xi≤109，1≤ti≤109。答案解析如下。1.答案：B。解析：char类型与int类型计算时，会自动扩大类型，'b'+1的计算结果为int类型的98+1=99，但在存储于变量a时会转换char类型存储，而99对应的ASCII字符为'c'，时按照char类型的输出规则，输出c。2.答案：B。解析：int*类型的指针变量不能直接进行乘法运算（p*p语法错误）；a*a是整数乘法，a&&a和p&&p是逻辑与运算（指针非空则为真），均符合语法。3.答案：A。解析：包含纯虚函数的类是抽象类，抽象类可以包含成员变量（A错误）；抽象类不能实例化对象（B正确）；派生类继承基类成员，内存不小于基类（C正确）；派生类若未实现基类虚函数，仍为抽象类（D正确）。4.答案：B。解析：数组初始化时，若只指定部分元素，剩余元素会被初始化为0（而非全部-1，B错误）；数组大小固定为10个int（通常40字节，A正确）；下标越界编译不报错，但运行时可能访问非法内存（C、D正确）。5.答案：C。解析：完全二叉树中，若总结点n为奇数，叶节点数为(n+1)/2；若为偶数，叶节点数为n/2。165是奇数，叶节点数为(165+1)/2=83。6.答案：C。解析：二叉排序树的高度取决于插入顺序，最坏情况下为O(n)（如有序插入形成单链），并非一定为[log2n]（C错误）；A、B、D均为二叉树的基本性质。7.答案：D。解析：有向图的生成树仅保证弱连通（任意两节点存在路径，不要求方向），但不一定强连通（任意两节点双向可达，D错误）；A、B、C均正确。8.答案：A。解析：BFS至少需访问所有顶点（O(V)）和所有边（O(E)），总时间复杂度为O(V+E)，这是复杂度的下界，该复杂度在使用邻接表存储时可以达到，因此是最优复杂度。9.答案：A。解析：覆盖冲突元素会导致数据丢失，无法解决冲突（A错误）；B是链地址法，C、D是再哈希或分离链表的变体，均为合理的冲突解决策略。10.答案：D。解析：动态规划的时间复杂度取决于状态数和转移复杂度，某些问题（如旅行商的动态规划解法）时间复杂度为指数级（D错误）；A、B、C均正确。11.答案：D。解析：函数缺少n=1的终止条件，当计算fib(6)时会递归到fib(-1)、fib(-2)等，陷入无限递归，无法正常结束。12.答案：D。解析：程序通过rec_fib数组缓存计算结果，每个fib(n)仅计算一次，总计算次数为O(n)，时间复杂度为线性。13.答案：C。解析：外层循环i从2到n，内层循环j的执行次数为n/i，总次数为n/2+n/3+…+n/n≈nlogn，因此时间复杂度为O(nlogn)。14.答案：C。解析：外层循环v的范围为O(√n)，内层循环u的范围为O(√n)，总循环次数为O(n)；GCD的时间复杂度为O(logn)，因此总复杂度为O(nlogn)。15.答案：B。解析：DFS要求访问一个节点后，优先深入其未访问的邻接节点。选项B中，访问2后直接跳到41，但4指向的节点（如3）未被访问，不符合DFS规则，故不可能是DFS序列。16.答案：错误。解析：&&是逻辑与运算符，两边非0则结果为1（真），类型为int，故结果应为1而非8。17.答案：错误。解析：C++编译器不检查数组下标是否越界，a[-1]编译时不会报错，但运行时会访问非法内存。18.答案：正确。解析：选择排序中，交换元素可能改变相等元素的相对顺序（如[2,2,1]排序后第一个2会被交换到末尾），因此不稳定。19.答案：错误。解析：int类型能够表达2^32个不同的整数值；float类型能够表达的浮点数值的数量略少于2^32，这是由于存在多种二进制模式用来表示特殊值（+0、-0、+Inf、-Inf、NaN等）。20.答案：错误。解析：log函数默认以自然常数e为底，log(256)的值约为5.545，以2为底的对数需用log2(256)=8.0。21.答案：正确。解析：完全二叉树的深度公式为[log₂N]+1，例如N=8时，深度为4（⌊log₂8⌋+1=3+1=4深度为3+1=4，实际8个节点的完全二叉树深度为4，公式正确）。22.答案：错误。解析：时间复杂度取决于操作类型：邻接表适合遍历边（O(E)），邻接矩阵适合判断边是否存在（O(1)），不能一概而论邻接表时间复杂度更低。23.答案：正确。解析：私有构造函数可防止类被实例化（如单例模式），是合法的语法。24.答案：正确。解析：递归泛洪受栈深度限制，大地图易栈溢出；BFS用队列实现，无此问题，更适合大地图。25.答案：正确。解析：技能依赖可能存在多个前置条件（如技能C需要A和B），形成DAG；树只能有一个父节点，故技能依赖更可能是DAG。26.参考程序。#include<algorithm>#include<cstdio>usingnamespacestd;constintN=1e5+5;intn,m;intf[N];intans;intgetf(intu){returnf[u]?f[u]=getf(f[u]):u;}intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=m;i++){intu,v;scanf("%d%d",&u,&v);if(getf(u)!=getf(v))f[getf(u)]=v;}for(inti=1;i<=n;i++)ans+=getf(i)==i;printf("%d\n",ans-1);return0;}27.参考程序。#include<algorithm>#include<cstdio>usingnamespacestd;constintoo=2e9