2024CSPJ初赛模拟题(四)
一 、单项选择（共 15 题， 每题 2 分，共计 30 分）
1、冯·诺伊曼结构计算机不包含( )
{{ select(1) }}
- 运算器
- 存储器
- 通讯器
- 控制器
2、下列不同的进制数中 ,与其它三项不同的是( )
{{ select(2) }}
3、已知两个整数的 8 位带符号二进制补码分别为 10101011 和 01001100，问这两个数的和的十 进制表示为( )
{{ select(3) }}
- 247
- -247
- 9
- -9
4、以下哪一个表达式的后缀形式是 abcd+*+ ( )。
{{ select(4) }}
- (a+b)*(c+d)
- a+b*(c+d)
- (a+b)*c+d
- a+b*c+d
5、若逻辑表达式 A、 B 为真，C、D 为假， 以下哪一项逻辑表达式的值为真（ ）。
{{ select(5) }}
- ( →A Λ B）V（C Λ D）
- (A Λ B Λ C) V (B Λ C Λ →D）
- (A V B) Λ (B V C) Λ (C V D)
- (A V →B V C) Λ (→ B V C V →D)
6、以下排序算法中， 平均时间复杂度最高的是（ ）。
{{ select(6) }}
- 快速排序
- 归并排序
- 堆排序
- 选择排序
7、在 C++中，长度为 1000000 的 int 数组所需的空间约为（ ）
{{ select(7) }}
- 1MB
- 4MB
- 32MB
- 64MB
8、已知大写字母 A 的 ASCII 编码为 65（10 进制） ,问大写字母 K 的 ASCII 码为 ( )
{{ select(8) }}
- 74
- 75
- 76
- 以上都不是
9、对于入栈顺序为 a,b,c,d 的序列 ,合法的出栈序列有( )种 {{ select(9) }}
- 10
- 12
- 14
- 16
10、根节点深度为 0,一棵深度为 h 的 k (k>1) 叉树 ,且每个节点要么没有儿子 ,要么有 k 个 儿子 , 则这棵树的最少节点数是 ( )
{{ select(10) }}
- k*h+1
- k*(h-1)+1
11、一个 6 个顶点的完全图至少删掉多少条边才能变为森林？ ( )
{{ select(11) }}
- 8
- 10
- 11
- 14
12、考虑如下递归算法，问调用 solve(87)的返回值 ( )
int solve(int x)
if x==0 return 0;
else return solve(x-(x&-x))+1;
{{ select(12) }}
- 4
- 5
- 6
- 7
13、有 8 个相同的球 ,放进 3 个不同的袋子里， 可以有空袋子， 问有多少种不同的放法 ( )
{{ select(13) }}
- 21
- 45
- 336
- 512
14、前序遍历和中序遍历相同的二叉树为且仅为( )
{{ select(14) }}
- 根结点没有右子树的二叉树
- 根结点没有左子树的二叉树
- 只有 1 个点的二叉树或非叶子结点只有左子树的二叉树
- 只有 1 个点的二叉树或非叶子结点只有右子树的二叉树
15、有甲乙丙丁戊己 6 个人按照某种顺序从左到右排成一排，其中甲乙要相邻，丙丁不得相邻， 问有多少种不同的方案 ( )
{{ select(15) }}
- 96
- 120
- 144
- 192
二、 阅读程序（除特殊说明外，判断题 1.5 分，选择题 4 分，共计 40 分）
1、
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn = 5000007; 04
05 int prime[maxn], tot = 0;
06 int sum[maxn];
07 bool vis[maxn];
08
09 void sieve() {
10 for(int i = 2; i < maxn; i++) {
11 if(!vis[i]) {
12 prime[++tot] = i;
13 sum[i] = 1;
14 }
15 for(int j = 1; j<=tot && prime[j] * i < maxn; j++){
16 vis[prime[j] * i]= true ;
17 sum[prime[j] * i] = sum[i] + 1;
18 if (i % prime[j] == 0)break;
19 }
20 }
21 for (int i = 1; i < maxn; i++) sum[i] += sum[i - 1];
22 }
23
24 int main() 25 {
26 sieve();
27 int T;
28 scanf("%d",&T);
29 while(T--){
30 int a, b;
31 scanf("%d%d",&a,&b);
32 printf("%d\\n",sum[a]-sum[b]);
33 }
34 return 0;
35 }
输入第一行为数据组数 T，接下来 T 行每行输入 a 和 b，1<=b<=a<=5000000
16、第 10 行， i=2 改成 i=1,程序结果不变( )
{{ select(16) }}
- 正确
- 错误
17、第 15 行 ,删去 j<=tot&& ,程序结果不变( )
{{ select(17) }}
- 正确
- 错误
18、删去第 18 行 ,程序结果不变 ,运行速度可能变慢( )
{{ select(18) }}
- 正确
- 错误
19、程序的输出结果不可能为 0( )
{{ select(19) }}
- 正确
- 错误
20、该算法的时间复杂度为( ) (3 分)
{{ select(20) }}
- O(n)
- O(logn)
- O(nlogn)
- O(n2)
21、输入 1 10 1,输出结果为( ) (3 分)
{{ select(21) }}
- 13
- 14
- 15
- 16
2、
01 #include <iostream>
02 using namespace std;
03 string s, t;
04 char c;
05 int a;
06 int main()
07 {
08 cin >> s;
09 for (int i = 0; i < s.size(); i++) 10 {
11 if ('A' <= s[i] && s[i] <= 'Z')
12 a = (s[i] - 'A' + 25) % 26;
13 else a = (s[i] - 'a' + 1) % 26;
14 if (i & 2) c = a + 'a';
15 else c = a + 'A';
16 t = t + c;
17 }
18 cout << t << endl;
19 return 0;
20 }
保证输入的字符串只包括大小写字母 22、删掉第 11 行的 'A' <= s[i]，输出结果会出现字母以外的字符。( )
{{ select(22) }}
- 正确
- 错误
23、如果 s 的长度是偶数， 那么输出的字符串中大写字母数量和小写字母的数量相同。
{{ select(23) }}
- 正确
- 错误
24、如果输入的 s="abedEFGH"，输出的结果是 ( )
{{ select(24) }}
- ZAbcFGhi
- zaBCfgHl
- BCdeDEfg
- bcDEdeFG
25、将第 14 行的 i & 2 替换为下列哪条语句不会影响最终的答案? ( ) (3 分)
{{ select(25) }}
- i%4%2 ==0
- i%4%2==1
- i%2= 1
- i/2%2==1
26、若输出的字符串 t="AZabGPds"，那么输入的 s 不可能是( ) (3 分)
{{ select(26) }}
- BABCfocr
- zABaHoEr
- zABCHQCT
- zyzCfQcr
3、
01 #include <iostream>
02 using namespace std;
03 int n,a[1001],index[1000];
04 int mark[1000];
05 int main(){
06 cin>>n;
07 for (int i=1; i<=n; i++){
08 cin>>a[i];
09 index[i] = i;
10 }
11 for( int i=1; i<=n; i++)
12 for(int j=1; j<=n-i; j++)
13 if(a[index[j]]>a[index[j+1]]){
14 int t = index[j];
15 index[j] = index[j+1];
16 index[j+1] = t;
17 }
18 int now = 0, ans = 0;
19 for (int i=1; i<=n; i++) {
20 now += mark[i];
21 mark[index[i]] = 1;
22 if (index[i] <= i)
23 now++;
24 if(now == i)
25 ans++;
26 }
27 printf("%d\\n", ans);
28 return 0;
29 }
输入的 n 为正整数
27、输出至少为 1。 ( )
{{ select(27) }}
- 正确
- 错误
28、在第 19 行的循环中， now 始终小于等于 i。 ( )
{{ select(28) }}
- 正确
- 错误
29、若 n=100，则答案最大为( )。 (3 分)
{{ select(29) }}
- 1
- 2
- 99
- 100
30、已知答案为 1，则在第 19 行的循环中， ans=0 时， i 的最大值为（ ）。 (3 分)
{{ select(30) }}
- n
- n-1
- 2
- 1
31、若 n=50，a 数组为 1~n 的排列，并且 a[n]=50,则答案至少为（ ）。 (3 分)
{{ select(31) }}
- 0
- 1
- 2
- 20
32、若 n 等于 6，a 数组依次为 3 2 1 6 4 7，则答案为( )。 (3 分)
{{ select(32) }}
- 1
- 3
- 5
- 6
三、完善程序（单选题，每小题 3 分，共计 30 分）
1、（拔河比赛） 张三现在要给班里的小盆友组织一场拔河比赛，为了公平起见，每一边个数至 少有 1 人，人数相差不能超过 1，张三希望两边的人的体重之差尽量小。除了参加拔河的人，还要挑选至少 1 名同学作为裁判。
第一行输入整数 T,表示数据组数。
每组数据，第一行一个整数 n，表示班里小盆友的个数；第二行 n 个整数，表示每个小盆友的体重。1<= n<= 15, 小盆友的体重范围[30,10000]， 1<=T<=10， 输出 T 个整数，表示最小的体重之差。
输入
2
3
30 31 100
4
30 38 67 1
输出
1
1
1 #include <bits/stdc++.h>
2 using namespace std;
3 int n;
4 int a[20];
5 int main() {
6 int T;
7 cin >> T;
8 while (T--) {
9 cin >> n;
10 for (int i = 0; i < n; i++) cin >> a[i];
11 int ans = 10000 \* n;
12 for (int st = 0; st < (①); st++) {
13 for (int l = st; l; l = ②) { //枚举 st 的子集
14 int r = st ^ l;
15 int cntl = 0, cntr = 0, cntp = 0;
16 int wl = 0, wr = 0;
17 for (int i = 0; i < n; i++) {
18 if (③) {
19 cntl++;
20 wl += a[i];
21 } else if ((1 << i) & r) {
22 cntr++;
23 ④
24 } else {
25 cntp++;
26 }
27 }
28 if (⑤) {
29 ans = min(ans, abs(wl - wr));
30 }
31 }
32 }
33 cout << ans << endl;
34 }
35 }
33、①处应填( )
{{ select(33) }}
- n
- 1 << (n+1)
- n +1
- 1 << n
34、②处应填( )
{{ select(34) }}
- (l - 1) ^ st
- (l - 1)
- (l - 1) & st
- (l - 1) | st
35、③处应填( )
{{ select(35) }}
- (1 << i+1) & l
- (1 << i) & l
- (1 << i+1) | l
- (1 << i) | l
36、 ④处应填( )
{{ select(36) }}
- wr += a[i];
- wl += a[i];
- wr -= a[i];
- wl -= a[i];
37、 ⑤处应填( )
{{ select(37) }}
- cntp>0 || abs(cntl - cntr) <= 1
- cntp>0 && abs(cntl - cntr) <= 1
- cntl>0 && cntr>0 && cntp>0 && abs(cntl - cntr) <= 1
- (cntl>0 || cntr>0 || cntp>0) && abs(cntl - cntr) <= 1
2、迷宫
小 C 最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个 n*m 的 迷宫中， 看看机器人能不能在最短的时间内到达目的地，可是小 C 不知道最短的时间是多少， 现在请你帮他算算机器人到达目的地的最短时间是多少？
输入数据第一行两个整数 n 和 m。 10<=n,m<=500 接下来 n 行， 每行 m 个元素，表示迷宫的每个方格。
'S'表示机器人的出发点 , 'T'表示目的地，
'#'表示该方格不能通过 '. '表示可以通过
输入
3 3
S..
##.
.T.
输出
5
01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 char a[1007][1007];
05 int x, y, n, m;
06 int dx[4] = { ① };
07 int dy[4] = { 0, 0, 1, -1 };
08 bool vis[1007][1007], flag = false;
09 struct node {
10 int row, col, dis;
11 };
12 queue<node> q;
13 bool check(int s, int t) {
14 if (② )
15 return false;
16 if (vis[s][t])
17 return false;
18 if (a[s][t] == '#')
19 return false;
20 return true; 21 }
22 void bfs() {
23 q.push({ x, y, 0 });
24 vis[x][y] = true;
25 while (!q.empty()) {
26 node p = q.front();
27 if (a[p.row][p.col] == 'T') {
28 cout << p.dis << endl;
29 flag = true;
30 break;
31 }
32 for (int i = 0; i < 4; i++) {
33 if (check(p.row + dx[i], p.col + dy[i])) {
34 ③
35 vis[p.row + dx[i]][p.col + dy[i]] = true;
36 }
37 }
38 q.pop();
39 }
40 ④
41 }
42 signed main() {
43 memset(vis, false, sizeof(vis));
44 scanf("%d%d", &n, &m);
45 for (int i = 0; i < n; i++) {
46 cin >> a[i];
47 }
48
49 for (int i = 0; i < n; i++) {
50 for (int j = 0; j < m; j++) {
51 if (⑤ ) {
52 x = i;
53 y = j;
54 break;
55 }
56 }
57 }
58 bfs();
59 return 0;
60 }
38、①处应填( )
{{ select(38) }}
- 0,-1,0,1
- 1,-1,0,0
- 0,0,1,-1
- 1,0,-1,0
39、②处应填( )
{{ select(39) }}
- s < 0 || s >= n || t < 0 || t >= m
- s >= 1 && s <= n && t >=1 && t <= m
- s < 1 || s > n || t < 1 || t > m
- s >= 0 && s < n && t >=0 && t < m
40、③处应填( )
{{ select(40) }}
- q.push({ p.row, p.col, p.dis + 1 });
- q.push({ p.row + dx[i], p.col + dy[i], p.dis + 1 });
- q.push({ p.row, p.col, p.dis});
- q.push({ p.row + dx[i], p.col + dy[i], p.dis});
41、 ④处应填( )
{{ select(41) }}
- while (!q.empty())q.pop();
- if (flag) cout << -1 << endl;
- return;
- if (!flag) cout << -1 << endl;
42、 ⑤处应填( )
{{ select(42) }}
- a[i][j] == '. '
- a[i][j] == '# '
- a[i][j] == 'S'
- a[i][j] == 'T '