CSP-S 2024 提高组初赛第一轮试题

一、 单项选择题（共15题，每题2分，共计30分）

1. 在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？( )

{{ select(1) }}

• pwd
• cd
• ls
• echo

2. 假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？( )

{{ select(2) }}

• O(n)
• O(logn)
• O(nlogn)
• O(1)

3. 在C++中，以下哪个函数调用会造成溢出？( )

{{ select(3) }}

• int foo(){ return 0;}
• int bar(){int x=1;return x; }
• void baz(){ int a[1000];baz();}
• void qux(){ return; }

4. 在一场比赛中，有10名选手参加，前三名将获得金、银、铜牌。若不允许并列、且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？( )

{{ select(4) }}

• 120
• 720
• 504
• 1000

5. 下面哪个数据结构最适合实现先进先出(FIFO)的功能？( )

{{ select(5) }}

• 栈
• 队列
• 线性表
• 二叉搜索树

6. 已知f(1)=1，且对于n≥2有f(n)=f(n-1)+f(⌊n/2⌋)，则f(4)的值为：( )

{{ select(6) }}

• 4
• 5
• 6
• 7

7. 假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？( )

{{ select(7) }}

• 所有顶点的度数均为偶数
• 该图连通
• 该图存在一个欧拉回路
• 该图的边数是奇数

8. 对数组进行二分查找的过程中，以下哪个条件必须满足？( )

{{ select(8) }}

• 数组必须是有序的
• 数组必须是无序的
• 数组长度必须是2的幂
• 数组中的元素必须为整数

9. 考虑一个自然数n以及一个数m，你需要计算n的逆元（即n在m意义下的乘法逆元），下列哪种算法最为适合？( )

{{ select(9) }}

• 使用暴力法依次尝试
• 使用扩展欧几里得算法
• 使用快速幂法
• 使用线性筛法

10. 在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对，表的装载因子为a(0<a<=1)。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为( )

{{ select(10) }}

• O(1)
• O(logn)
• O(1/(1-a))
• O(n)

11. 假设有一棵h层的完全二叉树，该树最多包含多少个结点？( )

{{ select(11) }}

• 2^h-1
• 2^(h+1)-1
• 2^h
• 2^(h+1)

12. 设有一个10个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为4的环？( )

{{ select(12) }}

• 120
• 210
• 630
• 5040

13. 对于一个整数n，定义f(n)为n的各位数字之和。问使f(f(x))=10的最小自然数x是多少？( )

{{ select(13) }}

• 29
• 199
• 299
• 399

14. 设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最坏情况下将这k个1移到字符串最右边所要的交换次数是多少？( )

{{ select(14) }}

• k
• k*(k-1)/2
• (n-k)*k
• (2n-k-1)*k/2

15. 如图是一张包含7个顶点的有向图，如果要删除其中一些边，使得从节点1到节点7没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？( )

{{ select(15) }}

• 1
• 2
• 3
• 4

二、 阅读程序（程序输入不超过数组成字符串定义的范围）

程序1

01 #include<iostream>
02 using namespace std;
03
04 const int N=1000;
05 int c[N];
06
07 int logic(int x,int y){
08     return(x&y)^((x^y)|(~x&y));
09 }
10 void generate(int a, int b, int*c){
11     for(int i=0;i<b; i++){
12         c[i]=logic(a,i)%(b+1);
13     }
14 }
15 void recursion(int depth,int*arr,int size){
16     if(depth<0||size<=1) return;
17     int pivot= arr[0];
18     int i=0,j=size-1;
19     while(i<=j){
20         while(arr[i]<pivot) i++;
21         while(arr[j]>pivot) j--;
22         if(i<=j){
23             int temp= arr[i];
24             arr[i]= arr[j];
25             arr[j]= temp;
26             i++; j--;
27         }
28     }
29     recursion(depth-1,arr,j+1);
30     recursion(depth-1,arr+i,size-i);
31 }
32
33 int main(){
34     int a,b,d;
35     cin>>a>>b>>d;
36     generate(a,b,c);
37     recursion(d,c,b);
38     for(int i=0; i<b;++i) cout<<c[i]<<" ";
39     cout<<endl;
40 }

16. 当1000>=d>=b时，输出的序列是有序的。( )

{{ select(16) }}

• √
• ×

17. 当输入"5 5 1"时，输出为"1 1 5 5 5"( )

{{ select(17) }}

• √
• ×

18. 假设数组c长度无限制，该程序所实现的算法的时间复杂度是O(b)的。( )

{{ select(18) }}

• √
• ×

19. 函数int logic(int x, int y)的功能是( )

{{ select(19) }}

• 按位与
• 按位或
• 按位异或
• 以上都不是

20. (4分)当输入为"10 100 4"时，输出的第100个数是( )

{{ select(20) }}

• 91
• 94
• 95
• 98

程序2

01 #include<iostream>
02 #include<string>
03 using namespace std;
04
05 const int P=998244353, N=1e4+10, M=20;
06 int n,m;
07 string s;
08 int dp[1<<M];
09
10 int solve(){
11     dp[0]=1;
12     for(int i=0; i<n; ++i){
13         for(int j=(1<<(m-1))-1; j>=0; --j){
14             int k=(j<<1)|(s[i]-'0');
15             if(j!=0||s[i]=='1')
16                 dp[k]=(dp[k]+dp[j])%P;
17         }
18     }
19     int ans=0;
20     for(int i=0; i<(1<<m); ++i){
21         ans=(ans+dp[i]*i)%P;
22     }
23     return ans;
24 }
25
26 int solve2(){
27     int ans=0;
28     for(int i=0; i<(1<<n); ++i){
29         int cnt=0;
30         int num=0;
31         for(int j=0; j<n; ++j){
32             if(i&(1<<j)){
33                 num=num*2+(s[j]-'0');
34                 cnt++;
35             }
36         }
37         if(cnt<=m) ans=(ans+num)%P;
38     }
39     return ans;
40 }
41
42 int main(){
43     cin>>n>>m;
44     cin>>s;
45     if(n<=20){
46         cout<<solve2()<<endl;
47     }
48     cout<<solve()<<endl;
49     return 0;
50 }

21. 假设数组dp长度无限制，函数solve()所实现的算法时间复杂度是O(n*2^m)( )

{{ select(21) }}

• √
• ×

22. 输入"11 2 10000000001"时，程序输出两个数32和23( )

{{ select(22) }}

• √
• ×

23. (2分)在n<=10时，solve()的返回值始终小于4^10( )

{{ select(23) }}

• √
• ×

24. 当n=10且m=10时，有多少种输入使得两行的结果完全一致？( )

{{ select(24) }}

• 1024
• 11
• 10
• 0

25. 当n<=6时，solve()的最大可能返回值为( )

{{ select(25) }}

• 65
• 211
• 665
• 2059

26. 若n=8，m=8，solve和solve2的返回值的最大可能的差值为( )

{{ select(26) }}

• 1477
• 1995
• 2059
• 2187

程序3

01 #include<iostream>
02 #include<cstring>
03 #include<algorithm>
04 using namespace std;
05
06 const int maxn=1000000+5;
07 const int P1=998244353,P2=1000000007;
08 const int B1=2,B2=31;
09 const int K1=0,K2=13;
10
11 typedef long long ll;
12
13 int n;
14 bool p[maxn];
15 int p1[maxn], p2[maxn];
16
17 struct H{
18     int h1,h2,l;
19     H(bool b=false){
20         h1=b+K1;
21         h2=b+K2;
22         l=1;
23     }
24     H operator+(const H&h)const{
25         H hh;
26         hh.l=l+h.l;
27         hh.h1=(h1*p1[h.l]+h.h1)%P1;
28         hh.h2=(h2*p2[h.l]+h.h2)%P2;
29         return hh;
30     }
31     bool operator==(const H&h) const{
32         return l==h.l && h1==h.h1 && h2==h.h2;
33     }
34     bool operator<(const H&h) const{
35         if(l!=h.l) return l<h.l;
36         else if(h1!=h.h1) return h1<h.h1;
37         else return h2<h.h2;
38     }
39 }h[maxn];
40
41 void init(){
42     memset(p,1,sizeof(p));
43     p[0]=p[1]=false;
44     p1[0]=p2[0]=1;
45     for(int i=1; i<=n; i++){
46         p1[i]=(ll)B1*p1[i-1]%P1;
47         p2[i]=(ll)B2*p2[i-1]%P2;
48         if(!p[i]) continue;
49         for(int j=2*i; j<=n; j+=i){
50             p[j]=false;
51         }
52     }
53 }
54
55 int solve(){
56     for(int i=n; i; i--){
57         h[i]=H(p[i]);
58         if(2*i+1<=n){
59             h[i]=h[2*i]+h[i]+h[2*i+1];
60         } else if(2*i<=n){
61             h[i]=h[2*i]+h[i];
62         }
63     }
64     cout<<h[1].h1<<endl;
65     sort(h+1,h+n+1);
66     int m=unique(h+1,h+n+1)-(h+1);
67     return m;
68 }
69
70 int main(){
71     cin>>n;
72     init();
73     cout<<solve()<<endl;
74     return 0;
75 }

27. 假设程序运行前能自动将maxn改为n+1，所实现的算法的时间复杂度是O(nlogn)( )

{{ select(27) }}

• √
• ×

28. 时间开销的瓶颈是init()函数( )

{{ select(28) }}

• √
• ×

29. 若修改常数B1或K1的值，该程序可能会输出不同的结果( )

{{ select(29) }}

• √
• ×

30. 在solve()函数中，h[]的合并顺序可以看作是( )

{{ select(30) }}

• 二叉树的BFS序
• 二叉树的先序遍历
• 二叉树的中序遍历
• 二叉树的后序遍历

31. 输入10，输出的第1行是( )

{{ select(31) }}

• 83
• 424
• 54
• 110101000

32. (4分)输入16，输出的第2行是( )

{{ select(32) }}

• 7
• 9
• 10
• 12

三、 完善程序（单选题，每小题3分，共计30分）

程序1 序列合并

#include<iostream>
using namespace std;
const int maxn=100005;
int n;
long long k;
int a[maxn], b[maxn];

int* upper_bound(int* a, int* an, int ai){
    int l=0, r=①;
    while(l<r){
        int mid=(l+r)>>1;
        if(②){
            r=mid;
        } else{
            l=mid+1;
        }
    }
    return ③;
}

long long get_rank(int sum){
    long long rank=0;
    for(int i=0; i<n; i++){
        rank+=upper_bound(b,b+n,sum-a[i])-b;
    }
    return rank;
}

int solve(){
    int l=0, r=④;
    while(l<r){
        int mid=((ll)l+r)>>1;
        if(⑤){
            l=mid+1;
        } else{
            r=mid;
        }
    }
    return l;
}

int main(){
    cin>>n>>k;
    for(int i=0; i<n; ++i) cin>>a[i];
    for(int i=0; i<n; ++i) cin>>b[i];
    cout<<solve()<<endl;
    return 0;
}

33. ①处应该填写( )

{{ select(33) }}

• an-a
• an-a-1
• ai
• ai+1

34. ②处应该填写( )

{{ select(34) }}

• a[mid]>ai
• a[mid]>=ai
• a[mid]<ai
• a[mid]<=ai

35. ③处应该填写( )

{{ select(35) }}

• a+l
• a+l+1
• a+l-1
• an-l

36. ④处应该填写( )

{{ select(36) }}

• a[n-1]+b[n-1]
• a[n]+b[n]
• 2*maxn
• maxn

37. ⑤处应该填写( )

{{ select(37) }}

• get_rank(mid)<k
• get_rank(mid)<=k
• get_rank(mid)>k
• get_rank(mid)>=k

程序2 次短路

#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
const int maxn=2e5+10, maxm=1e6+10, inf=522133279;
int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot=1;
int dis[maxn<<1], *dis2;
int pre[maxn<<1], *pre2;
bool vis[maxn<<1];

void add(int a, int b, int c){
    ++tot; nxt[tot]=head[a]; to[tot]=b; w[tot]=c; head[a]=tot;
}

bool upd(int a, int b, int d, priority_queue<pair<int,int>>& q){
    if(d>=dis[b]) return false;
    if(b<n) ①;
    q.push(②);
    dis[b]=d;
    pre[b]=a;
    return true;
}

void solve(){
    priority_queue<pair<int,int>> q;
    q.push(make_pair(0,s));
    memset(dis, ③, sizeof(dis));
    memset(pre,-1,sizeof(pre));
    dis2=dis+n;
    pre2=pre+n;
    dis[s]=0;
    while(!q.empty()){
        int aa=q.top().second; q.pop();
        if(vis[aa]) continue;
        vis[aa]=true;
        int a=aa%n;
        for(int e=head[a]; e; e=nxt[e]){
            int b=to[e], c=w[e];
            if(aa<n){
                if(!upd(a,b,dis[a]+c,q)) ④;
            } else{
                upd(n+a,n+b,dis2[a]+c,q);
            }
        }
    }
}

void out(int a){
    if(a!=s){
        if(a<n) out(pre[a]);
        else out(⑤);
    }
    printf("%d%c",a%n+1,"\n"[a==n+t]);
}

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    s--,t--;
    for(int i=0; i<m; ++i){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a-1,b-1,c);
    }
    solve();
    if(dis2[t]==inf) puts("-1");
    else{
        printf("%d\n",dis2[t]);
        out(n+t);
    }
    return 0;
}

38. ①处应填( )

{{ select(38) }}

• upd(pre[b],n+b,dis[b],q)
• upd(a,n+b,d,q)
• upd(pre[b],b,dis[b],q)
• upd(a,b,d,q)

39. ②处应填( )

{{ select(39) }}

• make_pair(-d,b)
• make_pair(d,b)
• make_pair(b,d)
• make_pair(-b,d)

40. ③处应填( )

{{ select(40) }}

• 0xff
• 0x1f
• 0x3f
• 0x7f

41. ④处应填( )

{{ select(41) }}

• upd(a,n+b,dis[a]+c,q)
• upd(n+a,n+b,dis2[a]+c,q)
• upd(n+a,b,dis2[a]+c,q)
• upd(a,b,dis[a]+c,q)

42. ⑤处应填( )

{{ select(42) }}

• pre2[a%n]
• pre[a%n]
• pre2[a]
• pre[a%n]+1