#A. CSP 09提高组第一轮

A
    客观题

CSP 09提高组第一轮

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、选择题

1.（）的出现推动了个人计算机的诞生。 {{ select(1) }}

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

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

  • 120
  • 24
  • 720
  • 60

3.在8位二进制补码中，10101010表示的数是十进制下的（）。 {{ select(3) }}

  • 176 176
  • −86 -86
  • −85 -85
  • −84 -84

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

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

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

  • (n−1)2−e(n-1)^2-e
  • 2e2e
  • n2−en^2-e
  • n2−2en^2-2e

6.二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,2,...,8i=0,1,2,...,8，其列下标j=1,2,...,10j=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）输入是一个仅包含大写字母的字符串。

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]∗iF[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.若输入的字符串为DBDC，则输出为（ ）。 {{ select(21) }}

  • 2
  • 4
  • 8
  • 24

（2）

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.若将第六行改为int t=a[0]，程序运行结果不会发生改变。（ ） {{ select(22) }}

  • 正确
  • 错误

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

  • 正确
  • 错误

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

  • 正确
  • 错误

25若输入的n值为1，则无论输入什么，输出都为0。（ ） {{ select(25) }}

  • 正确
  • 错误

选择题

26.该程序的时间复杂度为（ ）。 {{ select(26) }}

  • O(nlogn)O(nlogn)
  • O(n2)O(n^2)
  • O(logn)O(logn)
  • O(n)O(n)

27.若输入为6 1 10 7 8 2 2，则输出为（ ）。 {{ select(27) }}

  • 6
  • 7
  • 2
  • 8

（3）本题是一个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为10610^6）则调用clear（）函数的时间复杂度为（ ）。 {{ select(33) }}

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

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

  • O(n)，O（n）O(n)，O（n）
  • O(1)，O（n）O(1)，O（n）
  • O(1)，O（1）O(1)，O（1）
  • O(1)，O（logn）O(1)，O（logn）

三、完善程序

(1)(树的重心） 给出一个无根树，求树的重心。树的重心的定义：删除这个点及这条边相连的边之后，形成的所有连通块中最大连通块最小。若有多个符合条件的点，输出编号最小的那个。

思路：对每一个点的每一个子树求最大值，找到最大子树最小的点即可。

01   #include <bits/stdc++.h>
02   using namespace std;
03   const int maxn = 2e4 + 5;
04   int son[maxn], n, ans=1, size=1e5;
05   vector<int>G[maxn];
06   void dfs(int now, int pre) {
07   	int tmp = 0;
08   	son[now] = 1; 
09   	for(int i = 0; i < G[now].size(); i++) {
10   		int nxt = G[now][i];
11   		if(nxt != pre) {
12   			dfs(nxt, now);
13   			son[now] += **1**;
14   			tmp = max(tmp, **2**);
15   		}
16   	}
17   	tmp = max(tmp, **3**);
18   	if(**4**){
19   		ans = now;
20   		size = tmp;
21  	 }
22   }
23   int main() {
24   	cin >> n;
25   	for(int i = 1; i < n; i++) {
26   		int u, v;
27   		cin >> u >> v;
28   		G[u].push_back(v);
29   		G[v].push_back(u);
30   	}
31   	dfs(1,-1);
32   	cout << ans << endl;
33   }

35.①处应填（ ）。 {{ select(35) }}

  • son[nxt]son[nxt]
  • son[nxt]+1son[nxt]+1
  • 11
  • son[now]son[now]

36.②处应填（ ）。 {{ select(36) }}

  • son[now]son[now]
  • son[now]+1son[now]+1
  • son[nxt]+1son[nxt]+1
  • son[nxt]son[nxt]

37.③处应填（ ）。 {{ select(37) }}

  • son[now]son[now]
  • n−son[now]n-son[now]
  • n−son[now]−1n-son[now]-1
  • son[now]+1son[now]+1

38.④处应填（ ）。 {{ select(38) }}

  • tmp<sizetmp<size
  • tmp<=sizetmp<=size
  • tmp∗maxn+now<size∗maxn+anstmp*maxn+now<size*maxn+ans
  • now∗maxn+tmp<ans∗maxn+sizenow*maxn+tmp<ans*maxn+size

(2)(数字游戏） Alice和Bob正在玩数字游戏，初始时两个人手中的数字分别为a，b，两个人轮流操作，每次操作要么把手中的数字加上对方手中的数字，然后对n求余；要么用手中的数字乘以对方手中的数字，然后对n求余。得到的新数字替换自己手上原来的数字。假设n=5，a=2，b=3，那么Alice可以使用第一种操作使得自己手上的数字变成0（（2+5）%5=0），或者用第二种操作让自己手上的数字变成1。

谁先让自己手上的数字变成0谁就获胜，输出1表示先手必胜，0表示平局，-1表示后手必胜。（1<=a,b<n<=10001<=a,b<n<=1000）

01  #include <bits/stdc++.h>
02  using namespace std;
03  vector<int> g[1100000];
04  int f[1100000];
05  int n, k, a, b;
06  #define id(a,b) (a*n+b)
07  int cnt[1100000];
08  void init(int n) {
09  	for(int i = 1; i < n; i++)
10  		for(int j = 1; j < n; j++)
11  			g[id(j,**1**)].push_back(id(i,j));
12  	for(int i = 1; i < n; i++)
13  		for(int j = 1; j < n; j++)
14  			g[id(j,(i+j)%n)].push_back(id(i,j));
15  }
16  int main() {
17  	cin >> n;
18  	init(n);
19  	queue<pair<int, int> > Q;
20  	for(int i = 0; i <= n * n; i++)
21  		cnt[i] = **2**;
22  	for(int i = 1; i < n; i++)
23  		Q.push(**3**);
24  	while(!Q.empty()) {
25  		pair<int, int> x = Q.front();
26  		Q.pop();
27  		for(int y : g[x.first]) {
28  			if (**4**)	continue;
29  			if (!x.second) {
30  				f[y] = 1;
31  				Q.push({y, 1});
32  			} else {
33  				cnt[y]--;
34  				if(!cnt[y]) {
35  					f[y] = -1;
36  					Q.push(**5**);
37  				}
38  			}
39  		}
40  	}
41  	cin >> a >> b;
42  	cout << f[**6**] << endl;
43  }

39.①处应填（ ）。 {{ select(39) }}

  • i+j%n
  • i+j
  • i*j
  • (i*j)%n

40.②处应填（ ）。 {{ select(40) }}

  • 2
  • 1
  • n
  • n/2

41.③处应填（ ）。 {{ select(41) }}

  • {i,0}
  • {i,1}
  • {n*i,0}
  • {n*i,1}

42.④处应填（ ）。 {{ select(42) }}

  • f[y] == 0
  • f[y] != 0
  • f[x.second] != 0
  • f[x.second] == 0

43.⑤处应填（ ）。 {{ select(43) }}

  • {y,0}
  • {y,-1}
  • {y,1}
  • {y,n}

44.⑥处应填（ ）。 {{ select(44) }}

  • a+b
  • a*b%n
  • (a+b)%n
  • id(a,b)

CSP-S初赛模拟1

已参加
状态
已结束 (已参加)
规则
IOI(ObjectiveFirstSubmit)
题目
1
开始于
2024-8-26 20:08
结束于
2024-9-24 21:00
持续时间
770 小时
主持人
参赛人数
218
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 31ms
  4. Powered by Hydro v4.9.24 Community, Modified by hetao