D. 2024CSPJ初赛模拟题(二)

    客观题

2024CSPJ初赛模拟题(二)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单项选择(共 15 题,每题 2 分,共计 30 分)

1.以下不属于高级程序设计语言的是?( )

{{ select(1) }}

  • C++
  • C 语言
  • Python
  • 汇编语言

2.一个容量为 32GB 的 U 盘能存储大约( )张大小为 500KB 的数码照片。

{{ select(2) }}

  • 16000
  • 32000
  • 64000
  • 128000

3.十进制数 7.75 与二进制数( )值相等。

{{ select(3) }}

  • 101.11
  • 111.11
  • 111.101
  • 111.01

4.快速排序的最坏时间复杂度为( )。

{{ select(4) }}

  • O(n)
  • O(1)
  • Onlog2n​O(nlog_2 n)
  • O(n2)O​(n^2 )

5.现有一张 1024*768 像素的 32 位真彩色图片,问占用的存储空间大约为()

{{ select(5) }}

  • 3MB
  • 750KB
  • 24MB
  • 12MB

6.有 5 个点的简单无向图(无重边与自环)至多有多少条边()

{{ select(6) }}

  • 6
  • 8
  • 10
  • 12

7、 如果一棵二叉树只有根结点,那么这棵二叉树高度为 1。请问高度为 5 的完全 二叉树至少有多少个结点 ( )

{{ select(7) }}

  • 15
  • 16
  • 31
  • 32

8.表达式 a+(b+c)*d 的后缀表达式是( )。

{{ select(8) }}

  • abcd*++
  • abc+d*+
  • abc*+d+
  • +*abcd+

9.有一个 6 级台阶的楼梯,可以一次上一级或者两级台阶,问所有可能的方案数为 ( ) {{ select(9) }}

  • 5
  • 8
  • 10
  • 13

10、 用一个 1,两个 2,三个 3 组成一个六位数,问有多少个不同的数值 ( )

{{ select(10) }}

  • 720
  • 360
  • 120
  • 60

11.有一个二叉树,每个结点由不同的大写字母标记,已知前序遍历为 ABCDEFG, 中序遍历为 CBDEAGF,问后序遍历( )。

{{ select(11) }}

  • CEDBAFG
  • CDBEAFG
  • CEDBGFA
  • CDEBGFA

12、给出一个 3 位数 x(100<=x<=999)下面哪个逻辑表达式可以用来判断 x 是否是回文数( )。

{{ select(12) }}

  • x==999-x
  • x%10==x/100
  • x/10==x%100
  • x%10+x/100==9

13、 考虑如下递归算法,问调用 solve(9)的返回值 ( )

solve(n)
    if n==1 return 1
    else if n%2==0 return solve(n/2)+1
    else return solve(3*n+1)+1

{{ select(13) }}

  • 10
  • 15
  • 20
  • 25

14.初一年级共有 5 个班(每个班有 50 人),需要选出8 个同学参加合唱团,每 个班至少有一位同学入选,问班级名额分配共有多少种不同的方案 ( )

{{ select(14) }}

  • 25
  • 30
  • 35
  • 40

15.校乒乓球队有 4 名男运动员和 4 名女运动员,现在要安排混双分组,为了增 加比赛悬念,上届比赛冠军张三(男)和李四(女)不能分在一组,问有多少种 可行的分组方案。( )

{{ select(15) }}

  • 12
  • 18
  • 20
  • 24

二、阅读程序(除特殊说明外,判断题 1.5 分,选择题 4 分,共计 40 分)

image

规定输入的 a 为不超过 1000000 的正整数。

16、 若将第 6 行的 “i*i ” 改为 “i”.程序结果会发生变化。 ( )

{{ select(16) }}

  • 正确
  • 错误

17、若将第 8 行的 “++cnt,a/=i; ”改为 “++cnt;a/=i; ” 程序可以正常运行, 输出答案。 ( )

{{ select(17) }}

  • 正确
  • 错误

18、 若去掉第 11 行,对于任何输入 a,输出结果都和初始程序不同。 ( )

{{ select(18) }}

  • 正确
  • 错误

19、如果输入 1024,输出 11。 ( )

{{ select(19) }}

  • 正确
  • 错误

20、(3 分)若输入的 a 为 240, 则输出( )。

{{ select(20) }}

  • 16
  • 20
  • 24
  • 32

21、(3 分)若输出为 8,那么最小的可能的输入值 a 为( )。

{{ select(21) }}

  • 128
  • 30
  • 24
  • 12

image

输入的 n 为不超过 100000 的正整数,接下来 n 个数为 int 范围内的正整数。

22、 输出可能为 0。 ( )

{{ select(22) }}

  • 正确
  • 错误

23、若第 8 行改为 “int ans=0; ”,对任意满足要求的输入,答案保持不变。 ()

{{ select(23) }}

  • 正确
  • 错误

24、 若第 12 行改为 “int mid=1+r>>1; ”对任意满足要求的输入,答案保持不变。 ( )

{{ select(24) }}

  • 正确
  • 错误

25、程序运行到 31 行时,有 a[1]<=a[2]<=...<=a[n]。 ( )

{{ select(25) }}

  • 正确
  • 错误

26、若输入 5 4 3 1 3 2,则输出 ( )。

{{ select(26) }}

  • 5
  • 6
  • 7
  • 12

27、若输入的 n 为 16,则 Merge 函数被调用了 ( )次。

{{ select(27) }}

  • 64
  • 15
  • 31
  • 32

image

输入:第一行一个正整数n, 接下来输入 n 个正整数 a_ 1,a_2,..., a_n,用空格隔开。 (1<=n<=100000, 1<=a_ 1+a_2+...+a_n<=100000)

28、 若输入 2 3 4, 输出 No。 ( )

{{ select(28) }}

  • 正确
  • 错误

29、若输入的 n 为奇数,输出的结果一定为 No。 ( )

{{ select(29) }}

  • 正确
  • 错误

30、若输入的 n 个数 a1,a2,...,ana_ 1,a_2,..., a_n 之和为奇数,输出的结果一定为 No。 ( )

{{ select(30) }}

  • 正确
  • 错误

31、若将第 17 行的“j<<=1”,改为“j+=1”,不会改变输出结果。 ( )

{{ select(31) }}

  • 正确
  • 错误

32、 下列哪一组输入会输出 No ( )。

{{ select(32) }}

  • 5 1 2 3 7 9
  • 6 3 5 7 1 1 1
  • 6 1 1 2 3 4 5
  • 6 3 3 3 5 5 5

33、若 n 的上限和 a1+a2+...+ana_ 1+a_2+...+a_n 的上限一致,均记为 N,则该程序对应算法的 最坏时间复杂度为( )。

{{ select(33) }}

  • ​O​(​N)
  • ​O​(Nlog​N)
  • O(NN)O(N \sqrt{N})
  • O(N2)O(N^2)

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

1、 (转化进制) 众所周知,Yummy 是十分粗心的。给他一个十进制数,让他把 其化为 2 进制或 3 进制,他总是会把其中一位算错。举个例子:要他把 14 化为 2 进制,正确答案为 1110,但他会化成 0110 或 1111 等。(注意, Yummy 每次都 只会算错一位)

现在 Yummy 将一个正整数 num 化作 2 进制与 3 进制。告诉你他得出的2 进制 数与 3 进制数,你能知道 num 是多少么?

(num≤1e9。输入数据保证有唯一解。)

输入两个数字串,分别表示 Yummy 转化的二进制和三进制的数。

1.  #include<bits/stdc++.h>
2.	using namespace std;
3.	#define int long long
4.	char s[100],t[100],tp[100];
5.	int n,m;
6.	int calc(){
7.	    int res=0;
8.		  for(int i=1;i<=n;i++)res=①+s[i]- '0';  
9.	        return res;
10.	}
11.	bool chk(int x){
12.	    int top=0;
13.	    while(x){
14.	        ②=(x%3)+ '0';
15.	        x/=3;
16.	    }
17.	    if(top>m)③;
18.	    while(top<m) tp[++top]='0';
19.	    int cnt=0;
20.	    for(int i=1;i<=m;i++)cnt+=(t[i]!=tp[top-i+1]);
21.	    return (④);
22. }
23.	int main(){
24.	    scanf("%s%s",s+1,t+1);
25.	    n=strlen(s+1);m=strlen(t+1);
26.	    for(int i=1;i<=n;i++){
27.	        s[i]=⑤;
28.	        int tmp=calc();
29.	        if(chk(tmp)){
30.	            cout<<tmp<<endl;
31.	            return 0;
32.	        }
33.	        s[i]= '1'-s[i]+'0';
34.	    }
35.	    return 0;
36.	}

34、 ①处应填( )。

{{ select(34) }}

  • res
  • res*2
  • res*3
  • res*10

35、 ②处应填( )。

{{ select(35) }}

  • tp[--top]
  • tp[top]
  • tp[++top]
  • tp[top++]

36、 ③处应填( )。

{{ select(36) }}

  • return true
  • return false
  • top--
  • top=m

37、 ④处应填( )。

{{ select(37) }}

  • cnt==1
  • cnt>1
  • cnt<1
  • !cnt

38、 ⑤处应填( )。

{{ select(38) }}

  • 1+s[i]+0
  • 1-s[i]+0
  • '0'+s[i]+'1'
  • '1'-s[i]+'0'

2.给定一个 8x8 的国际象棋棋盘,棋盘上有一个骑士,骑士单步可以走一个日字形。

严谨地说 ,假如骑 士 当前 坐标为 (x,y), 走 一步可 以 到达 的坐标是 (x-1,y-2) (x+1,y-2)(x-1,y+2)(x+1,y+2)(x-2,y-1)(x-2,y+1)(x+2,y-1)(x+2,y+1), 当然,骑士 不能走到棋盘外。

棋盘上还有可能有一个皇后,皇后单步可以走横向,纵向,两个斜对角共 4 种方向,可以走任意多格。

给出骑士的起点和终点坐标,如果有皇后,给出皇后坐标。要求骑士使用尽可能少的步 数从起点走到终点。皇后始终保持不动,但是只要在任何时刻,骑士在皇后的攻击范围 内(​包括起点和终点*),皇后就会立刻吃掉骑士。所以骑士要么避开皇后的攻击范围, 要么先走到皇后的坐标位置吃掉皇后,之后方可畅通无阻。

问骑士至少要花多少步才能从起点安全走到终点。

【输入格式】

第一行输入两个整数 sx,sy,表示骑士初始坐标,用空格隔开。 第二行输入两个整数 ex,ey,表示骑士终止坐标,用空格隔开。

第三行输入两个整数 qx,qy,表示皇后坐标,用空格隔开,若为(0,0),表示不存 在皇后。

【输出格式】

输出一个整数,即骑士走的步数的最小值。若骑士无法安全抵达终点,输出-1。

1.   #include <bits/stdc++.h>
2.   using namespace std;
3.   int sx,sy,ex,ey,qx,qy;
4.   struct node{
5.         int x,y,flag,step;
6.    };
7.   queue<node>q;
8.   bool vis[10][10][2];
9.   int dx[8]={-2,-2,-1,-1,1,1,2,2};
10.  int dy[8]={-1,1,-2,2,2,-2,1,-1};
11.
12.  bool inside(int x,int y){
13.      if(①)return true;
14.      return false;
15.  }
16.
17.  bool attacked(int x,int y){
18.         if(x==qx||y==qy)return true;
19.         if(②)return true;
20.         return false;
21.  }
22.
23.  int main(){
24.         cin>>sx>>sy>>ex>>ey>>qx>>qy;
25.         if(qx==0&&qy==0){
26.                q.push((node){sx,sy,0,0});
27.         }else {
28.                 if(attacked(sx,sy)){
29.                        cout<<-1<<endl;
30.                        return 0;
31.                }else{
32.                        q.push((node){sx,sy,1,0});
33.                }
34.         }
35.         while(③){
36.                 node=q.front();
37.                 q.pop();
38.                 if(tmp.x==ex&&tmp.y==ey){
39.                        cout<<tmp.step<<endl;
40.                        return 0;
41.                }
42.                for(int i=0;i<8;i++){
43.                        int x=tmp.x+dx[i];
44.                        int y=tmp.y+dy[i];
45.                        int flag=tmp.flag;
46.                        int step=tmp.step+1;
47.                        if(!inside(x,y))④;
48.                        if(x==qx&&y==qy){
49.                               flag=0;
50.                        }
51.                        if(⑤)continue;
52.                        if(vis[x][y][flag])continue;
53.                        vis[x][y][flag]=true;
54.                        q.push((node){x,y,flag,step});
55.                }
56.
57.         }
58.         cout<<-1<<endl;
59. }

39、 ①处应填( )。

{{ select(39) }}

  • (x>=1&&x<=8) || (y>=1&&y<=8)
  • (x>=1||x<=8)&&(y>=1||y<=8)
  • x>=1&&x<=8&&y>=1&&y<=8
  • x>=1||x<=8||y>=1||y<=8

40、 ②处应填( )。

{{ select(40) }}

  • x+y==qx||x-y==qx
  • x+y==qx+qy||x-y==qx-qy
  • x+qx==y+qy||x-qx==y-qy
  • x+y==qx+qy&&x-y==qx-qy

41、 ③处应填( )。

{{ select(41) }}

  • !q.empty()
  • q.empty()
  • true
  • q.front().x!=ex&&q.front().y!=ey

42、④处应填( )。

{{ select(42) }}

  • break
  • continue
  • return 0
  • cout<<tmp.step

43、 ⑤处应填( )。

{{ select(43) }}

  • flag
  • attacked(x,y)
  • flag&&attacked(x,y)
  • flag||attacked(x,y)

2024.08.16 入门组周赛

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-8-16 19:45
结束于
2024-8-20 23:45
持续时间
100 小时
主持人
参赛人数
5