#A. CSP 10提高组第一轮

A
    客观题

CSP 10提高组第一轮

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

一、选择题

1.哈希函数为%11（对11求余），数组长度为11（下标从0到10），哈希冲突的解决方法是线性探测再散列法。元素插入依次是11，15，13，22，33。若此时再次插入一个元素1，请问会插入在数组的哪一个下标？（） {{ select(1) }}

  • 2
  • 3
  • 4
  • 5

2.哪种不是解决哈希冲突的方法（）？ {{ select(2) }}

  • 链地址法
  • 线性探测再散列法
  • 再哈希法
  • 制定复杂的哈希函数

3.设A=B=true，C=D=false，以下逻辑运算表达式值为假的有（）？ {{ select(3) }}

  • (¬ A∧B)∨(C∧D∨A)
  • ¬ (((A∧B)∨C)∧D)
  • A∧(B∨C∨D)∨D
  • (A∧(D∨C)) ∧B

4.若某算法的计算时间表示为递推关系式：T(N) = 2T(N / 2) + N log N，T(1) = 1，则该算法的时间复杂度为（）？ {{ select(4) }}

  • O(N2)O(N^2)
  • O(NlogN)O(NlogN)
  • O(Nlog2N)O(Nlog^2N)
  • O(N)O(N)

5.(110000)2(110000)_2和(1010111)2(1010111)_2求按位异或的结果是（）？ {{ select(5) }}

  • (100111)2(100111)_2
  • (1100111)2(1100111)_2
  • (0100111)2(0100111)_2
  • (1110111)2(1110111)_2

6.牛牛用数组实现一个循环队列，数组大小为n，即队列至多可以容纳n个元素。有两个变量front和rear分别表示队首和队尾。初始front=rear=0，每插入一个元素，则先插入到rear的位置，然后rear的值加一，每弹出一个元素，则先将front对应位置标记删除，然后front的值加一。因为是循环队列，所以front和rear的值需要随时对n求余。假设这个队列正常运行，请问以下说法正确的是（）？ {{ select(6) }}

  • front加一的次数可能比rear加一的次数多
  • front和rear既可以是指针类型，也可以是整数类型
  • front的值应当始终小于等于rear的值
  • 若rear指向的位置有元素，则说明队列已满，无法再插入元素

7.现在15个省三好学生名额分给1、2、3、4共四个班级，其中1班至少2个名额，2班、4班每班至少3个名额，3班最多2个名额，则共有（）种不同的分配方案？ {{ select(7) }}

  • 109
  • 85
  • 81
  • 144

8.牛牛写了一个快速幂的伪代码，请问说法正确的是（）？{{ select(8) }}

  • 这个代码对于N是奇数的情况无法获得正确的答案
  • 这个代码的时间复杂度是O(N)O(N)
  • 这个代码的时间复杂度是O(logN)O(logN)
  • 这个代码只要当N是2的幂次的情况才可以获得正确的答案
function fast_pow(int x, int N) // fast_pow 函数，用于求 x 的 N 次方
      如果 N 是 0：
             return 1
     如果 N 是偶数：
            return fast_pow(x, N/2) * fast_pow(x, N/2)
      如果 N 是奇数
            return fast_pow(x, N/2) * fast_pow(x, N/2) * x

9.可以将单个计算机接入到计算机网络中的网络接入通讯设备是（）？ {{ select(9) }}

  • 网卡
  • 内存
  • 显卡
  • 鼠标

10.以下哪个linux指令可以用于删除某一文件（）？ {{ select(10) }}

  • mv
  • Is
  • rm
  • mkdir

11.（）这一排序算法是不稳定的。 {{ select(11) }}

  • 冒泡排序
  • 插入排序
  • 归并排序
  • 快速排序

12.有一支医疗小队由3名不同的医生和5名不同的护士组成，他们全部要分配到三家不同的医院。每家医院分到的医生1名和护士1至3名，问有多少种不同的分法（）？ {{ select(12) }}

  • 900
  • 216
  • 1800
  • 108

13.以下哪种语言是编译型语言（）？ {{ select(13) }}

  • JAVA
  • C语言
  • python
  • scratch

14.表达式a∗d−b∗ca*d-b*c的前缀形式是（）？ {{ select(14) }}

  • a d ∗* b c∗−*-
  • −∗- * a d ∗* b c
  • a * d−- b * c
  • −- * * a d b c

15.一段文字中字母a出现7次，字母b出现4次，字母c出现5次，字母d出现1次，若要使用哈夫曼编码的方式给这四个字母进行01编码，请问整个文本编码之后的长度之和是多少（）？ {{ select(15) }}

  • 32
  • 39
  • 28
  • 33

二、阅读程序

（1）

01   #include <bits/stdc++.h>
02   using namespace std;
03   int t, n, m, q, k, a, b;
04   vector<pair<int,int> >G;
05   bool vis[1001];
06   bool dfs(int now, int dep) {
07   	if(now == m)	return true;
08   	int u = G[now].first, v = G[now].second;
09   	while((vis[u] || vis[v]) && now < m) {
10   		now++;
11   		if(now == m)	break;
12   		u = G[now].first, v = G[now].second;
13   	}
14   	if(now == m)	return true;
15   	if(dep == k)	return false;
16   	bool res = false;
17   	vis[u] = 1;
18   	res |= dfs(now + 1, dep + 1);
19   	vis[u] = 0;
20   	vis[v] = 1;
21   	res |= dfs(now + 1, dep + 1);
22   	vis[v] = 0;
23   	return res;
24   }
25   int main() {
26   	cin >> n >> m >> q;
27   	k = n - q;
28   	for(int i = 1; i <= m; i++) {
29   		cin >> a >> b;
30   		G.push_back({a, b});
31   	}
32   	if(dfs(0, 0))	cout << "Yes\n";
33   	else	cout << "No\n";
34   }

判断题

16.若交换14、15行的代码，程序运行结果不会改变（） {{ select(16) }}

  • 正确
  • 错误

17.若将30行改为G.push_back（{b,a}）;，程序运行结果不会改变 {{ select(17) }}

  • 正确
  • 错误

18.该代码的存图方式为邻接表法（） {{ select(18) }}

  • 正确
  • 错误

19.若删除19行，则程序运行结果可能会发生改变；但删去22行则不会（） {{ select(19) }}

  • 正确
  • 错误

选择题

20.该代码的时间复杂度为（） {{ select(20) }}

  • O(2n−q)O(2^{n-q})
  • O(2n−q∗m)O(2^{n-q}*m)
  • O(2n−q+m)O(2^{n-q}+m)
  • O(2n+m)O(2^n+m)

21.已知输入m为7，n为8，对应的7组a，b分别为[1,3],[2,3],[5,2],[6,3],[7,1],[7,4],[2,8]。请问，q至多为多少时可以输出Yes（）？ {{ select(21) }}

  • 2
  • 3
  • 4
  • 5

（2）

01  #include <bits/stdc++.h>
02  using namespace std;
03  const int mod = 1e9 + 7;
04  long long dp[(1<<17)+2], a[20], n, k;
05  int main(){
06  	cin >> n >> k;
07  	for(int i = 0; i < n; i++){
08  		cin >> a[i];
09  		if(a[i] > k)	return cout << 0, 0;
10  	}
11  	dp[0] = 1;
12  	for(int i = 0; i < (1 << n); i++){
13  		for(int j = 0; j < n; j++){
14  			if(i >> j & 1)	continue;
15  			dp[i | 1 << j] = (dp[i | 1 << j] + dp[i]) % mod;
16  			for(int u = 0; u < n; u++){
17  				if(i >> u & 1)	continue;
18  				if(j == u)	continue;
19  				if(a[j] + a[u] > k)	continue;
20  				int now = i | (1 << j) | (1 << u);
21  				dp[now] = (dp[now] + dp[i]) % mod;
22  			}
23  		}
24  	}
25  	cout << dp[(1<<n)-1] << endl;
26  }

判断题

22.若将11行的语句删除，则无论输入是什么，程序的输出都是0（） {{ select(22) }}

  • 正确
  • 错误

23.第20行定义的now在任何时候都大于等于3（） {{ select(23) }}

  • 正确
  • 错误

24.若输入的n为17，则程序会发生数组越界的情况（） {{ select(24) }}

  • 正确
  • 错误

25.若删除第9行，则程序的结果可能会发生改变（） {{ select(25) }}

  • 正确
  • 错误

选择题

26.若输入为2 5 3 4（前两个数字为n，k，后面两个数字是aia_i），则输出为（） {{ select(26) }}

  • 1
  • 2
  • 3
  • 4

27.若输入为4 6 2 3 4 5 （前两个数字为n，k，后面四个数字是aia_i），则输出为（） {{ select(27) }}

  • 120
  • 60
  • 48
  • 24

（3）

01  #include<bits/stdc++.h>
02  const int maxn = 1000;
03  using namespace std;
04  struct node{
05  	int weight;
06  	int parent, lchild, rchild;
07  };
08  int s1, s2, w[maxn], n, res[maxn];
09  char ans[maxn];
10  node HT[maxn];
11  void getMin(int x){
12  	int min1 = maxn, min2 = maxn;
13  	for(int i = 1; i <= x; i++){
14  		if(HT[i].parent)	continue;
15  		int val = HT[i].weight;
16  		if(val < min1){ 
17  			min2 = min1;
18  			s2 = s1;
19  			min1 = val;
20  			s1 = i;
21  		}else if(val < min2){
22  			min2 = val;
23  			s2 = i;
24  		}
25  	}
26  }
27  void init(){
28  	int m = 2 * n - 1;
29  	for(int i = 1; i <= m; i++) {
30  		if(i <= n)
31  			HT[i].weight = w[i];
32  		else
33  			HT[i].weight = 0;
34  		HT[i].parent = HT[i].lchild = HT[i].rchild = 0; 
35  	}
36  	for(int i = n + 1; i <= m; i++){
37  		getMin(i-1);
38  		HT[s1].parent = HT[s2].parent = i;
39  		HT[i].lchild = s1;
40  		HT[i].rchild = s2;
41  		HT[i].weight = HT[s1].weight + HT[s2].weight; 
42  	}
43  	for(int i = 1; i <= n; i++){
44  		char s[maxn];
45  		int cnt = 0;
46  		int start = n - 1, c, f; 
47  		for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent){
48  			if(HT[f].lchild == c)
49  				s[cnt] = '0';
50  			else
51  				s[cnt] = '1';
52  			cnt++;
53  		}
54  		cout << ans[i] << " ";
55  		for(int j = cnt - 1; j >= 0; j--)
56  			cout << s[j];
57  		cout << endl;
58  	}
59  }
60  int main(){
61  	string s; 
62  	cin >> s;
63  	int cnt[200] = {};
64  	for(int i = 0; i < s.size(); i++){
65  		cnt[s[i]]++;
66  	}
67  	for(int i = 1; i < 200; i++){
68  		if(cnt[i] != 0){
69  			w[++n] = cnt[i];
70  			ans[n] = i; 
71  			res[n] = cnt[i];
72  		}
73  	}
74  	init();
75  }

判断题

28.为了避免出现程序崩溃的情况，读入的字符串长度至多为999，且字符的ASCII码值必须小于200（） {{ select(28) }}

  • 正确
  • 错误

29.若输入的所有字符全部相同，则程序只会输出一个字母，不会输出任何数字（） {{ select(29) }}

  • 正确
  • 错误

30.getMin函数中的操作可以被优先队列或set替代，且能够使得程序的时间复杂度更优（） {{ select(30) }}

  • 正确
  • 错误

选择题

31.该代码的时间复杂度为（）？ {{ select(31) }}

  • O(n)O(n)
  • O(n2)O(n^2)
  • O(n3O(n^3
  • O(nlogn)O(nlogn)

32.若代码的输入为CSPCSP，则程序输出的数位的个数之和为（）？ {{ select(32) }}

  • 4
  • 3
  • 6
  • 5

33.若代码的输入为AKAKCSP，则程序输出时哪两个字母的后面的有三个数位（）？ {{ select(33) }}

  • C P
  • S P
  • C S
  • A K

34.若代码的输入为AKAKCSP，则程序输出时A后面的数字为（）？ {{ select(34) }}

  • 10
  • 01
  • 101
  • 111

三、完善程序

（1）（树的染色） 给一棵至多包含2e5个点的无根树，初始每个点都是白色的，你每次可以选择一个白点变成黑色。第一次可以任选，之后每次选择的白点都必须和至少一个黑点相邻。选择一个白点变黑可以得到的收益是这个白点所在的连通块大小，当树的所有点都全部变黑时结束。请问你最多可以获得多少收益？ image 例如本图的最大收益为36，每次选点分别为[8,9,4,1,2,3,5,6,7]，每一步所得收益为[9,8,6,5,4,1,1,1,1]，求和得到36。注意：第一次选8号点，第二次选7号点是非法的，因为第二次选的点没有和一个黑点相邻。当然，[8,9,7,4,1,2,6,5,3]也是一种合法且收益最大的选择。

提示：我们令第一个选择的点为树根，不难发现，当根节点确定时，整棵树的选择及收益都确定了。所以此题难点在于如何寻找第一个点。考虑换根dp，设f[i]为以i为根的收益，我们通过一个f[i]的值来推得以其他点为根的收益。试完成代码。

01  #include <bits/stdc++.h>
02  using namespace std;
03  #define ll long long
04  const int maxn = 2e5 + 5;
05  vector<int>G[maxn];
06  ll sz[maxn], dp1[maxn], dp2[maxn], n, ans = 0;
07  long long dfs(int now, int pre){
08  	sz[now] = 1;
09  	for(int i = 0; i < G[now].size(); i++){
10  		int nxt = G[now][i];
11  		if(nxt == pre)	continue;
12  		sz[now] += dfs(nxt, now);
13  		**1**; 
14  	}
15  	dp1[now] += sz[now];
16  	return sz[now];
17  }
18  void dfs2(int now, int pre){
19  	**2**;
20  	for(int i = 0; i < G[now].size(); i++){
21  		int nxt = G[now][i];
22  		if(nxt == pre)	continue;
23  		dp2[nxt] = max(dp2[nxt], **3**);
24  		dfs2(nxt, now);
25  	}
26  	ans = max(ans, dp2[now]);
27  }
28  int main(){
29  	cin >> n;
30  	for(int i = 1; i < n; i++){
31  		int a, b;
32  		cin >> a >> b;
33  		G[a].push_back(b);
34  		G[b].push_back(a);
35  	}
36  	**4**;
37  	cout << ans << endl;
38  }

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

  • dp1[now]=max(dp1[now],dp1[nxt])
  • dp1[now]+=dp1[nxt]
  • dp1[now]+=sz[nxt]
  • dp1[now]=max(dp1[now],sz[nxt])

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

  • dp2[now]=1
  • dp2[now]=dp1[now]
  • dp2[now]=sz[now]
  • dp2[now]=max(dp1[now],dp2[now])

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

  • dp2[now]+n-sz[nxt]-sz[nxt]
  • dp2[now]+n-sz[nxt]-sz[now]
  • dp2[now]+n-sz[now]-sz[now]
  • dp2[now]+sz[nxt]+sz[now]

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

  • dfs2(1,1);dfs(1,1);
  • dsf2(1,n);dfs(1,1);
  • dfs(1,1);dfs2(1,n);
  • dfs(1,1);dfs(1,1);

（2）（入度） 给定n个点和m条无向边，每条边有一个价值viv_i，你可以任选一些边并给这些边定向，使得每个点的入度均为1。问是否能够做到，若能，则输出所选边的最大权值和；否则输出impossible。（新图中不能出现二元环）

思路：将所有边排序，然后逐个添加，用并查集维护添加边之后是否有某个点不得不出现两条入边的情况。

01  #include <bits/stdc++.h>
02  using namespace std;
03  struct node{
04  	int u, v, val;
05  };
06  bool cmp(node a, node b){
07  	return **1**;
08  }
09  const int maxn = 100005;
10  node a[maxn];
11  int f[maxn], flag[maxn];
12  int Find(int x){
13  	return f[x] == x ? x : f[x] = Find(f[x]);
14  }
15  void Union(int x, int y){
16  	int fx = Find(x), fy = Find(y);
17  	f[fx] = fy;
18  	**2**;
19  }
20  int main(){
21  	int n, m, t;
22  	cin >> t;
23  	while(t--){
24  		long long cnt = 0, ans = 0; // cnt 表示总共插入了多少个关系
25  		cin >> n >> m;
26  		for(int i = 1; i <= n; i++){
27  			f[i] = i;
28  			flag[i] = 1; // flag 为 1 表示此点所在的集合没有环，否则说明有环
29  		}
30  		for(int i = 1; i <= m; i++)
31  			cin >> a[i].u >> a[i].v >> a[i].val;
32  		sort(a+1, a+1+m, cmp);
33  		for(int i = 1; i <= m; i++){
34  			int x = a[i].u, y = a[i].v;
35  			int fx = Find(x), fy = Find(y);
36  			if(fx == fy && **3**){
37  				**4**;
38  				cnt++;
39  				ans += a[i].val;
40  			}else if(fx != fy && **5**){
41  				Union(fx, fy);
42  				cnt++;
43  				ans += a[i].val;
44  			}
45  		}
46  		if(**6**){
47  			cout << ans << endl;
48  		}else{
49  			cout << "impossible" << endl;
50  		}
51  	}
52  }

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

  • a.u<b.u
  • a.u>b.u
  • a.val>b.val
  • a.val<b.val

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

  • flag[fx] = flag[fy]
  • flag[fx] &= flag[fy]
  • flag[fx] ^= flag[fy]
  • flag[fx] |= flag[fy]

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

  • flag[fx]==1
  • flag[fx]==0
  • cnt==n
  • cnt != n

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

  • flag[fx]=1
  • flag[fx]=0
  • f[fx]=fy
  • Union(fx,fy)

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

  • (flag[fx] || flag[fy])
  • flag[fx] && flag[fy]
  • flag[fx] == 0 && flag[fy] == 0
  • (flag[fx] ^ flag[fy])

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

  • cnt==n
  • cnt==n/2
  • flag[n]==1
  • flag[n]==0

CSP-S初赛模拟2

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