30.5 #2033. CSP 09提高组第一轮

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

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 27ms
  4. Powered by Hydro v4.9.24 Community, Modified by hetao