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

一、单项选择题(共 15 题，每题2分，共计 30 分；每题有且仅有一个正确选项)

1. 下列设备中，属于 $\text{OSI}$ 七层模型中数据链路层的是( )。 {{ select(1) }}

• 以太网线
• 路由器
• 交换机
• 光猫

2. 在 NOI Linux 终端系统中，下列哪个命令可以将 a.cpp 重命名为 b.cpp?( ) {{ select(2) }}

• mv a.cpp b.cpp
• cp < a.cpp > b.cpp
• rm A.cpp b.cpp
• echo > a.cpp < b.cpp

3. 某算法的执行时间由以下递归式定义：$T(n)=2T(\frac{n}2)+O(n^{\frac{1}{c}})) (c>1)$。该递归式的时间复杂度是( )。 {{ select(3) }}

• $O(n \log n)$
• $O(n^{\frac{1}{c}})$
• $O(n^{\frac1c}\ log⁡n)$
• $O(n)$

4. 以下对数据结构或算法的表述中不恰当的一项是( )。 {{ select(4) }}

• 栈是一种后进先出的数据结构
• 平衡树可以在 $O(n)$ 时间内完成遍历
• 随机访问长度为n的链表中一个元素的期望复杂度是 $O(1)$
• 二叉堆是一棵完全二叉树

5. 执行以下 C++代码后，z的值是( )。 int z=(unsigned long long)(-5)%5 {{ select(5) }}

• 0
• 1
• 2
• 3

6. 一棵大小为 $n$ 的树恰好有两个重心的必要不充分条件是( )。 {{ select(6) }}

• 这棵树有奇数个结点
• 这棵树有偶数个结点
• 这棵树存在两个结点，使得删去它们后剩下的所有连通块的大小不超过 $⌊\frac{n}{2}⌋$
• 这棵树可以完成黑白染色

7. 关于$x,y$ 的整系数方程 $ax+by=d$ 的解，下列说法中正确的是( )。 {{ select(7) }}

• 当且仅当 $d=gcd(a,b)$ 时，该方程存在一组整数解
• 该方程要么有无数个整数解，要么无解
• 若 $x_0,y_0$ 为该方程的一组解，则该方程的通解为 $x=x_0-kb,y=y_0+ka,k∈Z$
• 在使用 exgcd 算法求解上述问题的过程中，若$|a|,|b|≤10^9$，则计算时的中间结果需要使用 long long 保存

8. 有 $8$ 个结点，每个点度数不超过 $3$ 的树最多有( )个叶子结点。 {{ select(8) }}

• 3
• 4
• 5
• 以上答案都不对

9. 以下关于算法复杂度的描述，不正确的是( )。 {{ select(9) }}

• 基于比较的排序复杂度可以低于 $O(n\log ⁡n)$
• 对一个有 $n$ 个顶点、$m$ 条边的带权有向图用 Dijkstra 算法计算单源最短路时，若使用斐波那契堆进行优化，则复杂度为 $O(n \log ⁡n+m)$
• RMO(区间最值查询)问题的最优在线算法时间复杂度是 $O(n \log ⁡n+q)$
• 普通线段树的空间复杂度是 $O(n)$

10. 定义一个数 $x$ 是优美的，当且仅当 $x$ 的二进制表示下 $0$ 比 $1$ 多，问 $0\sim 255$ 中有多少个数是优美的?( )。 {{ select(10) }}

• 64
• 65
• 127
• 128

11. 下图合法的拓扑序数量是( )。

{{ select(11) }}

• 9
• 12
• 8
• 7

12. 定义两个字符串 $A、B$ 的编辑距离如下。 设 $A$ 和 $B$ 是两个字符串，编辑距离指体字符串 $A$ 转换为字符串 $B$ 所需的最少字符操作次数。这里所说的字符操作共有 $3$ 种：

• 删除一个字符;
• 插入一个字符;
• 将一个字符改为另一个字符。

字符串 platelets与planets的编辑距离是( )。 {{ select(12) }}

• 3
• 4
• 5
• 6

13. 现在用如下代码计算 $\frac12((\sum a_i)^2-(\sum a_i))$，其中 $a$ 的下标从 $0$ 开始，长度为 $2^n$，其时间复杂度为( )。

	int Sol(int *a, int n) {
		int sum = 0;
		for(int o = 1; o < (1 << n); o <<= 1) {
			for(int i = 0; i < (1 << n); i += (o << 1)) {
				for(int j = 0; j < o; j++)
					for(int k = 0; k < o; k++)
						sum += a[i + j] * a[i + k + o];
			}
		}
		return sum;
	}

{{ select(13) }}

• $O(4^nn)$
• $O(3^nn^2)$
• $O(4^n)$
• $O(8^n)$

14. 学生需要将编号为 $1,2,3,4,5,…$ 的方块顺次放人盒子中，每次放入方块时,需要保证盒子中其余方块(不包括当前放入的方块)的编号之和为完全平方数。当有 $5$ 个盒子时，最多可以放置( )个方块。 {{ select(14) }}

• 8
• 10
• 12
• 13

15. 甲乙二人各有两枚石头，在一个回合中，一人抛硬币，如果正面朝上，则将一枚石头交给对方，交不出来就输了，如果反面朝上则什么都不做。甲乙二人轮流进行游戏，甲先手，甲获胜的概率是( )。

{{ select(15) }}

• $\frac{4}{7}$
• $\frac{35}{81}$
• $\frac{11}{27}$
• $\frac{37}{81}$

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

(1)

	01	#include <bits/stdc++.h>
	02	using namespace std;
	03	int a[1 << 10], b[1 << 10], c[1 << 10], d[1 << 10], n;
	04	int main() {
	05		scanf("%d", &n);
	06		for(int i = 0; i < (1 << n); i++)
	07			scanf("%d", &a[i]), d[i] = a[i];
	08		for(int s = 0; s < (1 << n); s++)
	09			for(int s2 = 0; s2 < (1 << n); s2++)
	10				if((s & s2) == s2)
	11					b[s] += a[s2];
	12		for(int s = 0; s < (1 << n); s++) {
	13			int s2 = s;
	14			while(s2)
	15				c[s] += a[s2], s2 = (s2 - 1)&s;
	16		}
	17		for(int i = 0; i < n; i++)
	18			for(int s = 0; s < (1 << n); s++)
	19				if((s >> i) & 1)
	20					d[s] += d[s ^ (1 << i)];
	21		for(int i = 0; i < (1 << n); i++)
	22			printf("%d", b[i]);
	23		puts("");
	24		for(int i = 0; i < (1 << n); i++)
	25			printf("%d", c[i]);
	26		puts("");
	27		for(int i = 0; i < (1 << n); i++)
	28			printf("%d", d[i]);
	29		puts("");
	30		return 0;
	31	}

注：输入的 $n$ 满足 $0≤n≤10，1≤a_i≤10^4$。

判断题

16. 输出中的第2行一定与第1行不同。 ( )

{{ select(16) }}

• True
• False

17. 输出中的第3行不一定与第1行相同。 ( )

{{ select(17) }}

• True
• False

18. 把第 14 行中的 s2 改为 s2>=0，程序不会进入死循环。 ( )

{{ select(18) }}

• True
• False

19. (2分)把第17行中的 for(int i=0;i<n;i++) 改成 for(int i= n-1;i>=0;i--) 后，程序的输出结果不变。 ( )

{{ select(19) }}

• True
• False

选择题

20. 当输入为 0 1时，第2行输出结果为( )。

{{ select(20) }}

• 1
• 0
• 2
• -1

21. 当输入为3 1 2 3 4 5 6 7 8时，第2行输出结果为( )。

{{ select(21) }}

• 1 2 3 4 5 6 7 8
• 1 3 4 10 6 11 16 36
• 0 2 3 9 5 10 15 35
• 0 2 3 9 5 13 15 35

(2)

	01	#include <bits/stdc++.h>
	02	using namespace std;
	03	long long a[10000];
	04	int main() {
	05		int n, m, k;
	06		cin >> n >> m >> k;
	07		a[0] = 1;
	08		while(k--) {
	09			long long sum[100] = {};
	10			for(int i = 0; i < n; i++)
	11				for(int j = 0; j < m;j++)
	12					sum[j] = a[i * m + j] += sum[j];
	13			long long S = 0;
	14			for(int i = 0; i < m; i++)
	15				swap(sum[i], S), S += sum[i];
	16			for(int i = 0; i < n; i++)
	17				for(int j = 0; j < m; j++)
	18					a[i * m + j] += sum[j];
	19		}
	20		cout << a[n * m - 1] << endl;
	21	}

注：$n,m,k$ 都是正整数，程序运行中不会发生 long long 溢出。

判断题

22. 当 $n×m≤10 000$ 时，一定不会发生数组越界。 ( )

{{ select(22) }}

• True
• False

23. 删掉第13~18行，输出一定不会增大。( )

{{ select(23) }}

• True
• False

24. (2分)当n,m,k 中任意一个增大而另外两个不变时，输出一定会增大。 ( )

{{ select(24) }}

• True
• False

选择题

25. 当输入为1 2 10 时，输出为( )。

{{ select(25) }}

• 1
• 10
• 55
• 1024

26. 当输入为 20 15 10 时，记输出为X；当输入为 15 20 10 时，记输出为 Y。那么又和 Y 的大小关系为( )。

{{ select(26) }}

• X<Y
• X=Y
• X>Y
• 不能确定

27. 当输入为 100 100 3 时，输出为( )。

{{ select(27) }}

• 49995000
• 50005000
• 50015001
• 50025003

(3)

	01	#include <bits/stdc++.h>
	02	using namespace std;
	03	int foobar(vector<int> A, int k) {
	04		if(A.size() < 5) {
	05			sort(A.begin(), A.end());
	06			return A[k];
	07		}
	08		vector<int> B;
	09		for(int i = 0; i + 4 < A.size(); i += 5) {
	10			sort(A.begin() + i, A.begin() + i + 5);
	11			B.push_back(A[i + 2]);
	12		}
	13		int value = foobar(B, B.size() / 2);
	14		vector<int> left, right;
	15		for(int v ： A) {
	16			if(v < value)left.push_back(v);
	17			if(v > value)right.push_back(v);
	18		}
	19		if(k < left.size())return foobar(left, k);
	20		if(k < A.size() - right.size())return value;
	21		return foobar(right, k - (A.size() - right.size()));
	22	}
	23	int main() {
	24		ios::sync_with_stdio(false), cin.tie(nullptr);
	25		int n, k;
	26		cin >> n >> k;
	27		vector<int>A(n);
	28		for(int i = 0; i < n; i++)cin >> A[i];
	29		cout << foobar(A, k) << endl;
	30	}

注：假设 $0≤k≤n≤10^6$。

判断题

28. 把第13行中的 B.size()/2 改成 A.size()/10，效果不变。 ( )

{{ select(28) }}

• True
• False

29. 把第 16 行中的 v<value 改为 v<=value，不影响程序的正确性。 ( )

{{ select(29) }}

• True
• False

30. 把第20行中的 k<A.size()-right.size() 改成 A.size()-right.size()-k>0，效果不变。( )

{{ select(30) }}

• True
• False

选择题

31. 当输人为6 3 3 1 5 5 2 2时，输出为( )。

{{ select(31) }}

• 1
• 2
• 3
• 5

32. 最坏情况下，该程序的时间复杂度为( )。

{{ select(32) }}

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

33. 假设删掉第10行，最坏情况下该程序的时间复杂度为( )。

{{ select(33) }}

• $O(n\log n)$
• $O(n^{\log_{10}11})$
• $O(n^2)$
• 以上都不对

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

(1)最长超集子序列

给定一个 $0\sim 2^n-1(1≤n≤20)$ 的排列 $P$，定义超集子序列 $s_1,s_2,s_3,…, s_k$ 需要满足 $P_{s_i}\subseteq P_{s_{i+1}}(1\leq i\leq k-1)$，即 $(P_{s_i}|P_{s_{i+1}} )=P_{s_{i+1}}$ ，求出最长超集子序列的长度。

提示：设 $dp_i$ 表示以 $P_i$ 结尾的最长超集子序列的长度，转移为 $dp_i=\max \{dp_i\}+1 (P\subseteq P)$，直接转移复杂度为 $O(3^n)$，无法通过。动态维护辅助数组 $g_{A,B}$ 表示 $\max \{dp_j\}$，其中 $j$ 要满足 $P$ 在二进制表示下的高 $\lfloor \frac{n}{2} \rfloor$ 为$A$、低 $\lfloor \frac{n}{2} \rfloor$ 为 $B$ 的子集,用公式表达为：

$$g_{A,B}=\max \{ dp_j\}(c\subseteq B,P_j=A\times 2^{\lfloor \frac{n}{2} \rfloor}+c)$$

试补全程序。

	01	#include <bits/stdc++.h>
	02	using namespace std;
	03	int n, P[1 << 20], dp[1 << 20], g[1 << 10][1 << 10];
	04	void foobar(int& a, int b) {
	05		if(①)a = b;
	06	}
	07	int main() {
	08		ios::sync_with_stdio(false), cin.tie(nullptr);
	09		cin >> n;
	10		for(int i = 0; i < 1 << n; i++)cin >> P[i];
	11		for(int i = 0; i < 1 << n; i++) {
	12			int A = P[i] >> n / 2, B = P[i] & (②);
	13			for(int subset = A;; --subset& = A) {
	14				foobar(dp[i], g[subset][B] + 1);
	15				if(subset == 0)break;
	16			}
	17			for(int superset = B;; ③) {
	18				foobar(④, dp[i]);
	19				if(superset == ⑤)break;
	20			}
	21		}
	22		int ans = 0;
	23		for(int i = 0; i < 1 << n; i++)foobar(ans, dp[i]);
	24		cout << ans << endl;
	25	}

34. ①处应填( )。

{{ select(34) }}

• a < b
• a > b
• a = b
• a != b

35. ②处应填( )。

{{ select(35) }}

• 1 << n
• (1 << n)-1
• (1 << n)-(1 << n / 2)
• (1 << n / 2)-1

36. ③处应填( )。

{{ select(36) }}

• ++superset &= B
• ++superset |= B
• --superset &= B
• --superset |= B

37. ④处应填( )。

{{ select(37) }}

• g[A][superset] + 1
• g[B][superset] + 1
• g[superset][A] + 1
• g[superset][B] + 1

38. ⑤处应填( )。

{{ select(38) }}

• 0
• (1 << n)-1
• (1 << n)-(1 << n/2)
• (1 << n / 2)-1

(2)有限分数计数

给定正整数 $n(1≤n≤10^7)$，求出有序整数对 $(x,y)$ 的个数,满足 $1≤x,y≤n$，且 $\frac{x}{y}$ 可以表示为十进制有限小数。

提示：$\frac{x}{y}$ 可以表示为十进制有限小数的条件为，先把 $y$ 中所有 $2$ 和 $5$ 的因子去掉得到 $y’$， $\frac{x}{y'}$ 必须整数。我们可以枚举 $y’$，快速算出有多少对 $(x,y)$ 合法。

试补全程序。

	01	#include <bits/stdc++.h>
	02	using namespace std;
	03	int main() {
	04		int n;
	05		cin >> n;
	06		vector<int> num;
	07		for(int A = 1; A <= n; A *= 2)
	08			for(int B = 1;  A * B <= n; ①)
	09				num.push_back(A * B);
	10		②;
	11		long long ans = 0;
	12		for(int i = 1; i <= n; i++)
	13			if(③) {
	14				while(!num.empty() && num.back() > ④)num.pop_back();
	15				ans += ⑤ ;
	16			}
	17		cout << ans << 'n';
	18	}

39. ①处应填( )。

{{ select(39) }}

• B++
• B *= 2
• B *= 5
• B *= 10

40. ②处应填( )。

{{ select(40) }}

• sort(num.begin(),num.end(), less())
• sort(num.begin(),num.end(),greater())
• sort(num.rbegin(),num.rend())
• sort(num.rbegin(),num.rend(),less())

41. ③处应填( )。

{{ select(41) }}

• i % 2 == 0 && i % 5 == 0
• i % 2 == 0 || i % 5 == 0
• i % 2 != 0 && i % 5 != 0
• i % 2 != 0 || i % 5 != 0

42. ④处应填( )。

{{ select(42) }}

• i
• n
• n / i
• n - 1LL * i * i

43. ⑤处应填( )。

{{ select(43) }}

• num.size()
• 1LL * num.size() * i
• num.size() * n / i
• n / i * num.size()