該比賽已結束，您無法在比賽模式下遞交該題目。您可以點選“在題庫中開啟”以普通模式檢視和遞交本題。

CSP-S 初赛模拟卷01

一、单项选择题（共15题，每题2分，共计30分;每题有且仅有一个正确选项）

1. （）的出现推动了个人计算机的诞生。

{{ select(1) }}

• 晶体管
• 电子管
• 大规模集成电路
• 集成电路

2. 一个大小为 $5×5$ 的空地，在其中选取5块，使得任意2块不在同一行同一列的方案数量是（）。

{{ select(2) }}

• 120
• 24
• 720
• 60

3. 在 $8$ 位二进制补码中，$10101010$ 表示的数是十进制下的（）。

{{ select(3) }}

• $(176)_{10}$
• $(-86)_{10}$
• $(-85)_{10}$
• $(-84)_{10}$

4. 关键字序列 $(8,9,10,4,5,6,20,1,2)$ 只能是在下列排序算法中（）的两趟排序后的结果。

{{ select(4) }}

• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

5. 在含 $n$ 个顶点和 $e$ 条边的无向图的邻接矩阵中，零元素的个数为（）。

{{ select(5) }}

• $(n-1)^2-e$
• $2e$
• $n^2-e$
• $n^2-2e$

6. 二维数组A的每个元素是由10个字符组成的串，其行下标 $i=0,1,2,...,8$，其列下标 $j=1,2,...,10$。若 $A$ 按行先存储，元素 $A[8][5]$ 的起始地址与 $A$ 按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。

{{ select(6) }}

• $A[8][5]$
• $A[3][10]$
• $A[5][8]$
• $A[0][9]$

7. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点数量是（）。

{{ select(7) }}

• 9
• 11
• 15
• 不确定

8. 某文本包含240个汉字，39个数字以及666个字母，若将其强制转换为一个char数组，形如char[]="你好123abc”，不计算末尾的\0，则数组的长度为（）。

{{ select(8) }}

• 945
• 279
• 1851
• 1185

9. 前序遍历序列与中序遍历序列相同的二叉树为（）。

{{ select(9) }}

• 根结点无左子树的二叉树
• 根结点无右子树的二叉树
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

10. dijkstra算法用到的思想是（）。

{{ select(10) }}

• 动态规划
• 枚举
• 贪心
• 二分

11. 烧烤店有三种肉串售卖，其中肉串A的价格是2元，肉串B是3元，肉串C是4元，你有20元，恰好将钱花光的购买方案有（）种。

{{ select(11) }}

• 12
• 14
• 16
• 18

12. A，B，C，D，E五人吃饭，围成圆桌，要求A和D不相邻，方案数有（）种。

{{ select(12) }}

• 12
• 15
• 18
• 24

13. 有6个完全一样的小球，放3个标号为1到3的箱子中，其中1号箱子至少一个小球，2号和3号可以为空，不同的方案数量有（）。

{{ select(13) }}

• 15
• 18
• 21
• 24

14. 现在从10个小朋友中选3个小朋友参加文艺汇演，其中小朋友1和2的关系很好，要么两个小朋友一起参加要么都不参加，你有（）种不同的选派方案。

{{ select(14) }}

• 48
• 56
• 64
• 72

15. 现在有5个不同的节目要排出场顺序，其中节目1和节目2不能安排在相邻的顺序出场，节目2和节目3必须安排在相邻顺序出场，则总的出场顺序有（）种。

{{ select(15) }}

• 24
• 36
• 48
• 60

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第一题

输入是一个仅包含大写字母的字符串。

01  #include <bits/stdc++.h>
02  using namespace std;
03  const int maxn = 2e5 + 5;
04  string str;
05  int num[30], n;
06  long long F[maxn];
07  long long comb(int n, int m){
08      if(m < 0 || m > n) return 0;
09      return F[n] / F[m] / F[n-m];
10  }
11  long long dfs(int len, int now){
12  	if(len == n - 1)	return 1;
13  	if(len != -1 && now < str[len] - 'A'){
14  		int need = n - len - 1;
15  		long long tmp = 1;
16  		for(int i = 0; i < 26; i++)
17                if(num[i]){
18                    tmp *= comb(need, num[i]);
19  			need -= num[i];
20  		    }
21  		return tmp;
22  	}
23  	long long tmp = 0;
24  	for(int i = 0; i < 26; i++){
25  		if(i <= str[len+1] - 'A' && num[i]){
26  			num[i]--;
27  			tmp += dfs(len + 1, i);
28  			num[i]++;
29  		}
30  	}
31  	return tmp;
32  }
33  int main(){
34  	F[0] = 1;               
35  	for(int i = 1; i < maxn; i++){
36          F[i] = F[i-1] * i;
37      }
38  	cin >> str;
39  	n = str.size();
40  	for(int i = 0; i < n; i++)
41  		num[str[i]-'A']++; 
42  	cout << dfs(-1,30);	
43  }

判断题

16. 若删去第 8 行，程序运行结果一定不变。（ ）

{{ select(16) }}

• 正确
• 错误

17. 若将 36 行改为 F[i] = F[i − 1] ∗ i，程序运行结果一定不变。（ ）

{{ select(17) }}

• 正确
• 错误

18. 若输入的字符串长度大于24，程序运行结果可能为负数。（ ）

{{ select(18) }}

• 正确
• 错误

19. 若删除第 34 行，则无论输入什么，输出都为 0。（ ）

{{ select(19) }}

• 正确
• 错误

选择题

20. 若输入的字符串为 CCCCCCCCCC（10个C），则输出为（ ）。

{{ select(20) }}

• 1
• 10
• 55
• 3628800（10的阶乘）

21. （4分）若输入的字符串为 DBDC，则输出为（ ）。

{{ select(21) }}

• 2
• 4
• 8
• 24

第二题

01  #include <bits/stdc++.h> 
02  using namespace std; 
03  int n; 
04  int dfs(vector<int> a, int l = 0, int r = n - 1){ 
05  	if(l == r && l != n / 2)	return 0; 
06  	int t = a[rand() % (r - l + 1)]; 
07  	vector<int>low, up; 
08  	for(int i = 0; i < r - l + 1; i++){ 
09  		if(a[i] < t){ 
10  			low.push_back(a[i]); 
11  		}else if(a[i] > t){ 
12  			up.push_back(a[i]); 
13  		} 
14  	} 
15  	if(l + (int)low.size() - 1 >= n / 2) 
16  		return dfs(low, l, l + low.size() - 1); 
17  	else if(r - up.size() + 1 <= n / 2) 
18  		return dfs(up, l + low.size() + 1, r); 
19  	else 
20  		return t; 
21  } 
22  int main(){ 
23  	cin >> n; 
24  	vector<int>a(n); 
25  	for(int i = 0; i < n; i++){ 
26  		cin >> a[i]; 
27  	} 
28  	cout << dfs(a); 
29  }

判断题

22. 若将第 6 行改为 int t=a[0]，程序运行结果不会发生改变。（ ）

{{ select(22) }}

• 正确
• 错误

23. 若将第 4 行的后两个参数改为 int l，int r ，程序运行结果不会发生改变。（ ）

{{ select(23) }}

• 正确
• 错误

24. 第 5 行的后面应该再加一个判断语句 if(l>r)return 0;,若不加，则程序可能会死循环。（ ）

{{ select(24) }}

• 正确
• 错误

25. 若输入的 n 值为 1，则无论输入什么，输出都为 0。（ ）

{{ select(25) }}

• 正确
• 错误

选择题

26. 该程序的时间复杂度为（ ）。

{{ select(26) }}

• $O(n\text { log }n)$
• $O(n^2)$
• $O(\text{log }n)$
• $O(n)$

27. 若输入为 6 1 10 7 8 2 2，则输出为（ ）。

{{ select(27) }}

• 6
• 7
• 2
• 8

第三题

本题是一个hash_map，用与储存一些映射关系

01  #include <bits/stdc++.h>
02  using namespace std;
03  #define ll long long
04  const int maxm = 1e6 + 5;
05  class hash_map {
06  public:
07  	struct node {
08  		ll u;
09  		ll v,next;
10  	} e[maxm<<1];
11  	ll head[maxm],nume,numk,id[maxm];
12  	ll& operator[](ll u) {
13  		int hs = u % maxm;
14  		for(int i = head[hs]; i; i = e[i].next)
15  			if(e[i].u == u) return e[i].v;
16  		if(!head[hs])	id[++numk] = hs;
17  		return e[++nume] = (node) {u,0,head[hs]}, head[hs] = nume, e[nume].v;
18  	}
19  	void clear() {
20  		for(int i = 0; i <= numk; i++)
21  			head[id[i]] = 0;
22  		numk = nume = 0;
23  	}
24  } m;
25  int main() {
26  	int n;
27  	ll a, b, c;
28  	cin >> n;
29  	while(n--) {
30  		cin >> a;
31  		if(a == 1) {
32  			cin >> b >> c;
33  			m[b] = c;
34  		} else {
35  			cin >> b;
36  			cout << m[b] << endl;
37  		}
38  	}
39  }

判断题

28. 该hash_map只能存储整数与整数的对应关系，无法存储字符串或者小数与整数的对应关系。（ ）

{{ select(28) }}

• 正确
• 错误

29. 首先输入1使得n=1，然后再输入2 3，输出为0。（ ）

{{ select(29) }}

• 正确
• 错误

30. 若输入的所有a都为1，则程序没有输出。（ ）

{{ select(30) }}

• 正确
• 错误

31. 若先输入3，然后输入1 2 3\n 1 2 4\n 2 2(其中\n为换行符），则输出为4。（ ）

{{ select(31) }}

• 正确
• 错误

选择题

32. 该代码解决哈希冲突的方式为（ ）。

{{ select(32) }}

• 链地址法
• 线性探测再散列法
• 再哈希法
• 改代码不解决冲突，只避免了冲突的发生

33. 若已插入的元素数量为n，数组大小为m（本代码中m为 $10^6$）则调用clear（）函数的时间复杂度为（ ）。

{{ select(33) }}

• $O(n)$
• $O(m)$
• $O(n+m)$
• $O(nm)$

34. 若已插入元素数量为n，且n的大小约为 $\dfrac {m} {100}$，则单词调用[]的平均复杂度和最坏复杂度为（ ）。

{{ select(34) }}

• $O(n),O(n)$
• $O(1),O(n)$
• $O(1),O(1)$
• $O(1),O(\text {log } n)$