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

1. 下列设备中，属于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 > b.cpp

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

• $O(n \log n)$
• $O\left(n^{\frac{1}{c}}\right)$
• $O\left(n^{\frac{1}{c}} \log n\right)$
• $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) }}

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

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 \in \mathbb{Z}$
• 在使用cxgcd算法求解上述问题的过程中，若$|a|, |b| \leq 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)$
• RMQ（区间最值查询）问题的最优在线算法时间复杂度是$O(n \log n + q)$
• 普通线段树的空间复杂度是$O(n)$

10. 定义一个数x是优美的，当且仅当x的二进制表示下0比1多，问0~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. 现在用如下代码计算$\frac{1}{2}((\sum a_i)^2 - (\sum a_i^2))$，其中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\left(4^n n\right)$
• $O\left(3^n n^2\right)$
• $O\left(4^n\right)$
• $O\left(8^n\right)$

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}$

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填x；除特殊说明外，判断题每题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     }
18     for (int i = 0; i < n; i++)
19         for (int s = 0; s < (1 << n); s++)
20             if ((s >> i) & 1)
21                 d[s] += d[s ^ (1 << i)];
22     for (int i = 0; i < (1 << n); i++)
23         printf("%d ", b[i]);
24     puts("");
25     for (int i = 0; i < (1 << n); i++)
26         printf("%d ", c[i]);
27     puts("");
28     for (int i = 0; i < (1 << n); i++)
29         printf("%d ", d[i]);
30     puts("");
31     return 0;
32 }

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

■ 判断题 16. 输出中的第2行一定与第1行不同。（ ） {{ select(16) }}

• 正确
• 错误

17. 输出中的第3行不一定与第1行相同。（ ） {{ select(17) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

■ 选择题 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 
05 int main() {
06     int n, m, k;
07     cin >> n >> m >> k;
08     a[0] = 1;
09     while (k--) {
10         long long sum[100] = {};
11         for (int i = 0; i < n; i++)
12             for (int j = 0; j < m; j++)
13                 sum[j] = a[i * m + j] += sum[j];
14         long long s = 0;
15         for (int i = 0; i < m; i++)
16             swap(sum[i], s), s += sum[i];
17         for (int i = 0; i < n; i++)
18             for (int j = 0; j < m; j++)
19                 a[i * m + j] += sum[j];
20     }
21     cout << a[n * m - 1] << endl;
22 }

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

■ 判断题 22. 当$n × m ≤ 10000$时，一定不会发生数组越界。（ ） {{ select(22) }}

• 正确
• 错误

23. 删掉第14~19行，输出一定不会增大。（ ） {{ select(23) }}

• 正确
• 错误

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

• 正确
• 错误

■ 选择题 25. 当输入为1 2 10时，输出为（ ）。 {{ select(25) }}

• 1
• 10
• 55
• 1024

26. 当输入为20 15 10时，记输出为X；当输入为15 20 10时，记输出为Y。那么X和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 
04 int foobar(vector<int> A, int k) {
05     if (A.size() < 5) {
06         sort(A.begin(), A.end());
07         return A[k];
08     }
09     vector<int> B;
10     for (int i = 0; i + 4 < A.size(); i += 5) {
11         sort(A.begin() + i, A.begin() + i + 5);
12         B.push_back(A[i + 2]);
13     }
14     int value = foobar(B, B.size() / 2);
15     vector<int> left, right;
16     for (int v : A) {
17         if (v < value) left.push_back(v);
18         if (v > value) right.push_back(v);
19     }
20     if (k < left.size()) return foobar(left, k);
21     if (k < A.size() - right.size()) return value;
22     return foobar(right, k - (A.size() - right.size()));
23 }
24 
25 int main() {
26     ios::sync_with_stdio(false), cin.tie(nullptr);
27     int n, k;
28     cin >> n >> k;
29     vector<int> A(n);
30     for (int i = 0; i < n; i++) cin >> A[i];
31     cout << foobar(A, k) << endl;
32 }

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

■ 判断题 28. 该程序的功能是求第k小的元素。（ ） {{ select(28) }}

• 正确
• 错误

29. 该程序的最坏时间复杂度优于快速排序。（ ） {{ select(29) }}

• 正确
• 错误

30. 把第21行的k < A.size() - right.size()改为k >= 0，效果不变。（ ） {{ select(30) }}

• 正确
• 错误

■ 选择题

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\left(n^{\log_5 6}\right)$
• $O\left(n^2\right)$

33. 假设删掉第11行，最坏情况下该程序的时间复杂度为（）。 {{ select(33) }}

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

完善程序（单选题，每小题3分，共计30分）

(1) 最长超集子序列

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

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

试补全程序。

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

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

• a < b
• a > b
• a = b
• a \neq 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 = (superset - 1) & B
• superset |= B

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

• g[A][superset]
• g[B][superset]
• g[superset][A]
• g[superset][B]

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 
04 int main() {
05     int n;
06     cin >> n;
07     vector<int> num;
08     for (int A = 1; A <= n; A *= 2)
09         for (int B = 1; A * B <= n; ①)
10             num.push_back(A * B);
11     ②;
12     long long ans = 0;
13     for (int i = 1; i <= n; i++)
14         if (③) {
15             while (!num.empty() && num.back() > ④) num.pop_back();
16             ans += ⑤;
17         }
18     cout << ans << endl;
19 }

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

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

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

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

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
• 1LL * num.size() * (n / i)
• n / i * num.size()

---