#10626. 提高组CSP-S2025初赛模拟卷9

提高组CSP-S2025初赛模拟卷9

提高组CSP - S2025初赛模拟卷9

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

  1. 以下选项中,()不属于Linux操作系统。 {{ select(1) }}
  • Debian
  • Harmony
  • Ubuntu
  • Fedora
  1. 下面的C++代码构成的是()类型的数据结构。
typedef struct LinkList{
int value;
LinkList* Lft;
LinkList* rgt;
}LinkList,LinkNode;
bool ListInit(LinkList &LL){
LL =new LinkNode;
if(!LL)
return false;
LL->lft= NULL;
LL->rgt = NULL;
LL->value=-1;
return true;
}

{{ select(2) }}

  • 双向链表
  • 单向链表
  • 循环链表
  • 双向栈
  1. 后缀表达式134+5*567/-的前缀表达式为( )。 {{ select(3) }}
  • 1+34*5-56/7
  • -*1+345/567
  • -*+1345/567
  • -1+34*556/7
  1. 以下选项中属于面向对象的解释型高级语言的是()。 {{ select(4) }}
  • C++
  • C
  • Fortran
  • Python
  1. 高斯消元法不能用于求解()。 {{ select(5) }}
  • 线性方程组
  • 逆矩阵
  • 第k个质数
  • 行列式
  1. 以下哪个说法是正确的?() {{ select(6) }}
  • 在CSP - J/S初赛中交卷后,考试结束前,可以回考场取遗忘的身份证
  • IOI参赛选手可携带已关机的手机并放在自己座位后面的包里
  • IOI参赛选手在比赛时间内去厕所的时候可携带手机
  • CCF的全称是中国计算机学会
  1. 下列关于树的描述中正确的是()。 {{ select(7) }}
  • 在含有n个结点的最小生成树中,边数只能是(n - 1)条
  • 在哈夫曼树中,叶子结点的个数比非叶子结点的个数多1或2
  • 完全二叉树一定是二叉排序树
  • 在二叉树的后序遍历序列中,若结点u在结点v之前,则u一定是v的祖先
  1. 有11个黑球和9个红球,将球依次取出,剩下的球全是一种颜色就结束,最后只剩下红球的概率为()。 {{ select(8) }}
  • 5/12
  • 2/5
  • 1/2
  • 9/20
  1. 关于图G=(V, E),顶点数为n,边数为m,下列说法中正确的是()。 {{ select(9) }}
  • Prim算法用到了二分算法的思想
  • Kruskal算法和Prim算法只有一种用到了贪心算法的思想
  • 如果使用邻接表来存储图G,并使用优先队列进行优化,Prim算法的时间复杂度可以从(O(n^{2}))缩减为(O(m log n))
  • 基于并查集的Kruskal算法的时间复杂度为(O(m log n))
  1. 对长度为x的有序单链表,若检索每个元素的概率相等,则顺序检索到表中任一元素的平均检索长度为( )。 {{ select(10) }}
  • x/2
  • ((x + 1)/2)
  • ((x - 1)/2)
  • x/3
  1. 下列选项中哪个不属于与初等数论有关的定理或者算法?() {{ select(11) }}
  • 欧拉定理
  • 裴蜀定理
  • 中国剩余定理
  • 欧拉路
  1. 有如下递归代码(假设非负整数a ≤b):
int fun(int a,int b){
while(a>0)
{
int tmp=a;
a=b%a;
b=tmp;
}
return b;
}

最坏情况下程序的时间复杂度为( )。 {{ select(12) }}

  • (O(log n))
  • (O(n))
  • (O(n log n))
  • (O(n^{2}))
  1. 一堆卡片共3234张,若每次取相同的质数张,若干次后刚好取完,不同的取法有A种;若每次取相同的奇数张,若干次后刚好取完,不同的取法有B种。则(A + B=)( )。 {{ select(13) }}
  • 17
  • 16
  • 15
  • 14
  1. 从乘法算式(1×2×3×4×\cdots×26×27)中最少要删掉( )个数,才能使得剩下的数的乘积是完全平方数。共有( )种不同的删除方法。 {{ select(14) }}
  • 4 3
  • 5 3
  • 5 2
  • 4 2
  1. A是一个两位数,它的6倍是一个三位数B,如果把B放在A的左边或者右边得到两个不同的五位数,并且这两个五位数的差是一个完全平方数(整数的平方),那么A的所有可能取值之和为()。 {{ select(15) }}
  • 135
  • 144
  • 145
  • 146

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特殊说明外,判断题每题1.5分,选择题每题3分,共计40分)

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=1e5+10;
04
05 priority_queue<int>q1;
06 priority_queue<int,vector<int>,greater<int>>q2;
07 int n,a;
08 int main(){
09 cin>>n;
10 cin>>a;
11 cout<<a<<" ";
12 q1.push(a);
13 for (int i=2;i<=n; i++){
14 cin>>a;
15 if(a>q1.top())
16 q2.push(a);
17 else
18 q1.push(a);
19 while (abs((int)(q1.size()-q2.size()))>1)
20 if (q1.size()>q2.size()){
21 q2.push(q1.top());
22 q1.pop();
23 }else {
24 q1.push(q2.top());
25 q2.pop();
26 }
27 if(i%2){
28 cout<<(q1.size()>q2.size()?q1.top():q2.top())<<" ";
29 }
30 }
31 return 0;
32 }

判断题

  1. 若程序输入5 3 2 1 4 5,则最终输出为3 2 3。 {{ select(16) }}
  • √
  • ×
  1. (2分)若将第15行中的>改为>=,程序输出一定不会改变。 {{ select(17) }}
  • √
  • ×
  1. 若将头文件#include <bits/stdc++.h>改成#include <stdio.h>,程序仍能正常运行。 {{ select(18) }}
  • √
  • ×

选择题

  1. 若输入4 3 5 2 7,则输出是什么?() {{ select(19) }}
  • 3 3 3 3
  • 3 3
  • 3 3 5
  • 3 5
  1. (4分)若将第27行改为i%2==0,则输入4 3 5 2 7时,输出是什么?() {{ select(20) }}
  • 3 3
  • 3 5 3
  • 3 2 3
  • 3 5 5

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define INF 0x3f3f3f3f
04 const int N=1e2+10,M=5e3+10;
05
06 int n,m;
07 int a[N][N];
08 int d[N],f[N];
09 void p(){
10 for (int i=1;i<=n; i++){
11 f[i]=0;
12 d[i]=INF;
13 }
14 f[1]=0;
15 d[1]=0;
16 for (int i=1;i<n; i++){
17 int mn=INF;
18 int t;
19 for (int j=1;j<=n; j++){
20 if((f[j]^1)&&d[j]<mn){
21 t=j;
22 mn=d[j];
23 }
24 }
25 f[t]=1;
26 for (int j=1;j<=n; j++){
27 if(a[t][j]+1==0)
28 continue;
29 d[j]=min(d[j],mn+a[t][j]);
30 }
31 }
32 }
33 int dd[N];
34 int dfs(int u){
35 if(u==1)
36 return 0;
37 for (int i=1;i<=n;i++){
38 if(a[i][u]==-1)
39 continue;
40 if (a[i][u]+d[i]==d[u]){
41 a[i][u]<<=1;
42 a[u][i]<<=1;
43 for (int j=1;j<=n; j++){
44 f[j]=0;
45 dd[j]=INF;
46 }
47 f[1]=0;
48 dd[1]=0;
49 for (int j=1; j<=n;j++){
50 int mn=INF;
51 int id;
52 for (int k=1; k<=n; k++){
53 if((f[k]&1)||dd[k]>=mn)
54 continue;
55 id =k;
56 mn=dd[k];
57 }
58 f[id]^=1;
59 if(id ==n)
60 break;
61 for (int k=1; k <=n; k++){
62 if(a[id][k]<=-1)
63 continue;
64 dd[k]=min(dd[k],mn+a[id][k]);
65 }
66 }
67 int tmp = dd[n];
68 a[i][u]>>=1;
69 a[u][i]>>=1;
70 return max(tmp,dfs(i));
71 }
72 }
73 return 0;
74 }
75 int main(){
76 memset(a,-1,sizeof a);
77 cin>>n>>m;
78 for(int i=0;i<m;i++){
79 int u,v,W;
80 cin>>u>>v>>w;
81 a[u][v]=a[v][u]=w;
82 }
83 p();
84 int ans =d[n];
85 cout<<dfs(n)- ans;
86 return 0;
87 }

程序输入为一张带权无向连通图且没有重边,其中n(n ≤100)为顶点数,m为边数,边权不超过1000000,完成下面的判断题和选择题。

判断题

  1. 函数P的时间复杂度为(O(n^{2}))。 {{ select(21) }}
  • √
  • ×
  1. 第76行中a数组的初始值为(2^{31}-1)。 {{ select(22) }}
  • √
  • ×
  1. 最终的输出值可能为负。 {{ select(23) }}
  • √
  • ×
  1. 若输入5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2,则输出为2。 {{ select(24) }}
  • √
  • ×

选择题

  1. 若将第14行改为f[1]=1,则按照第24题的输入,最终的输出为()。 {{ select(25) }}
  • 2
  • -6
  • 1061109567
  • -1061109567
  1. 若将第41行和第42行中的<<=1改为*=3,第68行和第69行中的>>=1改为/=3,则按照第24题的输入,最终的输出为()。 {{ select(26) }}
  • 6
  • 8
  • 2
  • 1

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=1e2+10;
04
05 int n,m;
06 int fx[]={-1,1,0,0};
07 int fy[]={0,0,-1,1};
08 vector<pair<int,int>>f[N][N];
09 int vis[N][N],a[N][N];
10 int main(){
11 cin>>n>>m;
12 for(int i=0;i<m;i++){
13 int x,y,xx,yy;
14 cin>>x>>y>>xx>>yy;
15 f[x][y].push_back({xx, yy});
16 }
17 int ans =1;
18 a[1][1]=1;
19 queue<pair<int,int>>q;
20 q.push({1,1});
21 vis[1][1]=1;
22 while (!q.empty()){
23 pair<int,int>u=q.front();
24 q.pop();
25 for (int i= 0;i<4;i++){
26 int xx =u.first+ fx[i],yy =u.second+fy[i];
27 if (xx<1||xx>n||yy<1||yy>n||vis[xx][yy])
28 continue;
29 vis[xx][yy]=1;
30 q.push({xx,yy});
31 }
32 for (int i=0;i<f[u.first][u.second].size();i++){
33 pair<int,int>v=f[u.first][u.second][i];
34 if(vis[v.first][v.second])
35 continue;
36 if(a[v.first][v.second]==0)
37 ans++;
38 else
39 continue;
40 a[v.first][v.second]=1;
41 for (int j=0;j<4;j++){
42 int xx=v.first+fx[j],yy=v.second+fy[j];
43 if(xx<1||xx>n||yy<1||yy>n)
44 continue;
45 if(vis[xx][yy]){
46 q.push({v.first,v.second});
47 vis[v.first][v.second] =1;
48 break;
49 }
50 }
51 }
52 }
53 cout<<ans;
54 return 0;
55 }

假设程序的输入是一个NxN的网格,N不超过100,M是对网格的M种相同的约束,M不超过200000。

判断题

  1. 若将第27行中的if语句改为if(vis[xx][yy]||(!a[xx][yy]),输出结果不变。 {{ select(27) }}
  • √
  • ×
  1. 若输入为3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1,则输出为5。 {{ select(28) }}
  • √
  • ×

选择题

  1. 该算法的时间复杂度为( )。 {{ select(29) }}
  • (O(N^{2}))
  • (O(M))
  • (O(N + M))
  • (O(N^{2}+M))
  1. 若输入4 8 1 1 1 2 1 1 3 4 1 1 2 1 1 2 1 3 1 3 3 1 3 4 4 2 2 1 4 1 2 2,则输出为( )。 {{ select(30) }}
  • 6
  • 7
  • 8
  • 9
  1. 若将第25行到第31行注释掉,输入与第30题相同的数据,则输出为( )。 {{ select(31) }}
  • 6
  • 7
  • 8
  • 9
  1. (4分)如果不在第37行进行ans++,而是在第29行和第47行进行ans++,然后输入与第30题相同的数据,则输出为()。 {{ select(32) }}
  • 6
  • 7
  • 8
  • 9

三、完善程序(单选题,每小题3分,共计30分)

(1)题目描述:

小J有一个长度为n(1 ≤n ≤1000)的a数组,小P有一个长度为m(1≤m≤1000)的b数组。现在小J与小P要分别从各自的数组中选出k(1≤k≤10)个数字,小J选出的数字中最大的数字与小P选出的数字中最大的数字进行比较,小J选出的数字中次大的数字与小P选出的次大的数字进行比较,以此类推。如果小J选出的每个数字都比相对应的小P选出的数字大的话,小J就获得了胜利。 请求出在所有选出k个数字的情况中,有多少种情况小J可以获胜,输出方案数对1000000009取模的结果。

01 #include<bits/stdc++.h>
02 #define ll long long
03 using namespace std;
04 const int N=1e3+10;
05 const ll mod=1e9+9;
06
07 int n,m,k;
08 int a[N],b[N];
09 ll f[2][N][20];
10 int main(){
11 cin>>n>>m>>k;
12 for (int i=1; i<=n; i++)
13 cin>>a[i];
14 for (int i=1;i<=m;i++)
15 cin>>b[i];
16 sort(a+1,a+1+n),sort(b+1,b+1+m);
17 for (int i=0;i<=1; i++){
18 for (int j=0;j<=m; j++){
19 f[i][j][0]=1;
20 }
21 }
22 for (int i=1;i<=n;i++){
23 int id=i% 2;
24 for (int j=1;j<=m;j++){
25 for (int t=1;t<=k;t++){
26 ①;
27 ②;
28 f[id][j][t]=(f[id][j][t]+f[id][j-1][t])%mod;
29 ③;
30 if(a[i]>b[j])
31 ④;
32 }
33 }
34 }
35 cout<<⑤;
36 return 0;
37 }
  1. ①处应填()。 {{ select(33) }}
  • f[i][j][t]=0
  • f[i][j][t]=f[i-1][j-1][t-1]
  • f[id][j][t]=0
  • f[id][j][t]=f[id-1][j-1][t-1]
  1. ②处应填()。 {{ select(34) }}
  • f[id][j][t]+=f[id-1][j][t]
  • f[id][j][t]=(f[id][j][t]+f[id-1][j][t])% mod
  • f[id][j][t]+=f[id^1][j][t]
  • f[id][j][t]=(f[id][j][t]+f[id^1][j][t])%mod
  1. ③处应填()。 {{ select(35) }}
  • f[id][j][t]=(f[id][j][t]-f[id^1][j-1][t])% mod
  • f[id][j][t]=(f[id][j][t]-f[id^1][j-1][t-1])% mod
  • f[id][j][t]=(f[id][j][t]-f[id^1][j-1][t-1]+mod)% mod
  • f[id][j][t]=(f[id][j][t]-f[id^1][j-1][t]+mod)% mod
  1. ④处应填()。 {{ select(36) }}
  • f[id][j][t]=(f[id][j][t]+1)%mod
  • f[id][j][t]=(f[id][j][t]+f[id^1][j-1][t])%mod
  • f[id][j][t]=(f[id][j][t]+f[id^1][j-1][t-1]+1)%mod
  • f[id][j][t]=(f[id][j][t]+f[id^1][j-1][t-1])%mod
  1. ⑤处应填()。 {{ select(37) }}
  • f[n^1][n][k]
  • f[n&1][m][k]
  • f[n^1][m][k]
  • f[n][m][k]

(2)题目描述:

小J想要制造k(1≤k≤100000)台机器人,每台机器人有N (1 ≤N ≤100000)个位置必须装上控制器,小J可以选择不同型号的控制器安装在每个位置上,每种型号的花费不同。 为了让k台机器人看起来不那么假,小J希望没有两台机器人的控制器是完全相同的。对于任意两台机器人来说,至少要有一个位置,在这个位置上两台机器人安装了不同的控制器(题目保证控制器种类总能满足需求) 现在小J希望他的机器人造价尽可能低,请计算最小费用。 输入m表示第i个位置可以安装的控制器数,p[i]j表示在第i个位置安装第j种控制器的花费。

01 #include<bits/stdc++.h>
02 #define fi first
03 #define se second
04 #define ll long long
05 using namespace std;
06 typedef pair<int,int> PII;
07 const int N=1e5+10;
08
09 int n,k;
10 int m[N],p[N][20],tmp[N];
11 int a[N][20];
12 struct node{
13 ll x,y,v;
14 bool operator<(const node &t) const{
15 ①;
16 }
17 };
18 int main(){
19 cin>>n>>k;
20 vector<PII>t;
21 for (int i=1;i<=n; i++){
22 cin>>m[i];
23 for (int j=1;j<=m[i]; j++){
24 cin>>p[i][j];
25 }
26 sort(p[i]+1,p[i]+1+m[i]);
27 if(m[i]>1)
28 ②;
29 else
30 t.push_back({-p[i][1],i});
31 }
32 sort(t.begin(),t.end());
33 for (int i=1;i<=n; i++){
34 int id=t[i-1].se;
35 for (int j=1;j<=m[id];j++){
36 a[i][j]=p[id][j];
37 }
38 tmp[i]=m[id];
39 }
40 for (int i=1;i<=n;i++)
41 m[i]=tmp[i];
42 ll x,y,V=0;
43 for(int i=1;i<=n; i++){
44 V+=a[i][1];
45 }
46 for (int i=1;i<=n; i++){
47 if(t[i-1].fi>=0)
48 x=i;
49 break;
50 }
51 }
52 ll ans=V;
53 k--;
54 priority_queue<node> q;
55 ③;
56 while(!q.empty()&&k){
57 k--;
58 node u=q.top();
59 q.pop();
60 x=u.x,y=u.y,v=u.v;
61 ans+=v;
62 if(y<m[x])
63 ④;
64 if(x<n)
65 q.push({x+1,2,v-a[x+1][1]+a[x+1][2]});
66 if(x<n&&y==2)
67 ⑤;
68 }
69 cout<<ans;
70 return 0;
71 }
  1. ①处应填( )。 {{ select(38) }}
  • return v<t.v
  • return v>t.v
  • return x>t.x
  • return y>t.y
  1. ②处应填()。 {{ select(39) }}
  • t.push_back({-p[i][1],i})
  • t.push_back({p[i][1],i})
  • t.push_back({p[i][m[i]]-p[i][1],i})
  • t.push_back({p[i][2]-p[i][1],i})
  1. ③处应填()。 {{ select(40) }}
  • q.push({x,1,0})
  • q.push({x,1,v})
  • q.push({x,2,v+a[x][2]-a[x][1]})
  • q.push({x,2,v})
  1. ④处应填()。 {{ select(41) }}
  • q.push({x,y+1,v-a[x][y]+a[x][y+1]})
  • q.push({x,y+1,v+a[x][y+1]})
  • q.push({x,y,v-a[x][y]+a[x][y+1]})
  • q.push({x,y,a[x][y+1]-a[x][y]})
  1. ⑤处应填()。 {{ select(42) }}
  • q.push({x+1,y+1,v+a[x+1][y+1]-a[x+1][y]})
  • q.push({x+1,2,v-a[x][2]+a[x][1]-a[x+1][1]+a[x+1][2]})
  • q.push({x+1,2,v+a[x][2]-a[x][1]+a[x+1][2]-a[x+1][1]})
  • q.push({x+1,2,v+a[x+1][2]-a[x+1][1]})
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 闽ICP备2024031974号-1
  3. Powered by Hydro v5.0.0-beta.3 Community, Modified by Robinchen