2025年CCF非专业级别软件认证第一轮（CSP-S）提高级C++语言试题

2025年CCF非专业级别软件认证第一轮 (CSPS)提高级C++语言试题 认证时间：2025年9月20日14：30-16：30 考生注意事项： ●试卷纸共16页，答题纸共有一页，满分100分。请在答题纸上作答，写在试题纸上 一律无效。 ●不得使用任何电子设备（如计算机、手机、电子词典等）或查阅任何书籍资料 一.单项选择题（共15题，每题2分，共计30分） 1、有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这10个球排成一排，要 求任意两个蓝色球都不能相邻，有多少种不同的排列方法？() A.25B.30C.6D.120 2、在KMP算法中，对于模式串P-abacaba,其next数组(next[i]定义为模式串P[O.] 最长公共前后缀的长度，且数组下标从0开始)的值是什么？() A.{0,0,0,1,0,1,2,3}B.{0,1,2,3,4,5,6} C.{0,0,0,1,1,2,2,3}D.{0,0,0,0,0,1,2,3} 3、对一个大小为16（下标0~15）的数组上构建满线段树。查询区间[3,11]时，最少需要 访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？() A.7 B.8 C.9 D.10 4、将字符串cat,car,cat,case,dog,do插入一个空的Trie树（前缀树）中。构建完成Trie 树（包括根节点）共有多少个结点？ A.8B.9C.10D.11 5、对于一个包含n个结点和m条边的有向无环图(DAG),其拓扑排序的结果有多少种 可能？() A.只有1种B.最多n种C.等于nm种D.以上都不对 6、在一个大小为I3的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为Hky) =key mod13。依次插入关键字18,26,35,9,68,74。插入74后，它最终被放置在哪个索引 位置？() A.5B.7C.9D.11 7、一个包含8个顶点的完全图（顶点的编号为1到8），任意两点之间的边权等于两顶点 编号的差的绝对值。例如，顶点3和7之间的边权为|7-3|=4。该图的最小生成树总权 重是多少？ A.7 B.8 C.9 D.10 8、如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6，那么该树的前序遍历是什么？ A.6,4,2,5,10,8,12 CCF CSP-S2025第一轮C+语言试题 第1页共13页 B.6,4,5,2,10,12,8 C.2,4,5,6,8,10,12 D.12,8,10,5,2,4,6 9、一个0-1背包问题，背包容量为20。现有5个物品，其重量和价值分别 为7,5,4,3,6和15,12,9,7,13。装入背包的物品能获得的最大总价值是多少？() A.43B.41C.45D.44 10、在一棵以结点1为根的树中，结点12和结点18的最近公共祖先(LCA)是结点4。那 么下列哪个结点的LCA组合是不可能出现的？()？ ALCA(12,4)=4B.LCA(18,4)=4C.LCA(12,18,4)=4D.LCA(12,1)=4 11、递归关系式T(m=2T(n/2)+O(n)描述了某个分治算法的时间复杂度。请问该算法 的时间复杂度是多少？() A O(n)B O(nlogn)C O(n2)D O(n2logn) 12、在一个初始为空的最小堆(min-heap)中，依次插入元素20,12,15,8,10,5。然后连续执 行两次“删除最小值”(delete-mim)操作。请问此时堆顶元素是什么？ A.10B.12C.15D.20 13、1到1000之间，不能被2,3,5中任意一个数整除的整数有多少个？() A.266B.267C.333D.334 14、斐波那契数列的定义为F(0=0,F(1)=1,Fn)=Fn-1)+Fn-2)。使用朴素递归方法计 算F)的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线 性的。造成这种巨大差异的根本原因是？() A.递归函数调用栈开销过大 B操作系统对递归深度有限制 C朴素递归中存在大量的重叠子问题未被重复利用 D.动态规划使用了更少的数据存储空间 15、5个独立的、不可抢占的任务A1,A2,A3,A4,A5需要在一台机器上执行（从时间0开始执 行)，每个任务都有对应的处理时长和截止时刻，按顺序分别为3,4,2,5,1和5,10,3,15,11。 如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执 行哪个任务？ A处理时间最短的任务A5B.截止时间最早的任务A3 C.处理时间最长的任务A4D.任意一个任务都可以 CCF CSP-S2025第一轮C+语言试题 第2页共13页 二、阅读程序（程序输入不超过数组或字符串定义的范围：判断题正确填√， 错误填×：除特殊说明外，判断题1.5分，选择题3分，共计40分) (1) 01 #include <algorithm> 02 #include <cstdio> 03 #include <cstring> 04 bool flag[27]; 05 int n; 06 int p[27]; 07 int ans=0; 08 void dfs(int k){ 09 fk=n+1){ 10 十+ans, 11 return; 12 } 13 for (int i=1;i<=n;++i){ 14 if (flag[il)continue; 15 if (k>1&&i=p[k-1]+1)continue; 16 p[k]=i; 17 flag[i]=true; 18 dfs(k+1); 19 flag[i]false; 20 21 return; 22 23 int mainOf 24 scanf("od",&n); 25 dfs(1); 26 printf("od n",ans); 27 return 0: 28 29 ●判断题 16、(1分)当输入的n=3的时候，程序输出的答案为3。（) 17、在dfs函数运行过程中，k的取值会满足1≤k≤+1。() 18、删除第l9行的flag[]-false:,对答案不会产生影响。() ●单选题 19.当输入的n=4的时候，程序输出的答案为()。 A.11B.12C.24D.9 CCF CSP-S2025第一轮C+语言试题 第3页共13页 20.如果因为某些问题，导致程序运行第25行的dfs函数之前，数组p的初值并不全为0， 则对程序的影响是()。 A输出的答案比原答案要小 B.无法确定输出的答案 C程序可能陷入死循环 D.没有影响 21.假如删去第14行的if(flag[i])continue,输入3，得到的输出答案是（)。 A.27B.3C.16D.12 (2) 01 #include <algor ithm> 02 #include <cstdio> 03 #include <cstring> 04 #define ll long long 05 int cnt broken=0; 06 int cnt check=0; 07 int n,k; 08 inline bool check(int h){ 09 printf("now check:%d n",h); 10 ++cnt check: 11 if (cnt broken=2){ 12 printf("You have no egg!n"); 13 return false; 14 } 15 if (h>=k){ 6 ++cnt broken; 17 return true; 18 else 19 return false; 20 } 21 22 inline bool assert ans(int h)f 23 if (h=k){ 24 printf("You are Right using %d checks n",cnt check); 25 return true; 26 else 27 printf("Wrong answer!n"); 28 return false; 29 } 30 31 inline void guess1(int n)f for (int i=1;i<=n;+i){ 33 if(check(①){ 34 assert ans(1); CCF CSP-S2025第一轮C+语言试题 第4页共13页 35 return; 36 } 37 } 38 39 inline void guess2(int n){ 40 int w=0: 41 for(w=1;w*(w+1)/2<n;++w 42 43 for (int ti=w,nh =w;--ti,nh +=ti,nh=std::min(nh,n)){ 44 if (check(nh)){ 45 for (intj=nh-ti+1;j<nh;+j){ 46 if (check(j)){ 47 assert ans(j); 48 return, 49 50 } 51 assert ans(nh); 52 return; 53 } 54 } 55 56 int mainO{ 57 scanf"od%od",&n,&k); 58 int t 59 scanf"od",&t); 60 f(t=1){ 61 guess1(n); 62 else 63 guess2(n); 64 } 65 return 0; 66 注意：下述的“猜测数”为调用check函数的次数（即ent check的值），“猜测正确”的含 义为assert_ans函数return true(执行第25行所在分支)的情况；所有输入保证1≤k≤n)。 ●判断题 22.当输入为"651"时，猜测次数为5；当输入为"652"时，猜测次数为3。() 23.不管输入的n和k具体为多少，2时的猜测数总是小于等于=1时的猜测数。（) 24不管=1或t=2,程序都一定会猜到正确结果。 () ●单选题 25.函数guessl在运行过程中，cnt broken的值最多为？() CCF CSP-S2025第一轮C++语言试题 第5页共13页 A.0 B.1 C.2 D.n 26.函数guess2在运行过程中，最多使用的猜测次数的量级为() A.O(n)B.O(n2)C.O(n)D.Ologn) 27.当输入的=100的时候，代码中=1和=2分别需要的猜测次数最多分别为() A.100,14B.100,13C.99,14D.99,13 (3) 01 #include <algorithm> 02 #include <cstdio> 03 #include <cstring> 04 #include <vector> 05 #define ll long long 06 int n,m; 87 std::vector<int>k,p; 08 inline int mpow(int x,int k){ 89 int ans =1; 10 for (k;k>>=1,x=x*x){ 11 if k&1) 12 ans ans x; 13 } 14 return ans; 15 } 16 std:vector<int>ans1,ans2; 17 int cntl,cnt2; 18 inline void dfs(std::vector<int&ans,int&cnt,int l,int r,int v){ 19 fa>){ 20 ++cnt; 21 ans.push back(v); 22 return; 23 } 24 for (int i=1;i<=m;+i){ 25 dfs(ans,cnt,I+1,r,v+k[l]mpow(i,p[l])); 26 } 27 return; 28 29 std::vector<int>cntans1; 30 int mainO{ 31 scanf("odod",&n,&m); 32 k.resize(n+1); 33 p.resize(n+1); 34 for (int i=1;i<=n;++i){ CCF CSP-S2025第一轮C+语言试题 第6页共13页 35 scanf("odod",&k[i],&pi]); 36 } 37 dfs(ans1,cntl,1,n>>1,0); 8 dfs(ans2,cnt2,(n>>1)+1,n,0); 39 std::sort(ans1.beginO,ans1.endO); 40 int newcntl =1: 41 cntans1.push_back(1); 42 for (int i=1;i<cntl;++i){ 43 if (ans1[i]ans1[newcnt1 -1]){ 44 ++cntanslnewcnt1-1]; 45 else 46 ans1[newent1++]=ans1[i]; cntans1.push_back(1); 48 49 } 50 cntl =newcntl; 51 std::sort(ans2.begin0,ans2.endO); 52 int las=0; 53 ll ans =0: 54 for (int i=cnt2-1;i>=0;--i){ 55 for (las cntl &ans1[las]+ans2[i]<0;++las) 56 57 if (las cntl &ans1[las]ans2[i]=0) 58 ans +=cntans1[las]; 59 } 60 printf("olldn",ans); 61 return 0; 62 ●判断题 28.删除第51行的std:sort(ans2.begin0,ans2.end0),后，代码输出的结果不会受 到影响。() 29.假设计算过程中不发生溢出，函数mpow(x,k)的功能是求出x的取值。 30.代码中第39行到第50行的目的是为了将ams1数组进行“去重”操作。（) ●单选题 31.当输入为31512-1212时，输出结果为() A.4 B.8C.0 D.10 CCF CSP-S2025第一轮C+语言试题 第7页共13页 32、记程序结束前pp数组元素的最大值为PP,则该代码的时间复杂度是()。 A.O(n)B.O(m"log m")C.O(m logm")D.O(ma (logm2+log P)) 33、本题所求出的是()。 A.满足a,b,c∈[1，m]的整数方程3+b3=c3的解的数量 B.满足a,b,c∈[1，m]的整数方程r2+b2=c2的解的数量 C.满足xi∈[0，m的整数方程∑k·x”-0的解的数量 D.满足Ⅺ∈[1，m]的整数方程∑k,·x”=0的解的数量 三、完善程序（单选题，每小题3分，共计30分） (I)(特殊最短路)给定一个含N个点、M条边的带权无向图，边权非负。起点 为S,终点为T。对于一条S到T的路径，可以在整条路径中，至多选择一条边 作为“免费边”：当第一次经过这条被选中的边时，费用视为0：如果之后再次 经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从S到T的最 小总费用。 以下代码求解了上述问题。试补全程序。 01 #include <algorithm> 02 #include <iostream 03 #include <queue> 84 #include <vector> 05 using namespace std; 86 87 const long long INF=1e18; 08 09 struct Edge 18 int to; 11 int weight; 12 } 13 14 struct State{ 15 long long dist, 16 int u; 17 int used freebie;//0 for not used,1 for used 18 bool operator(const State &other)const 19 return dist other.dist; 20 21 CCF CSP-S2025第一轮C+语言试题 第8页共13页 22 23 int mainO{ 24 int n,m,s,t; 25 cin >n>>m>>s>>t; 26 27 vector<vector<Edge>>adj(n+1); 28 for (int i=0;i<m;+i){ 29 int u,v,w; 30 cin >u>>v>>w, 31 adjlu].push back(v,w)); 32 adj[v].push_back({u,w}); 33 34 35 vector<vector<long long>>d(n+1,vector<long long>(2,INF)); 36 priority_queue<State,vector<State>,greater<State>>pq; 37 38 d[s][o]=0; 39 pq.push({0,s,_①})： 4日 41 while (!pq.empty(){ 42 State current=pq.topO; 43 Pq-popO; 44 45 long long dist current.dist; 46 int u =current.u; 47 int used current.used freebie; 48 49 if(dist>②){ 50 continue; 51 } 52 53 for (const auto &edge:adj[u]){ 54 int v=edge.to; 55 int w-edge.weight; 56 57 if(du][used+w<③){ 8 ③=dlu[used]+w 9 pq.push({_③，V,used}方 6 if (used=0){ if(④<dI1){ 64 d[v][1]=d[u][used]; CCF CSP-S2025第一轮C+语言试题 第9页共13页 65 pq.push({d[v][1],v,1)); 66 67 68 69 70 71 cout<⑤<end; 72 return 0; 73 34.①处应该填 A.0 B.1 C.-1 D.false 35.②处应该填 A.d[u][!used] B.d[u][used] C.d[t][used] D.INF 36.③处应该填 A.d[[1] B.d[v][used] C.d[u][used] D.d[v][o] 37.④处应该填 A.d[v][o] B.d[v[1] C.d[u][o] D.d[u][1] 38.⑤处应该填 A.d[t[1] B.d[t][o] C.min(d[t][o],d[t][1]) D.d[t[o]+d[[1] (2)工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有条 生产线（编号0~-1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产 线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退 货（结果记为1），否则正常收货（记为0）。受售后压力限制，在所有发货批次中，最多 只能有k次退货（即结果为1的次数k)。工厂的目标是，设计最少的间接测试轮数w(发 货总批次)，保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。 以下程序实现了工厂的目标，包含两部分：)确定w的最小值，并设计最优测试方案：)根 据测试结果推断存在缺陷的生产线。该程序确定w最小值的方法为：由于不同的生产线故 障时，测试应当返回不同的结果，因此w轮测试的可能结果总数不应少于生产线数量。 test subset(0函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码 表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未 给出。 CCF CSP-S2025第一轮C+语言试题 第10页共13页 试补全程序。 01 #include <algorithm> 02 #include <cstddef 03 #include <iostream> 04 #include <vector> 05 using namespace std; 06 07 long long comb(int w,int i){ 08 if (i<oli>w){ 09 return 0; 10 11 long long res=1; 12 for (int t=1;t<=i;++t){ 13 res=res *(w-t+1)/t; 14 15 return res; 16 1 18 ∥计算长度为w、1的个数≤k的码字总数 19 long long count patterns(int w,int k){ 20 long long total=0; 21 for (int t=0;t<=min(w,k);++t) 22 total +=comb(w,t); 23 } 24 return total; 25 } 26 27 ∥抽象测试接口 28 int test subset(const vector<vector<int>>&plan); 29 30 int solve(int n,int k){ 31 ∥三第1步：求最小w三 32 intw=1: 33 while(①){ 34 ++W, 35 } 36 cout<<w<<endl; 37 38 ∥一第2步：生成测试方案 vector<vector<int>code(n,vector<int(w,0)); 40 int idx=0; 41 for (int ones =0;ones<=k &idx<n;+ones){ CCF CSP-S2025第一轮C+语言试题 第11页共13页 42 vector<int>bits(w,0); 43 fill(bits.beginO,bits.begin+ones,1); 44 do{ for (int b=0;b<w;++b){ 46 code[idx][b]bits[b]; 47 } 48 ++idx; 49 if (idx>=n){ 50 break; 51 52 }while(_②)； 53 } 54 55 vector<vector<int>>plan(w); 56 for (int i=0;i<w;++i){ 57 for (int j=0;j<n;++j){ 58 f(③){ 59 plan[i].push back(i); 60 } 61 62 } 63 64 ∥=1 第3步：调用测试接口一 65 int signature=test_subset(plan); 66 67 ∥一第4步：结果解码 68 vector<int sig bits(w,0); 69 for (int i=0;i<w;+i){ 70 f(④){ 71 sig bits[i]=1; 72 } 73 74 75 for (int j=0;j<n;++j){ 76 if(_⑤)returnj; 11 } 78 } 79 80 int mainO{ 81 int n,k; 82 cin >n>>k; 83 int ans solve(n,k); 84 cout <ans <endl: CCF CSP-S2025第一轮C+语言试题 第12页共13页 85 return O; 86 39.①处应该填 A.(1<w<n B.count patterns(w,k)<n C.count patterns(k,w)<n D.comb(w,k)<n 40.②处应该填 A.next permutation(bits.begin0,bits.endO) B.prev_permutation(bits.begin0,bits.endO) C.next permutation(bits.beginO,bits.beginO+ones) D.prev_permutation(bits.beginO,bits.beginO+ones) 41.③处应该填 A.G>i)&1 B.(i>)&1 C.code[i][j]=1 D.code[il[i]=1 42.④处应该填 A.(signature>>i)&1 B.(signature>>i）n1 C.signature (1<<i) D.(signature>>i)1 43.⑤处应该填 A.is permutation(codei.beginO,codeil.endo,sig bits.begino) B.code[j]=sig bits C.plan[j]-sig bits D.code[jl[i]=sig_bits[i] CCF CSP-S2025第一轮C+语言试题 第13页共13页