#C1211. 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)
-
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 分)
规定输入的 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
输入的 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
输入:第一行一个正整数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 个数 之和为奇数,输出的结果一定为 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 的上限和 的上限一致,均记为 N,则该程序对应算法的 最坏时间复杂度为( )。
{{ select(33) }}
- O(N)
- O(NlogN)
三、完善程序(单选题,每小题 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)