CSP-J 2024 初赛模拟02

一、单项选择题：本题共 15 小题，每题 2 分，共 30 分。

每题有且仅有一个正确选项。

1. 一棵层数为 n 的满二叉树有（ ）个结点？

{{ select(1) }}

• $n$
• $2^n$
• $2^{n-1}$
• $2^n-1$

2. （ ）是一种先进后出的线性表。

{{ select(2) }}

• 栈
• 队列
• 哈希表
• 链表

3. 硬盘是（ ）的重要组成部分

{{ select(3) }}

• 冯诺依曼体系结构
• 存储器
• CPU
• 控制器

4. 下列不属于图像格式的是：

{{ select(4) }}

• jpg
• png
• mp4
• gif

5. 编译器的功能是：

{{ select(5) }}

• 将高级语言翻译成软件
• 将高级语言翻译成低级语言或机器语言
• 将高级语言翻译成自然语言
• 将自然语言翻译成高级语言

6. 下列电子元件中，存取速度最快的是：

{{ select(6) }}

• 高速缓冲存储器（cache）
• 寄存器
• 固态硬盘（SSD）
• 内存

7. （ ）算法就是把一个复杂的问题分成两个或者更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后的子问题可以简单的直接求解。而原问题的解就是子问题解的并。

{{ select(7) }}

• 贪心
• 回溯
• 分治
• 枚举

8. 在平面直角坐标系中取 n 个整点（即横纵坐标均为整数的点）。当 n 至少为( )时，这 n 个点中必定会有两个点的中点为整点。

{{ select(8) }}

• 4
• 3
• 6
• 5

9. 一棵二叉树，前序遍历是 1243576，中序遍历是 2415736，则后序遍历是

{{ select(9) }}

• 4257631
• 4275631
• 7425631
• 4276531

10. 全国青少年信息学奥林匹克竞赛的英文缩写是

{{ select(10) }}

• NOIP
• CSP
• CCF
• NOI

11. 小明买了一个存储空间为 128G 的手机，用于存放 128G 内容的硬件属于哪一种硬件？

{{ select(11) }}

• 内存
• 外存
• 高速缓冲存储器（cache）
• 输入设备

12. 在 C++ 程序中，表达式 130 | 10 的值为

{{ select(12) }}

• 13
• 1
• 120
• 138

13. 一棵有 n 个结点的树具有的性质是（ ）

{{ select(13) }}

• 有 n 条边
• 每个节点都只有最多两个孩子
• 可能有两个点之间没有路径
• 可能没有边

14. 三名男生，四名女生中选三人，要求至少有一名男生和一名女生，求方案数。

{{ select(14) }}

• 12
• 35
• 30
• 15

15. 在参加 NOI 系列竞赛过程中，下面哪一种行为是不被严格禁止的 。

{{ select(15) }}

• 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
• 通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
• 通过互联网搜素取得解题思路。
• 在提交的程序中启动多个进程以提高程序的执行效率。

二、阅读程序（除特殊说明外判断题 1 分，选择题 4 分，共计 40 分。）

阅读程序第一题

01  #include <iostream>
02  #include <cstring>
03  using namespace std;
04  int main() {
05  	int n, ans = 0;
06  	cin >> n;
07  	int a[100], b[100];
08  	memset(a, 0, sizeof a);
09  	for(int i = 0; i < n; i++)
10  		cin >> b[i];
11  	for(int i = 0; i < n; i++) {
12  		for(int j = 0; j < n; j++) {
13  			if(b[i] + b[j] == a[0]) {
14  				ans++;
15  			}
16  		}
17  	}
18  	cout << ans << endl;
19  }

判断题

16. 这个程序读入了一个整数 n 和一个整数数组，并且将整数数组存在数组 a 中。

{{ select(16) }}

• 正确
• 错误

17. 若将第 13 行中的 a[0] 改为 a[1]，则程序运行结果可能会发生改变。

{{ select(17) }}

• 正确
• 错误

18. 若将第 8 行改为 memset(a, 1, sizeof a);，则执行完此语句后，a[0] 的值为 1。

{{ select(18) }}

• 正确
• 错误

19. 若将第 8 行改为 memset(a, 0, 4);，则程序运行结果一定不变。

{{ select(19) }}

• 正确
• 错误

选择题

20. 若输入的 n 为 5，输入的五个数字分别是 1 2 -1 -2 0，则程序的输出结果为

{{ select(20) }}

• 5
• 3
• 4
• 2

21. 若输入了 50 个数字，则输出的结果最多为

{{ select(21) }}

• 2500
• 1250
• 2450
• 1225

阅读程序第二题

1 #include<iostream> 
2 using namespace std; 
3 const int maxn = 110; 
4 int a[maxn], b[maxn], n, ans; 
5 int main(){ 
6 		cin >> n; 
7 		for(int i = 1; i <= n; i++) { 
8 			int x; 
9 			cin >> x; 
10 			a[i] = x; 
11 			if(!b[x])	b[x] = i; 
12 		} 
13 		ans = 0;
14 		for(int i = 1; i <= n; i++){ 
15 			ans += a[i] * b[i]; 
16 		} 
17 		cout << ans << endl;
18 		return 0; 
19 } 

判断题

22. 若输入的 x 均不为 0，则 a 数组的 [1...n] 元素一定均不为 0

{{ select(22) }}

• 正确
• 错误

23. 若输入的 x 均不为 0，则 b 数组的 [1...n] 元素一定均不为 0

{{ select(23) }}

• 正确
• 错误

24. 若输入的数字均为正整数且程序正常运行，则程序输出的结果一定大于 0

{{ select(24) }}

• 正确
• 错误

25. 若输入的 n 为 5，且其余输入的数字均为 int 范围内的数字，则该程序一定能正常运行并输出结果

{{ select(25) }}

• 正确
• 错误

选择题

26. 若输入为 5 2 2 3 3 5，则该程序的输出为

{{ select(26) }}

• 36
• 38
• 39
• 21

27. 要想让 b 数组的 [1...n] 元素均不为 0 并且 ans 大于 100，那么 n 最小应该为 .

{{ select(27) }}

• 6
• 7
• 8
• 9

阅读程序第三题

注意：输入的字符串仅包含 { } [ ] ( ) 这六种字符中的一种。

01  #include <iostream>
02  #include <stack>
03  using namespace std;
04  int main(){
05  	string s;
06  	cin >> s;
07  	stack<int>sta;
08  	bool flag = true;
09  	char a[] = {'{', '[', '(', '}', ']', ')'};
10  	for(int i = 0; i < s.size(); i++){
11  		for(int j = 0; j < 6; j++){
12  			if(a[j] != s[i])	continue;
13  			if(j <= 2)	sta.push(j);
14  			else if(!sta.empty()){
15  				int now = sta.top();
16  				sta.pop();
17  				if(now + 3 != j)	flag = false;
18  			}else{
19  				flag = false;
20  			}	
21  		}
22  	}
23  	cout << ((flag && sta.empty()) ? "YES" : "NO");
24  }

判断题

28. 若将第 9 行的 char a[] 改为 char a[6]，程序运行结果一定不变。

{{ select(28) }}

• 正确
• 错误

29. 若将第 9 行改为 char a[] = {"{[(}])"};，程序运行结果一定不变。

{{ select(29) }}

• 正确
• 错误

30. 若在第 20 行之后加上一句 break;，程序运行结果一定不变。

{{ select(30) }}

• 正确
• 错误

31. 如果输入的字符串长度为奇数，则程序运行结果一定为 NO。

{{ select(31) }}

• 正确
• 错误

32. 若将第 23 行中的 flag && sta.empty() 改为 flag，程序运行结果一定不变。

{{ select(32) }}

• 正确
• 错误

33. 第 7 行刚定义 sta 时，sta 内容为随机值。

{{ select(33) }}

• 正确
• 错误

34. 若将第 6 行改为 getline(cin, s);，程序运行结果一定不变。

{{ select(34) }}

• 正确
• 错误

35. 如果输入的字符串长度大于 6，则程序可能会运行崩溃。

{{ select(35) }}

• 正确
• 错误

选择题

36. 如果输入的字符串长度为 100，则 sta 中元素的数量最多为

{{ select(36) }}

• 50
• 100
• 6
• 3

37. 若程序的输出结果为 YES，则输入的字符串可能为

{{ select(37) }}

• {[(())(])}
• {}[]((([)]))
• {[]}[{}]()
• {()}([)]()

三、完善程序（单选题，每小题 3 分，共计 30 分）

1. （选择数对）有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船）

输入格式：第一行给出 n，k 分别表示小朋友的个数，以及参数 k。$(1≤n,k≤10^5)$，接下来给出 n 个数字，表示每个小朋友手上的数字。

提示：二分最终的结果，对于二分的结果 mid，在 check 函数中 $O(n)$ 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。

01  #include <iostream>
02  #include <algorithm>
03  using namespace std;
04  const int maxn = 1e5 + 5;
05  int a[maxn], n, k;
06  bool check(int mid){
07  	bool flag = true;
08  	for(int i = 1, **1**; j <= n; j++, i++){
09  		if(**2**)
10  			flag = false;
11  	}
12  	return flag;
13  }
14  int main(){
15  	cin >> n >> k;
16  	for(int i = 1; i <= n; i++)
17  		cin >> a[i];
18  	int l = **3**, r = n, ans;
19  	sort(a+1, a+1+n);
20  	while(l <= r){
21  		int mid = (l + r) / 2;
22  		if(check(mid)){
23  			**4**;
24  			ans = mid;
25  		}else{
26  			**5**;
27  		}
28  	}
29  	cout << ans << endl;
30  }

38. 1 处应该填的代码是:

{{ select(38) }}

• j = 1
• j = n - mid
• j = n - mid + 1
• j = mid

39. 2 处应该填的代码是:

{{ select(39) }}

• a[i] - a[j] > k
• a[i] - a[j] <= k
• a[j] - a[i] > k
• a[j] - a[i] <= k

40. 3 处应该填的代码是:

{{ select(40) }}

• 1
• 0
• n/2
• a[1]

41. 4 处应该填的代码是:

{{ select(41) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

42. 5 处应该填的代码是:

{{ select(42) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

2. (栅栏涂色)现在有 $n$ 个宽度为 1 的栅栏（可以看作长方形）在平面上并列，其中第 $i$ 个栅栏的高度为 $a_i$，现在要每次可以选择一块长方形的区域涂色，不能涂到无栅栏的地方。问至少涂色几次，可以把所有栅栏全部涂色（一个位置可以被涂色多次）

输入第一行包含一个正整数 $n$，接下来 $n$ 个数字分别表示每个长方体的高度 $a_i$。

解题思路：用递归来求解，假设现在需要涂色 a[l] 到 a[r] 的栅栏，我们可以横着涂一个 minn * (r-l+1) 的区域，其中 minn 为这些栅栏的最低高度。此时会将栅栏中未涂色的区域分成多段（因为可能有多个地方高度为 minn），再分别进行递归即可。

01  #include <bits/stdc++.h>
02  using namespace std;
03  const int maxn = 1e5 + 5;
04  int a[maxn], n;
05  int get_st(int st, int minn) { // 获得本段递归的起点
06  	while(a[st] == minn) st++; // minn 的地方已经被涂了，所以无需涂色
07  	return st;
08  }
09  int dfs(int l, int r) {
10  	if(l > r)
11  		**1**;
12  	int minn = 1e9;
13  	for(int i = l; i <= r; i++)
14  		minn = min(a[i], minn);
15  	int res = 0, st = get_st(l, minn);
16  	for(int i = st + 1; i <= r; i++) {
17  		if(a[i] == minn) {
18  			res += dfs(st, i-1);
19  			st = **2**;
20  		}
21  	}
22  	if(st <= r)	res += **3**;
23  	return **4**;
24  }
25  int main() {
26  	cin >> n;
27  	for(int i = 1; i <= n; i++)
28  		cin >> a[i];
29  	cout << **5**;
30  }

43. 1 处代码应该填

{{ select(43) }}

• return
• return 0
• return 1
• 什么也不用填

44. 2 处代码应该填

{{ select(44) }}

• get_st(i, minn);
• i
• i + 1
• res

45. 3 处代码应该填

{{ select(45) }}

• dfs(st, r-1)
• dfs(st + 1, r)
• dfs(st, r)
• dfs(st + 1, r-1)

46. 4 处代码应填

{{ select(46) }}

• res + 1
• res
• res + dfs(l, st) + dfs(st, r)
• res + dfs(l, st - 1) + dfs(st + 1, r)

47. 5 处代码应填

{{ select(47) }}

• res
• dfs(1, n)
• dfs(l, r)
• dfs(1, n) - 1