#4036. CSP-X 2024年山东小学组初赛真题

CSP-X 2024年山东小学组初赛真题

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

  1. (2024)10+(2F)16的运算结果是( )

{{ select(1) }}

  • (100000010110)2
  • (816)16
  • (2071)10
  • (4026)8

2.执行完以下代码后,c的值是( )

int a=9,b=6,c;
c=a/b+0.5;

{{ select(2) }}

  • 1.5
  • 2
  • 2.0
  • 1
  1. 将数组{7,20,4,16,88,0,55,100}中的元素按从大到小的顺序排列,每次可以交换任意两个元素,最少需要交换 ( )次。

{{ select(3) }}

  • 4
  • 5
  • 6
  • 7
  1. 若待排序对象序列在排序前已按其排序码递增顺序排序,则采用 ( )方法比较次数最少。

{{ select(4) }}

  • 直接插入排序
  • 快速排序
  • 归并排序
  • 直接选择排序
  1. 设有一个100阶的对称矩阵保存在二维数组a[100][100],满足a[i][j]=a[j][i],如果采用压缩存储方式按行将矩阵的下三角部分的元素存入一维数组b[]中,a[0][0]存入b[0]中,则a[10][5]在b[]中 ( )位置。

{{ select(5) }}

  • 50
  • 60
  • 51
  • 61
  1. 字符串abcabcabc有多少不同的非空子串? ( )。 {{ select(6) }}
  • 24
  • 36
  • 45
  • 46
  1. 一个栈的输入顺序为1、2、3、4、5、6,下列序列中可能是栈的输出序列是 ( )。

{{ select(7) }}

  • 654312
  • 241356
  • 216543
  • 125346
  1. 一棵二叉树的中序遍历序列为:DGBAECHF,后序遍历序列为:GDBEHFCA,则前序遍历的序列是 ( )。 {{ select(8) }}
  • ABCDFGHE
  • ABDGCEFH
  • ACBGDHEF
  • ACEFHBGD
  1. 对于下面这段代码,如果在主函数里调用f(4,4),在程序运行结束前,f函数共被调用了多少次? ( )
void f(int n,int m){
	if(n&&m){
		for(int i=1;i<=m;i++) f(n-1,i-1);
			}
	}

{{ select(9) }}

  • 15
  • 16
  • 26
  • 27

10.有n个相同结点并且其高度为n的二叉树的数目是 ( )

{{ select(10) }}

  • nn
  • 2n2n
  • 2n12^{n-1}
  • 2(n1)2(n-1)

11.在有n个叶节点的哈夫曼树中,其节点总数为 ( )。 {{ select(11) }}

  • 2n
  • 2n-1
  • 2n+1
  • 不确定

12.n个顶点n条边构成的简单无向图(无重边和自环),下列描述不正确的是 ( )。 {{ select(12) }}

  • 一定有环
  • 不一定有环
  • 如果是连通图有1个环
  • 如果图不连通,至少有2个环

13.以下哪句话与“爱她,就请她吃哈根达斯”等价? ( )。

{{ select(13) }}

  • 不爱她,就不请她吃哈根达斯。
  • 请她吃哈根达斯,就表示爱她。
  • 不请她吃哈根达斯就表示不爱她。
  • 不爱她,也可以请她吃哈根达斯。

14.5个男生3个女生排成一排,3女生都不能相邻,有多少种方案 ( )。 {{ select(14) }}

  • 14400
  • 2400
  • 40320
  • 720

15.由3个a,2个b和1个c构成的所有字符串共有 ( )个。 {{ select(15) }}

  • 720
  • 360
  • 120
  • 60

二、阅读程序(判断题正确选A,错误选B;除了特殊说明外,判断题2分,选择题3分,共40分)

(1)(共12分)

01 #include<cstdio>
02 #include<iostream>
03 #include<cstring>
04 using namespace std;
05 int x[10000];
06 int y[100000000];
07 long long s,sum;
08 int a,b;
09 int main( ){
10    memset(x,-1,sizeof(x));
11    memset(y,1,sizeof(y));
12    a=b=200000;
13    s=a*b;
14    int cnt;
15    for(int i=1;i<=10000;i++){
16        sum+=y[i];
17        cnt=cnt+1;
18    }
19    cout<<sum<<endl;
20    cout<<cnt<<endl;
21    return 0;
22 }

判断题

  1. 语句 memset(x,-1,sizeof(x));执行完后,x[0]=-1。 ( ) {{ select(16) }}
  • 正确
  • 错误
  1. 语句memset(y,1,sizeof(y));执行完后,y[0]= 1。 ( ) {{ select(17) }}
  • 正确
  • 错误
  1. 程序运行后sum的值不是10000。 ( ) {{ select(18) }}
  • 正确
  • 错误
  1. 语句s=a*b;执行完后,s的值是40000000000。 ( ) {{ select(19) }}
  • 正确
  • 错误
  1. 如果内存限制256MB,程序运行没有超内存。 ( )

{{ select(20) }}

  • 正确
  • 错误
  1. 程序运行后,最后输出cnt的值一定是10000 ( )

{{ select(21) }}

  • 正确
  • 错误

(2)(共13分)

01 #include<bits/stdc++.h>
02 using namespace std;
03 int f(int a, int n, int m)
04 {
05    if(a==1) return 1%m;①
06    long long ans = 1%m;
07    while(n){
08        if(n&1)
09           ans = (ans * a) % m;②
10        a = (a * a) % m;
11        n >>= 1;
12    }
13    return ans;
14 }
15 int main (  )
16 {
17    int a,n,m;
18    cin >> a>>n>>m;
19    cout << f(a, n,m);
20 }

判断题

22.程序的时间复杂度是0(logn) ( ) {{ select(22) }}

  • 正确
  • 错误

23.删除①处语句,程序输出不受影响 ( )

{{ select(23) }}

  • 正确
  • 错误

24.如果输入为1 999 2048,②处语句会执行8次 ( )

{{ select(24) }}

  • 正确
  • 错误

25.如果输入1 0 1,输出结果为1 ( )

{{ select(25) }}

  • 正确
  • 错误

单选题

26.(2分)输入2 13 2048输出为( )

{{ select(26) }}

  • 0
  • 1
  • 2047
  • 2000

27.输入7 11 10,输出为 ( )

{{ select(27) }}

  • 5
  • 3
  • 7
  • 1

(3)(共15分)

01 #include<iostream>
02 #include<cstring>
03 using namespace std;
04 char s[10000];
05 int cnt[200];
06 int main (  ){
07     scanf("%s",s);
08     for(int i=0;i<strlen(s);i++){
09         if(s[i]>=48&&s[i]<=57&&cnt[s[i]-48]<=10){
10             s[strlen(s)]=s[i];
11         }
12         cnt[s[i]-48]++;
13     }
14     printf("%s\n",s);
15     return 0;
16 }

假设输入的字符串长度不超过50且只包含数字和小写字母,完成下面的判断题和单选题:

判断题

28.因为输入字符串长度不超过50,故第4行的10000改成100,程序运行结果不变。 ( ) {{ select(28) }}

  • 正确
  • 错误

29.将第8行改成for(int i=0,len=strlen(s);i<len;i++){程序运行结果不变且运行速度提高。 ( ) {{ select(29) }}

  • 正确
  • 错误

30.对于任意一个只包含数字字符且每个数字字符出现的次数不小于10的字符串B,总存在一个字符串A使得输入A后输出结果为B。 ( ) {{ select(30) }}

  • 正确
  • 错误

单选题

31.如果输入的字符串只包含数字字符,则输出的字符串长度可能是 ( )。 {{ select(31) }}

  • 10
  • 11
  • 160
  • 200

32.设输入的字符串长度为x,输出的字符串长度为y,则以下关系正确的是 ( )。

{{ select(32) }}

  • x=y
  • x<y
  • x<y 或者x=y
  • x<y 或者 x=y 或者x>y

33.设字符串A为12,如果输入字符串为AA,(A重复2次),则输出为 ( )。

{{ select(33) }}

  • A重复10次
  • A重复11次
  • A重复12次
  • A重复13次

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

(1)(消灭怪兽) 有n个怪兽,每个怪兽血量为hpihp_i。每次可以任意选择一个还存活的怪兽进行攻击,被选择的怪兽受到A点伤害,其他还存活的怪兽也同样会受到B点溅射伤害。当一个怪兽的血量降到0或以下时就会消失。求最少需要进行多少次攻击可以消灭所有怪兽。

数据范围满足 1n105,1B<A109,1hpi1091≤n≤10^5,1≤B<A≤ 10^9,1≤ hp_i≤10^9

提示:可以采用二分答案的方法来求解。 试补全程序。

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N=1e5+5;
04 typedef long long ll;
05 ll hp[N];
06 int n;
07 ll a,b;
08 bool check(11 x){
09   ll cnt=x;
10   for(int i=1;i<=n;i++){
11   ll res_hp=___①___;
12   if(res_hp>0){
13       ll cnta=___②__;
14       if(__③__) cnta++;
15       cnt-=cnta;
16       if(cnt<0) break;
17    }
18  }
19    return ___④_;
20 }
21 int main (  ){
22   cin>>n>>a>>b;
23   for(int i=1;i<=n;i++) cin>>hp[i];
24   ll l=1,r=1e9;
25   while(l<=r){
26       ll mid=1+r>>1;
27       if(check(mid)) r=mid-1;
28       else l=mid+1;
29   }
30   cout<<____⑤___<<endl;
31   return 0;
32 }

34.①处应填 ( )。 {{ select(34) }}

  • hp[i]-a
  • hp[i]-b
  • hp[i]-x*a
  • hp[i]-x*b

35.②处应填 ( )。 {{ select(35) }}

  • hp[i]/(a-b)
  • res_hp/(a-b)
  • res_hp/a
  • hp[i]/b
  1. ③处应填 ( )。 {{ select(36) }}
  • res_hp%a==0
  • res_hp%b
  • res_hp%(a-b)
  • res_hp%(a-b)==0

37.④处应填 ( )。 {{ select(37) }}

  • cnt>=x
  • cnt>=0
  • cnt<=x
  • cnt<=0

38.⑤处应填 ( )。 {{ select(38) }}

  • l-1
  • l
  • r-1
  • r

(2)(位运算操作)现有编号为1到n的n位同学和n个操作,每位同学都会进行一些操作,操作流程如下面描述。

最开始老师手里有一个整数x,交给1号同学,1号同学执行完第1个操作交给2号同学;2号同学执行完第1,2个操作交给3号同学;…;第i号同学从第i-1号同学接过数后,依次执行前i个操作,将最后的数交给第i+1号同学;依此下去直到第n号同学完成所有操作。

为了方便表示,我们用二元组来描述操作,其中第i个操作作用二元组(op,a[i])表示:op取值为1,2,3分别表示将当前数字与a[i]进行AND,OR,XOR操作(即按位与,按位或,按位异或)。

求每个同学执行完自己的轮次后,手里的数是多少。

先输入n和初始的整数x,接下来n行每行两个数表示描述操作的二元组。

数据范围满足1n2105,0a[i],x1091≤n≤ 2*10^5,0 ≤ a[i],x ≤ 10^9

提示:如果进行模拟时间复杂度为O(n2)O(n^2)会超时,因此采用位运算,提前通过递推求出x的每一个数位经过前i次操作后的值,设f[i][i][k] 表示初始状态是j,经过k次操作第i位的值。实际模拟时直接读取该值即可。

试补全程序。

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N=2e5+5;
04 int op[N],a[N];
05 int f[35][2][N];
06 int n,x;
07 int main (  ) {
08   cin>>n>>x;
09   for(int i=1;i<=n;i++) cin>>op[i]>>a[i];
10   for(int i=0;i<30;i++){
11     ___①_;
12   }
13   for(int i=0; i<30;i++){
14       for(int j=0;j<2;j++){
15           for(int k=1; k<=n;k++){
16               int bit=___②___;
17               if(op[k]==1) f[i][j][k]=f[i][j][k-1] & bit;
18               if(op[k]==2) f[i][j][k]=f[i][j][k-1] | bit;
19               if(op[k]==3) f[i][j][k]=__③___;
20            }
21       }
22   }
23   for(int i = 1; i <= n; ++i) {
24       int t=0;
25       for(int j=0;j<30;j++) {
26           int bit=(x>>j)&1;
27           if(___④__) t+=(___⑤_);
28        }
29       cout<<t<<end1;
30       x=t;
31    }
32    return 0;
33 }

39.①处应填 ( )。 {{ select(39) }}

  • f[0][0][i]=0,f[0][1][i]=1;
  • f[i][0][0]=0,f[i][1][0]=1
  • f[i][0][0]=1,f[i][1][0]=0;
  • f[0][1][0]=1,f[0][1][0]=0
  1. ②处应填 ( )。 {{ select(40) }}
  • a[k]>>i&1
  • a[k]>>i|1
  • (a[k]>>i)|1
  • (a[k]>>i)&1

41.③处应填 ( )。 {{ select(41) }}

  • f[i][j][k-1] ^ bit
  • f[i][j][k-1] + bit
  • f[i][j][k-1] & bit
  • f[i][j][k-1] | bit
  1. ④处应填 ( )。 {{ select(42) }}
  • f[i][bit][j]
  • !f[i][bit][j]
  • f[j][bit][i]
  • !f[j][bit][i]
  1. ⑤处应填 ( )。 {{ select(43) }}
  • t+=(f[i][bit][j]<<j)
  • t+=(f[j][bit][i]<<j)
  • t=(f[i][bit][j]<<(j-1))
  • t=(f[j][bit][i]<<(j-1))