2025年12月 CCF GESP认证 C++八级试题

国时真机 GESP CCF编程能力等级认证 Grade Examination of Software Programming C++八级 2025年12月 1单选题（每题2分，共30分） 题号123456789101112131415 答案BB A C B C BB CCC B A C B 第1题某平台生成取件码由6个字符组成：前4位为数字（0-9)，后2位为大写字母（A-Z),其中字母不能 为I、0。假设数字和字母均可重复使用，要求整个取件码中恰好有2个数字为奇数。共有多少种不同取件码？( ☐A.1,440,000 ☐B.2,160,000 ☐C.2,535,000 ☐D.8,640,000 第2题下列代码实现了归并排序(Merge Sort)的分治部分。为了正确地将数组a的[Left,right]区间进行 排序，横线处应该填入的是()。 1 void merge_sort(int a[],int left,int right){ 2 if (Left >right)return; 3 int mid =(Left right)/2; merge_sort(a,left,mid); 5 ---；/在此处填入选项 6 merge(a,Left,mid,right);//合并操作 7} A.merge_sort(a,mid,right) OB.merge_sort(a,mid 1,right) C.merge_sort(a,Left,mid 1) D.merge_sort(a,mid -1,right) 第3题某社团有男生8人、女生7人。现需选出1名队长（性别不限）、1名副队长（性别不限）、2名宣传委员（两 人无角色区别，且必须至少1名女生)。假如一人不能兼任多职，共有多少种不同选法？() ☐A.12012 ☐B.11844 ☐C.12474 ☐D.11025 第4题二项式(2x-y)8的展开式中x5y3项的系数为(）。 ☐A.-7168 第1页/共9页 ☐B.7168 ☐C.-1792 ☐D.1792 第5题下面是使用邻接矩阵实现的D冰sa算法的核心片段，用于求单源最短路径。在找到当前距离起点最近的顶点 U后，需要更新其邻接点j的距离。横线处应填入的代码是（)。 1 for (int j=1;j <n;j++){ 2 if (!visited[j]&graph[u][j]INF){ 3 if -){/在此处填入选项 dis[j]dis[u]graph[u][j]; 6 7 A.dis[j]dis[u]graph[u][j] B.dis[j]dis[u]+graph[u][j] C.graph[u][j]>dis[u]dis[j] D.dis[j]graph[u][j] 第6题下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度，横线处应填入的是（)。 1 #include <algorithm> #include <string> 3 #include <vector> using namespace std; 5 6 int lcs_len(const string &a,const string &b){ int n =(int)a.size(),m=(int)b.size(); 8 vector<vector<int>>dp(n 1,vector<int>(m 1,0)); 9 for (int i=1;i <n;i++) 10 for (int j=1;j <m;j++) 11 if(a[i-1]==b[j-1]) 12 dp[i][]=dp[i-1][j-1]+1; 13 else 14 --；/1在此处填入选项 15 return dp[n][m]; 16 A.dp[i][j]=dp[i 1][j]+dp[i][j-1]; B.dp[i][j]min(dp[i-1][j],dp[i][j 1]); C.dp[i][j]=max(dp[i-1][j],dp[i][j-1]); D.dp[i][j]max(dp[i-1][j],dp[i][j -1])+1; 第7题已知两个点A(x1,y1)和B(x2,2)在平面直角坐标系中的坐标。下列C++表达式中，能正确计算这两点之间 直线距离的是（)。 ☐A.sqnt(x1-x2)^2+(y1-y2)^2) B.sqrt(pow(x1 -x2,2)+pow(y1 -y2,2)) OC.pow(x1-x2,2)+pow(y1 -y2,2) OD.abs(x1 -x2)+abs(y1-y2) 第8题已知inta=10;,执行int&b=a;b=20;后，变量a的值是()。 第2页/共9页 ☐A.10 ☐B.20 ☐c.30 ☐D.编译错误 第9题下列代码的时间复杂度（以为自变量，忽略常数与低阶项）是()。 1 Longlong s =0; 2 for (int i=1;i<=n;i++){ 3 for (int j=1;j*j<=i;j++){ s+=ji 5 } 63 ☐A.0(n) ☐B.O(n log n) ☐c.O(nvm) ☐D.0(n2) 第10题下列程序实现了线性筛法（欧拉筛），用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数 只被其最小质因子筛掉，横线处应填入的语句是（)。 1 for (int i=2;i<=n;i++){ if (!not_prime[i])primes[++cnt]i; for (int j=1;j<=cnt &i*primes[j]<n;j++){ 4 not_prime[i primes[j]]true; 5 if(---)break;/在此处填入选项 73 ☐A.i+primes[j]=n ☐B.primes[j]>i ☐C.i%primes[j]=o □D.i%primes[j]I=g 第11题在C+语言中，关于类的继承和访问权限，下列说法正确的是（）。 ☐A.派生类可以访问基类的private成员。 □B.基类的protected成员在私有继承(private inheritance)后，在派生类中变为public。 ☐C.派生类对象在创建时，会先调用基类的构造函数，再调用派生类自己的构造函数。 ☐D.派生类对象在销毁时，会先调用基类的析构函数，再调用派生类自己的析构函数。 第12题当输入6时，下列程序的输出结果为（)。 第3页/共9页 1 #include <iostream> 2 using namespace std; 3 int f(int n){ 4 if (n <3)return n; 5 return f(n-1)+f(n-2)+2*f(n-3); 6 int main(){ 8 int n; 9 cin >n; 10 cout <f(n)<<endl; 11 return 0; 2 ☐A.14 ☐B.27 ☐C.28 ☐D.15 第13题从1到999这999个正整数中，十进制表示中数字5恰好出现一次的数有多少个？() ☐A.243 ☐B.271 ☐C.300 ☐D.333 第14题当输入2023时，下列程序的输出结果为(）。 1 #include <iostream> using namespace std; 3 4 int main() int x,ans =0; 6 cin >x; 7 while (x !0){ X-=X&-X; 9 ans++; 10 11 cout <ans <endl; 12 return 0; 13} ☐A.7 ☐B.8 ☐c.9 ☐D.11 第15题对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分 MST结构中，(，v)已在同一连通块内。关于边e的处理，下列说法正确的是（）。 口A.必须选入MST,否则可能不连通。 □B.一定不能选入MST(在此扫描顺序下)。 口C.若后续出现更大的边权，可以回溯改选e。 ☐D.只有当e是当前最小边时才能舍弃。 第4页/共9页 2判断题（每题2分，共20分) 题号12345678910 答案√√√√√√×××× 第1题若一项任务可用两种互斥方案完成：方案A有m种做法，方案B有n种做法，则总做法数为m+几。 第2题在C++语言中，引用一旦被初始化，就不能再改为引用另一个变量。 第3题快速排序和归并排序的平均时间复杂度都是O(nlog),但快速排序是不稳定的排序算法，归并排序是稳定 的排序算法。 第4题使用math.h或cmath头文件中的函数，表达式sqrt(4)的结果类型为double。 第5题在杨辉三角形中，第n行（从0开始计数，即第n行有n+1个数）的所有数字之和等于2n。 第6题使用二叉堆优化的Dj水stra最短路算法，在某些特殊情况下时间复杂度不如朴素实现的O(V)。 第7题个不同元素依次入栈的出栈序列数与将个不同元素划分成若干非空子集的方案数相等。 第8题快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pvot)的方法完全避免退 化。 第9题在C+语言中，一个类可以拥有多个构造函数，也可以拥有多个析构函数。 第10题求两个序列的最长公共子序列(LC$)时，使用滚动数组优化空间后，仍然可以还原出具体的LCS序列。 3编程题（每题25分，共50分） 3.1编程题1 ·试题名称：猫和老鼠 。时间限制：1.0s ·内存限制：512.0MB 3.1.1题目描述 猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2，·，n编号，结点i (1≤i≤n)有价值为c:的奶酪。在m条带权无向边中，第i(1≤i≤m)条无向边连接结点u:与结点v,边权 w表示猫和老鼠通过这条边所需的时间。 猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言，结点u是安全的当且仅当： ·老鼠能规划一条从结点“出发逃往老鼠洞的路径，使得对于路径上任意结点x(包括结点w与老鼠洞)都有： 猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。 老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一 失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。 第5页/共9页 3.1.2输入格式 第一行，两个正整数，m,分别表示图的结点数与边数。 第二行，两个正整数α，b,分别表示猫窝的结点编号，以及老鼠洞的结点编号。 第三行，n个正整数c1,c2,,cm,表示各个结点的奶酪价值。 接下来m行中的第i行(1≤i≤m)包含三个正整数u,v,w:,表示图中连接结点u:与结点v:的边，边权为w:。 3.1.3输出格式 输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。 3.1.4样例 3.1.4.1输入样例1 155 212 3124816 4124 5233 6 341 7 252 8318 3.1.4.2输出样例1 122 3.1.4.3 输入样例2 1610 234 3111111 4126 5233 6314 7345 8458 9 562 10 641 11324 12 544 13 336 3.1.4.4 输出样例2 13 3.1.5数据范围 对于40的测试点，保证1≤n≤500,1≤m≤500。 对于所有测试点，保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤u,v:≤n,1≤w:≤10°。 第6页/共9页 3.1.6 参考程序 #include <cstdio> 2 #include <algorithm> 3 #include <vector> #include <queue> 5 6 using namespace std; 8 const int N 1e5 5; 9 const longlong oo 1e18; 10 11 int n,mi 12 int a,b; 13 int c[N]; 14 vector<pair<int,int>>e[N]; 15 Long Long dis[N]; 16 priority_queve<pair<long long,int>>q; 17 Long long ans; 18 19 int main(){ 20 scanf("%d%d",&n,&m); 21 scanf("%d%d",&a,&b); 22 for (int i=1;i <n;i++) 23 scanf("%d",&c[i]); 24 for (int i=1;i<=m;i++){ 25 int U,V,wi 26 scanf ("%d%d%d",&u,&v,&W); 27 e[u].emplace_back(make_pair(v,w)); 28 e[v].emplace_back(make_pair(u,w)); 29 30 for (int i=1;i<=n;i++) 31 dis[i]=oo; 32 dis[b]0; 33 q.push(make_pair(-dis[b],b)); 34 while (!g.empty()){ 35 auto p q.top() 36 q.pop(); 37 if (dis[p.second]!=-p.first) 38 continve; 39 int u p.second; 40 for (auto r:e[u]){ 41 int v r.first,w r.second 42 if (dis[v]dis[u]w){ 43 dis[v]dis[u]w; 44 q.push(make_pair(-dis[v],v)); 45 46 47 48 for (int i=1;i <n;i++) if (dis[i]dis[a]) 50 ans +c[i]; 5 printf("%Ld ",ans); 52 return 0; 53 3.2 编程题2 。试题名称：宝石项链 。时间限制：1.0s 。内存限制：512.0MB 第7页/共9贡 3.2.1题目描述 小A有一串包含n枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以1,2，，n编号，第n枚宝石与第1枚 宝石相邻。项链由m种宝石组成，其中第i枚宝石种类为t。 小A想将宝石项链分给他的好朋友们。具体而言，小A会将项链划分为若干连续段，并且需要保证每段都包含全部 m种宝石。请帮小A计算在满足条件的前提下，宝石项链最多可以划分为多少段。 3.2.2输入格式 第一行，两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。 第二行，n个正整数t1,t2,…,tn,表示每枚宝石的种类。 32.3输出格式 输出一行，一个整数，表示宝石项链最多可以划分的段数。 3.2.4样例 3.2.4.1 输入样例1 162 2121212 3.2.4.2输出样例1 13 3.2.4.3输入样例2 173 23131212 3.2.4.4输出样例2 12 3.2.5数据范围 对于40的测试点，保证2≤n≤1000。 对于所有测试点，保证2≤n≤105,2≤m≤n,1≤t≤m,保证1,2，，m均在t,t2,,tn中出现。 第8页/共9页 3.2.6 参考程序 1 #include <cstdio> 2 #include <algorithm> using namespace std; 5 6 const int L 20; const int N 2e5 5; const int oo 1e9; 9 10 int n,m; 11 int t[N],jump[L][N]; 12 int cnt[N],tot; 13 int ans; 14 15 int go(int u){ 16 int cnt 0,ans 0; 17 for (int i=L-1;i>=0;i--) 18 if (cnt jump[i][u]<n){ 19 cnt +jump[i][u]; 20 ans+=1<<i; 21 u=(u+jump[i][u]-1)%n+1: 22 23 return ans; 24 25 26 int main(){ 27 scanf("%d%d",&n,&m); 28 for (int i 1;i <n;i++){ 29 scanf("%d",&t[i]): 30 t[i n]t[i]; 31 2 for (int i 1,r =0;i <n;i++) 33 while (tot m){ 34 下++； 35 if (!cnt[t[r]]++) 36 tot++; 37 38 jump[0][i]=r-i+1; 39 if(！--cnt[t[i]]) 40 tot--; 42 for (int i=1;i<L;i++) 43 for (int j=1;j <n;j++){ 44 int tar (j+jump[i -1][j]-1)%n 1; 45 jump[i][j]min(jump[i-1][j]jump[i-1][tar],oo); 46 47 for (int i=1;i <n;i++) 48 ans max(ans,go(i)); 49 printf("%d ",ans); 50 return 0; 51 第9页/共9贡