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

ID: 156

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

robin

标签>

CSP通关之路

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

在NOI Linux系统终端中,()命令可以用来修改文件名。
{{ select(1) }}

mkdir
cp-a
mv
touch

以下关于二叉排序树的表述中,不恰当的一项是()。
{{ select(2) }}

若左子树不空,则其所有结点的值均小于根结点的值
二叉排序树的根结点一定有最小值或者最大值
若右子树不空,则其所有结点的值均大于根结点的值
二叉排序树的左右子树也分别为二叉排序树

计算机病毒最不容易攻击的是()。
{{ select(3) }}

硬盘
内存
只读光盘
U盘

假设我们有以下C++代码:

unsigned char a=143,b=3,C=4;
a<<=2;
int res =a|(b+c>>1);

则res的值是()。
{{ select(4) }}

使用邻接表表示一个简单有向图,图中包含n个顶点、m条边,则该出边表中边结点的个数为( )。
{{ select(5) }}

n+m
n*(n-1)
m
n*m

()问题不是典型的与动态规划算法相关的问题。
{{ select(6) }}

最长公共子序列
打水
多重背包
最长递增子序列

解决RMQ问题通常使用( )。
{{ select(7) }}

哈夫曼树
并查集
哈希表
稀疏表

以下关于强连通图的说法中,正确的是()。
{{ select(8) }}

图中一定有环
每个顶点的度数都大于0
对于大于1个点的强连通图,任意两个顶点之间都有路径相连
每个顶点至少都连有一条边

甲乙两人进行比赛,每局比赛获胜的概率相同,均为甲获胜的概率为0.4,乙获胜的概率为0.6,现规定两人持续比赛,直到有一方比对方获胜局数多两局时获得一场比赛的胜利,则甲获胜的概率是( )
{{ select(9) }}

2/5
4/9
4/13
1/3

给定地址区间为0~12的哈希表,哈希函数为 (h(x)=x % 13) ,采用二次探查的冲突解决策略(出现冲突后会往后依次探查以下位置:h(x), (h(x)+1^2) , (h(x)-1^2) , (h(x)+2^2) , (h(x)-2^2) , (h(x)+3^2) ,h(x)-3^2,..)。哈希表初始为空表,依次存储(26,36,13,18,39,3,0)后,请问0存储在哈希表的哪个地址中?()
{{ select(10) }}

STL模板中的容器可以分为顺序容器和关联容器,下列选项中,()不属于容器适配器。
{{ select(11) }}

iterator
stack
queue
priority_queue

下面关于C++类继承的说法中,错误的是( )。
{{ select(12) }}

一个类可以继承多个类
一个类可以继承另一个类的子类
一个类可以被多个类继承
抽象类必须被至少一个类继承,否则会发生编译错误

假设G是一张有m个点、n条边的图,小明想找一棵有n个结点的最小生成树,必须删去若干点和()条边才能将其变成这样的一棵树。
{{ select(13) }}

m-n-1
m+n-1
1
m-n+1

一只蚂蚁从一个棱长为2的正方体的一个顶点出发,沿着棱爬,则其爬过所有棱长且回到出发的顶点的最短路径长是()。
{{ select(14) }}

二叉堆算法插入操作和删除操作的时间复杂度分别为()。
{{ select(15) }}

O(log n) 、 O(log n)
O(n) 、 O(n)
O(n) 、 O(log n)
O(log n) 、 O(n)

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

(1)

01 #include <bits/stdc++.h>
02
03 using namespace std;
04
05 const int N=3e5+10;
06 const int mod =1e9+7;
07
08 int n,a[N];
09
10 using ii=pair<int,int>;
11
12 int dp[N];
13 int sum[N];
14
15 int main(){
16 ios::sync_with_stdio(0);
17 cin.tie(0);
18 cin>>n;
19 for (int i=1;i<=n;++i) cin>>a[i];
20 set<ii> s;
21 sum[0]=1;
22 for (int i=1,res=0;i<=n;++i){
23 ii u;
24 while (!s.empty()){
25 u=(*s.rbegin());//*rbegin是反向迭代器
26 if(u.first>a[i]){
27 res=(res-dp[u.second]+mod)% mod;
28 s.erase(u);
29 } else break;
30 }
31 if (s.empty()) dp[i]=sum[i-1];
32 else dp[i]=(res+sum[i-1]-sum[u.second])%mod;
33 if(dp[i]<0)dp[i]+=mod;
34 sum[i]=(sum[i-1]+dp[i])% mod;
35 s.insert({a[i],i});
36 res=(res+dp[i])% mod;
37 }
38 int ans=0;
39 for(ii u:s)ans=(ans+dp[u.second])% mod;
40 cout<<ans<<endl;
41 return 0;
42}

保证输入 (1 ≤ N ≤300000) ,a是一个排列。

判断题(每题2分)

本段代码的时间复杂度为 (O(N)) 。
{{ select(16) }}

本段代码不可能输出负数。
{{ select(17) }}

第19行代码从++i改成i++后,程序仍能正常运行,并且输出结果不变。
{{ select(18) }}

选择题

对于输入

3
2 3 1

程序的输出是( )。
{{ select(19) }}

对于输入

4
2 1 4 3

程序的输出是( )。
{{ select(20) }}

(2)

01 #include<bits/stdc++.h>
02 #define v first
03 #define id second
04 using namespace std;
05
06 typedef long long ll;
07
08 const int N=100010;
09 int n,d,cnt;
10 ll a[N],num[N];
11 int f[N],g[N];
12 typedef pair<int,int>pii;
13
14 pii mx[N<<2];
15
16 pii query(int u,int l,int r,int ql,int qr)
17 {
18 if(ql>qr) return {-1,0};
19 if(ql<=l&&r<=qr) return(mx[u].v?mx[u]:make_pair(-1,0));
20 int mid=(l+r)>>1;
21 if(ql<=mid&&qr>mid) return max(query(u<<1,l,mid,ql,qr),query(u<<1|1,mid+1,r,ql,qr));
22 else if(ql<=mid) return query(u<<1,l,mid,ql,qr);
23 else return query(u<<1|1,mid+1,r,ql,qr);
24 }
25
26 void modify(int u,int l,int r,int pos,pii v)
27 {
28 if(l==r){mx[u]=max(mx[u],v);return;}
29 int mid=(l+r)>>1;
30 if(pos<=mid) modify(u<<1,l,mid,pos,v);
31 else modify(u<<1|1,mid+1,r,pos,v);
32 mx[u]=max(mx[u<<1],mx[u<<1|1]);
33 }
34
35 void print()
36 {
37 int mx=0;
38 for(int i=1;i<=n;i++)if(f[i]>f[mx])mx=i;
39 printf("%d\n",f[mx]);
40 vector<int>ans;
41 ans.push_back(mx);
42 while(g[mx]){int x=g[mx];ans.push_back(x);mx=x;}
43 reverse(ans.begin(),ans.end());
44 for(int x:ans)printf("%d ",x);puts("");
45 }
46
47 int main()
48 {
49 scanf("%d %d",&n,&d); for(int i=1;i<=n;i++)
50 {
51 scanf("%lld",&a[i]);
52 num[i]=a[i];
53 }
54 sort(num+1,num+n+1);
55 cnt=unique(num+1,num+n+1)-num-1;
56 for(int i=1;i<=n;i++)
57 {
58 int x=lower_bound(num+1,num+cnt+1,a[i])-num;
59 int l=upper_bound(num+1,num+cnt+1,a[i]-d)-num-1;
60 int r=lower_bound(num+1,num+cnt+1,a[i]+d)-num;
61 pii ans = max({make_pair(0,0),query(1,1,cnt,1,l),query(1,1,cnt,r,cnt)});
62 f[i]=ans.v+1,g[i]=ans.id;
63 modify(1,1,cnt,x,{f[i],i});
64 }
65 print();
66 return 0;
67 }

保证输入数据中 (1 ≤n ≤10^{5}) , (0 ≤d ≤10^{9}) , (1 ≤a[i] ≤10^{15}) 。

判断题(每题2分)

d非0时,第60行与第61行代码中的l与r值一定不一样。( )
{{ select(21) }}

第23行后应该再加一行代码else return make_pair(-1,0),否则在一些情况下,函数不会返回值,导致未定义行为。( )
{{ select(22) }}

选择题

这段代码的时间复杂度是( )。
{{ select(23) }}

O(N)
O(N log N)
O(N log² N)
O(N²)

如果a[i]的值为10,d的值为3,a数组的值为1 5 6 8 10 12 14 17,那么l和r的值分别为()。
{{ select(24) }}

以下说法中正确的是()。
{{ select(25) }}

如果需要单点修改,区间查询max值,在本段代码中也可以使用树状数组,时间复杂度不变。
如果输入合法,在本段代码中,upper_bound(num+1,num+cnt+1,a[i]-d)和lower_bound(num+1,num+cnt+1,a[i]+d)一定不同。
modify(1,1,cnt,i,f[i])这段代码会递归 (\left\lceil\frac{cnt}{2}\right\rceil) 次。
第60行代码中,int后面的内容可以改成l=lower_bound(num+1,num+cnt+1,a[i]-d)-num,与原来l=upper_bound(num+1,num+cnt+1,a[i]-d)-num-1的作用相同。

(3)

01 #include<bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 const int N=5e5+10;
05 vector<int> e[N];
06 int w[N];
07 int L[N],R[N];
08 int n,m,res;
09
10 void add(int a,int b)
11 {
12 e[a].push_back(b),e[b].push_back(a);
13 }
14
15 void dfs(int u,int fa)
16 {
17 vector<int> S;
18 if(u<=m) return;
19 for(auto v:e[u])
20 {
21 if(v==fa)continue;
22 dfs(v,u);
23 S.push_back(L[v]),S.push_back(R[v]);
24 }
25 sort(S.begin(),S.end());
26 int sz=S.size();
27 if(sz&1) L[u]=R[u]=S[sz/2];
28 else L[u]=S[sz/2-1],R[u]=S[sz/2];
29 for(auto v:e[u])
30 {
31 if(v==fa)continue;
32 if(L[u]>R[v]) res+=L[u]-R[v];
33 else if(L[u]<L[v]) res+=L[v]-L[u];
34 else res+=0;
35 }
36 }
37
38 signed main()
39 {
40 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
41 cin>>n>>m;
42 for(int i=1,a,b;i<n;i++)
43 {
44 cin>>a>>b;
45 add(a,b);
46 }
47 for(int i=1;i<=m;i++)cin>>w[i],L[i]=R[i]=w[i];
48 if(n==2)
49 {
50 cout<<abs(w[1]-w[2])<<"\n";
51 return 0;
52 }
53 dfs(m+1,0);
54 cout<<res<<"\n";
55 return 0;
56 }

题目保证输入是一棵树,其中叶子结点标号为 ([1, M]) , (2 ≤M ≤N ≤500000) ,其他读入的数据均不会大于500000。

判断题(每题2分)

不考虑vector的复杂度,这段代码的时间复杂度为 (O(N)) 。
{{ select(26) }}

删除第28行代码,并删除第27行代码中的"else",程序仍然可以输出相同的结果。
{{ select(27) }}

当 (n=2) 的时候,程序输出不会大于500000。
{{ select(28) }}

选择题

本段代码中res可能达到的最大值为多少?()
{{ select(29) }}

250000000000
125000000000
124999250001
62500000000

假如 (n=5) , (m=3) , (w[1]=10) , (w[2]=20) , (w[3]=30) ,在程序正确运行的前提下,理论上本题res的最小值是多少?()
{{ select(30) }}

以下说法中正确的是()。
{{ select(31) }}

本段代码中每次sort的复杂度最大为O(nlogn),因此,该程序的复杂度为O(n² logn)。
本段代码中的 (dfs(m+1,0)) 改成dfs(1,0),结果不变。
如果读入n条边,程序一定会读入一个环,导致dfs过程出现死循环。
如果给定的是一条链,则输出一定是|w[1]-w[2]|。

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

(1)题目描述:

给定一个只有左右括号的字符串,然后用H、G两种字符来标记这个序列,所有标记H的括号可以组成一个正确的括号序列,所有标记G的括号也组成一个正确的括号序列,然后输出这种标记方案的总数mod2012的值。可以用一个dp来解决问题。

01 #include <iostream>
02 #include<cstring>
03 #include<cmath>
04 #include<cstdio>
05
06 using namespace std;
07
08 const int mod=2012;
09 char s[1005];
10 int n,f[1005][1005],g[1005][1005];
11
12 int main()
13 {
14 scanf("%s",s+1);
15 n=①;
16 int oo=0;
17 f[0][0]=1;
18 for(int i=1;i<=n;++i)
19 {
20 if(s[i]=='(')
21 {
22 oo++;
23 for(int j=0;j<=oo;++j)
24 {
25 if(j)g[j][oo-j]=(g[j][oo-j]+f[j-1][oo-j])%mod;
26 if(oo-j)②;
27 }
28 }
29 else if(s[i]==')')
30 {
31 ③;
32
33 for(int j=0;j<=oo;++j)
34 g[j][oo-j]=④;
35 g[j][oo-j]=(g[j][oo-j]+f[j][oo-j+1])%mod;
36 }
37 for(int j=0;j<=oo;++j)⑤;
38 }
39 printf("%d",f[0][0]);
40 return 0;
41 }

①处应填()。
{{ select(32) }}

strlen(s)
strlen(s+1)
strlen(s)+1
strlen(s+1)-1

②处应填()。
{{ select(33) }}

g[j][oo-j]=(g[j][oo-j]+f[j][oo-j-1])%mod
g[j][oo-j]=(g[j][oo-j]+f[j-1][oo-j])%mod
g[j][oo-j]=(g[j][oo-j]+f[j][oo-j])%mod
g[j][oo-j]=(g[j][oo-j]+f[j-1][oo-j-1])%mod

③处应填()。
{{ select(34) }}

oo++
oo--
oo=0
oo=n

④处应填()。
{{ select(35) }}

(g[j][oo-j]+f[j][oo-j+1])%mod
(g[j][oo-j]+f[j][oo-j])%mod
(g[j][oo-j]+f[j+1][oo-j+1])%mod
(g[j][oo-j]+f[j+1][oo-j])%mod

⑤处应填()。
{{ select(36) }}

f[j][oo-j]=g[j][oo-j],g[j][oo-j]=0
f[j][oo-j+1]=g[j][oo-j],g[j][oo-j]=0
f[j][j]=g[j][oo-j],g[j][oo-j]=0
f[j][j+1]=g[j][oo-j],g[j][oo-j]=0

(2)题目描述:

对n个单词进行加密,过程如下。选择一个英文字母表的排列作为密钥。将单词中的a替换为密钥中的第一个字母,b替换为密钥中的第二个字母,以此类推。请你构造一组密钥,使得对所有单词加密并且按照字典序升序排列后,最初的第ai个单词位于第i个位置,如果不能,输出NE,否则输出DA并且下一行输出一种可行的密钥。可以想到,如果把字典序限制看成一条有序边,可以按照拓扑排序来分配密钥,如果出现环,则说明无解。

01 #include<bits/stdc++.h>
02
03 #define LL long long
04 using namespace std;
05
06 const LL M1=300,M2=30;
07 LL n;
08 string a[M1],a_sort[M1];
09 LL du[M1];
10 queue<LL> qu;
11 vector<LL> ve[M2];
12 LL ans[M2];
13
14 int main(){
15 cin>>n;
16 for(LL i=1;i<=n;i++) cin>>a[i];
17 for(LL i=1;i<=n;i++){
18 LL b;
19 cin>>b;
20 ①;
21 }
22
23 for(LL i=1;i<n;i++){
24 bool flag=true;
25 for(LL j=0;j<②;j++)
26 if(a_sort[i][j]!=a_sort[i+1][j]){
27 ③;
28 du[a_sort[i+1][j]-'a']++;
29 flag=false;
30 break;
31 }
32 if(flag&&④){
33 cout<<"NE";
34 return 0;
35 }
36 }
37
38 for(LL i=0;i<26;i++)if(du[i]==0)qu.push(i);
39
40 LL cnt=0;
41 while(!qu.empty()){
42 LL v=qu.front();
43 qu.pop();
44 ans[v]=cnt;
45 cnt++;
46 for(LL i=0;i<(LL)ve[v].size();i++){
47 du[ve[v][i]]--;
48 if(⑤)qu.push(ve[v][i]);
49 }
50 }
51
52 if(cnt!=26)cout<<"NE";
53 else{
54 cout<<"DA"<<endl;
55 for(LL i=0;i<26;i++){
56 cout<<(char)(ans[i]+'a');
57 }
58 }
59 return 0;
60 }

①处应填()。
{{ select(37) }}

a_sort[i]=a[b]
a_sort[i]=a[i]
a_sort[b]=a[b]
a_sort[b]=a[i]

②处应填()。
{{ select(38) }}

a_sort[i].size()
a_sort[i+1].size()
min(a_sort[i].size(),a_sort[i+1].size())
max(a_sort[i].size(),a_sort[i+1].size())

③处应填()。
{{ select(39) }}

ve[a_sort[i][j]-'a'].push_back(a_sort[i][j]-'a')
ve[a_sort[i][j]-'a'].push_back(a_sort[i+1][j]-'a')
ve[a_sort[i+1][j]-'a'].push_back(a_sort[i][j]-'a')
ve[a_sort[i+1][j]-'a'].push_back(a_sort[i+1][j]-'a')

④处应填()。
{{ select(40) }}

a_sort[i].size()>=a_sort[i+1].size()
a_sort[i].size()==a_sort[i+1].size()
a_sort[i].size()>a_sort[i+1].size()
a_sort[i].size()<a_sort[i+1].size()

⑤处应填()。
{{ select(41) }}

!du[ve[v][i]]
du[ve[v][i]]
~du[ve[v][i]]
-du[ve[v][i]]

#156. 提高组CSP-S2025初赛模拟卷2

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