2024CSPJ初赛模拟题(一)
一、单项选择（共 15 题，每题 2 分，共计 30 分）
1.提出“存储程序 ”的计算机原理的是( )。
{{ select(1) }}
- 克劳德 ·香农
- 戈登 ·摩尔
- 查尔斯 · 巴比奇
- 冯 ·诺依曼
2 在计算机内部，用来传送、存储、加工处理的数据或指令（命令）都是以( ) 形式进行的。
{{ select(2) }}
- 十进制码
- 二进制码
- 智能拼音码
- 五笔字型码
3.8GB 的 U 盘大约能存储多少张 500KB 的照片( )。
{{ select(3) }}
- 8000
- 16000
- 32000
- 64000
4.一个自然数在十进制下有 n 位，则它在二进制下的位数与( )最接近。 {{ select(4) }}
- 5n
5.在字长为16 位的系统环境下， 一个16 位带符号整数的二进制补码为 1111111111101101。其对应的十进制整数应该是( )。
{{ select(5) }}
- 19
- -19
- 18
- -18
6.深度优先搜索时，需要用到的数据结构是( )
{{ select(6) }}
- 链表
- 栈
- 队列
- 散列表
7.若树的根结点深度为 0 ，求有 n 深度的完全二叉树至少有几个结点( )
{{ select(7) }}
8.某树的前序遍历为 ABDHECFGJKI, 中序遍历为 HDBEAFJGKCI,求此树的后序遍历( )
{{ select(8) }}
- IKJGFCEHDBA
- HDEBJKGFICA
- ABCDEFGHIJK
- ICKGJFAEBDH
9.基于比较的排序时间复杂度的下限是( ),其中 n 表示待排序的元素个数。
{{ select(9) }}
- O(n)
- O(nlogn)
- O(logn)
10.用 0，1，2，2，3 能组成多少个不同的五位数( )。
{{ select(10) }}
- 120
- 60
- 48
- 32
11.元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第一个出栈的是 R3,那么第五个出栈的不可能是( )。
{{ select(11) }}
- R1
- R2
- R4
- R5
12.前缀表达式“+3*2+5 12”的值是( )。
{{ select(12) }}
- 23
- 25
- 37
- 65
13.双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱和后继。 设 p 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 p,则下面
语句 序列中错误的是( )。
{{ select(13) }}
- p->rlink->llink=p->rlink;p->llink->rlink=p->llink;delete(p)
- p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete(p)
- p->rlink->llink=p->llink;p->rlink->llink->rlink=p->rlink;delete(p)
- p->llink->rlink=p->rlink;p->llink->rlink->llink=p->llink;delete(p)
14.5 个人排成一排，其中有两个人关系特别好，一定要排在相邻的位置，问一共 有多少种排法( )
{{ select(14) }}
- 120
- 64
- 48
- 24
15.给一个五边形（非正五边形，且五条边长度两两不同）的 5 条边染色，要求 只能使用红、绿、蓝三种颜色，且相邻的边不能同色，问一共有多少种染色方法 ( )
{{ select(15) }}
- 24
- 28
- 30
- 32
二、阅读程序（除特殊说明外，判断题 1.5 分，选择题 4 分，共计 40 分）
01 #include <iostream>
02 using namespace std;
03
04 int rSum(int j)
05 {
06 int sum=0;
07 while(j!=0)
08 {
09 sum=sum*10+(j%10);
10 j=j/10;
11 }
12 return sum;
13 }
14
15 int main()
16 {
17 int n,m,i;
18 cin>>n>>m;
19 for(i=n;i<m;i++)
20 if(i==rSum(i))
21 cout<<i<<' ';
22 return 0;
23 }
16)rSum(i)>=i。 ( )
{{ select(16) }}
- 正确
- 错误
17)若 n 和 m 都很大时，程序一定有输出结果。 ( )
{{ select(17) }}
- 正确
- 错误
18)将第 7 行的“j!=0”,改为“j>=0”时，程序会出错。 ( )
{{ select(18) }}
- 正确
- 错误
19)若输入的 n 等于 m,程序一定没有输出。 ( )
{{ select(19) }}
- 正确
- 错误
20)若要想程序输出的最后一个数字是 99， 则输入的 m 有( )种方案。
{{ select(20) }}
- 2
- 3
- 11
- 12
21)若输入的 n 和 m 分别为 1000 和 2000， 则程序会输出 ( )个数字。
{{ select(21) }}
- 20
- 9
- 10
- 11
01 #include <bits/stdc++.h>
02 #define maxn 50
03 using namespace std;
04
05 const int y = 2009;
06
07 int main()
08 {
09 int n,i,j,s;
10 int c[maxn][maxn];
11 s=0;
12 scanf("%d",&n);
13 c[0][0]=1;
14 for(i=1;i<=n;i++){
15 c[i][0]=1;
16 for(j=1;j<=i;j++)
17 c[i][j] = (c[i-1][j-1]+c[i-1][j])%y;
18 c[i][i]=1;
19 }
20 for(i=0;i<=n;i++)
21 s=(s+c[n][i])%y;
22 printf("%d\n",s);
23 return 0;
24 }
- 若输入的 n 足够大时，对于任意 i,j,有 c[i][j]>=c[i][j-1]。 ()
{{ select(22) }}
- 正确
- 错误
23)将第 16 行的“j=1”改为“j=0” ，程序会出错。( )
{{ select(23) }}
- 正确
- 错误
24)对于 c[i][j],j 固定时，当 i 越大时,c[i][j]就越大。 ( )
{{ select(24) }}
- 正确
- 错误
25)若给出 x(3<x<=10),则任意的 c[x][i](1<=i<=x-1)和 x 的最大公因数一定大于 1。 ( )
{{ select(25) }}
- 正确
- 错误
26)若输入 10，在程序运行到 19 行时，二维数组c 内部储存的最大数值为 ( )。
{{ select(26) }}
- 120
- 188
- 252
- 320
- 若输入 11,则输出的值为( )
{{ select(27) }}
- 1
- 11
- 24
- 39
01 #include <bits/stdc++.h>
02 using namespace std;
03 char s[100];
04 bool vis[100];
05 char tmp[100];
06 int n;
07
08 void dfs(int step){
09 if(step==n){
10 cout<<tmp<<endl;
11 return;
12 }
13 for(int i=0;i<n;i++){
14 if(!vis[i]){
15 vis[i]=true;
16 tmp[step] = s[i];
17 dfs(step+1);
18 vis[i]=false;
19 }
20 }
21 }
22
23 int main(){
24 cin>>s;
25 n=strlen(s);
26 dfs(0);
27 return 0;
28 }
28)若将第 9 行的 if(step==n)改为 if(step>=n),不影响输出结果。 ( )
{{ select(28) }}
- 正确
- 错误
29)输入的字符串只会在输出的第一行出现一次。 ( )
{{ select(29) }}
- 正确
- 错误
30)若删除第 18 行，则输出一行字符串，和输入字符串保持一致。 ( )
{{ select(30) }}
- 正确
- 错误
31)若输入的字符串由同一个小写字母组成，例如 aaa,输出的每一行都相同。（ ）
{{ select(31) }}
- 正确
- 错误
选择题
32)(3 分)若输入 abc，则输出的第 4 行为 ( )。
{{ select(32) }}
- cab
- bca
- cba
- abc
33)(3 分)若输出的第 2 行为 abcde，则输出的第 5 行为( )。
{{ select(33) }}
- abedc
- abecd
- abdce
- abdec
三、完善程序（单选题，每小题 3 分，共计 30 分）()
(哥德巴赫猜想)哥德巴赫猜想是指，任一大于 2 的偶数都可写成两个质数 之 和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。 试编 写程序，验证任一大于 2 且不超过 n 的偶数都能写成两个质数之和。
01 #include <iostream>
02 using namespace std;
03
04 int main()
05 {
06 const int SIZE = 1000;
07
08 int n, r, p[SIZE], i, j, k, ans;
09 bool tmp;
10
11 cin>>n;
12 r = 1;
13 p[1] = 2;
14 for (i = 3; i <= n; i++) {
15 [ ① ];
16 for (j = 1; j <= r; j++)
17 if (i % [ ② ] == 0) {
18 tmp = false;
19 break;
20 }
21 if (tmp) {
22 r++;
23 [ ③ ] ;
24 }
25 }
26
27 ans = 0;
28 for (i = 2; i <= n / 2; i++) {
29 tmp = false;
30 for (j = 1; j <= r; j++)
31 for (k = j; k <= r; k++)
32 if (i + i == [ ④ ] ) {
33 tmp = true;
34 break;
35 }
36 if (tmp)
37 ans++;
38 }
39 cout<<ans<<endl;
40 return 0;
41 }
若输入 n 为 2010，则输出 ⑤ 时表示验证成功，即大于 2 且不超过 2010 的 偶数 都满足哥德巴赫猜想。
34)①处应填（ ）。
{{ select(34) }}
- tmp=true
- tmp=false
- tmp++
- r=sqrt(n)
35)②处应填（ ）。
{{ select(35) }}
- j
- p[j]
- p[j+1]
- p[i]
36)③处应填（ ）。
{{ select(36) }}
- p[r]=i
- p[r-1]=i
- p[r]=j
- p[r-1]=j
37)④处应填（ ）。
{{ select(37) }}
- p[k]
- p[i]+p[k]
- p[i]+p[i]
- p[j]+p[k]
- ⑤处应填（ ）。
{{ select(38) }}
- 1003
- 1004
- 1005
- 1006
(寻找等差数列)有一些长度相等的等差数列(数列中每个数都为 0 ~59 的 整数),设长度均为 L,将等差数列中所有数打乱顺序放在一起。现在给你这些打乱 后的数，问原先 L 的最大可能取值。先读入一个数 n(1<=n<=60),再读入 n 个 数， 代表打乱后的数，输出等差数列最大可能长度 L。
01 #include <iostream>
02 using namespace std;
03 int hash[60];
04 int n, x, ans, maxnum;
05 int work(int now) {
06 int first, second, delta, i;
07 int ok;
08 while ( ① && !hash[now])
09 ++now;
10 if (now > maxnum)
11 return 1;
12 first = now;
13 for (second = first; second <= maxnum; second++)
14 if (hash[second]) {
15 delta = ② ;
16 if (first + delta * ③ > maxnum)
17 break;
18 if (delta == 0)
19 ok = ( ④ );
20 else{
21 ok = 1;
22 for (i = 0; i < ans; i++)
23 ok = ⑤ && (hash[first+delta*i]);
24 }
25 if (ok){
26 for (i = 0; i < ans; i++)
27 hash[first+delta*i]--;
28 if (work(first))
29 return 1;
30 for (i = 0; i < ans; i++)
31 hash[first+delta*i]++; 32 }
33 }
34 return 0;
35 }
36 int main(){
37 int i;
38 memset(hash, 0, sizeof(hash));
39 cin >> n;
40 maxnum = 0;
41 for (i = 0; i < n; i++){
42 cin >> x;
43 hash[x]++;
44 if (x > maxnum)
45 maxnum = x;
46 }
47 for (ans = n; ans >= 1; ans--)
48 if ( n%ans==0 && work(0) ) {
49 cout << ans << endl;
50 break;
51 }
52 return 0;
53 }
- ①处应填（ ）。
{{ select(39) }}
- now
- now<=maxnum
- now<=n
- hash[now]==0
40)②处应填（ ）。
{{ select(40) }}
- maxnum-first
- second-first
- maxnum-second
- hash[second]-hash[first]
- ③处应填（ ）。
{{ select(41) }}
- ans
- (ans-1)
- now
- (now-1)
- ④处应填（ ）。
{{ select(42) }}
- hash[second]>=ans
- ok
- first+delta*(ans-1)
- hash[first]==ans
- ⑤处应填（ ）。
{{ select(43) }}
- ok
- hash[first]
- (hash[second+delta*i])
- hash[second]
相关
在下列比赛中: