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

1. 以下哪个操作系统版本不属于Linux操作系统？（ ） {{ select(1) }}

• Ubuntu
• CentOS
• RedHat
• iOS

2. 对于已经排好序的数列，以下排序算法最快的是（ ）。 {{ select(2) }}

• 插入排序
• 基数排序
• 选择排序
• 快速排序

3. 以下哪个排序从顺序存储改为链式存储时间复杂度会增加？（ ） {{ select(3) }}

• 冒泡排序
• 插入排序
• 希尔排序
• 堆排序

4. 一个有54个结点（根结点深度为1）的完全四叉树，按前序遍历的顺序给结点从1开始编号，则第30号结点的父结点是第（ ）号。 {{ select(4) }}

• 5
• 6
• 7
• 8

5. 有5枚硬币，第i枚硬币有$\frac{p_{i}}{q_{i}}$的概率抛出正面（剩余概率出现反面）。这些硬币抛完后，正面数量超过反面数量的概率是多少？假设$p_{1}=3$，$q_{1}=5$，$p_{2}=1$，$q_{2}=7$，$p_{3}=1$，$q_{3}=1$，$p_{4}=0$，$q_{4}=1$，$p_{5}=4$，$q_{5}=6$。（ ） {{ select(5) }}

• $\frac{1}{35}$
• $\frac{13}{35}$
• $\frac{7}{15}$
• $\frac{8}{21}$

6. 对二叉树T来说，$L(T)$表示T的根的左子树，$R(T)$表示T的根的右子树。二叉树T与二叉树S的大小关系定义如下：
   • 首先，结点数少的二叉树更小。
   • 其次，若结点数相同，则比较$L(S)$与$L(T)$，左子树更小的二叉树更小。
   • 若左子树也一样大，则比较$R(S)$与$R(T)$，右子树更小的二叉树更小。

二叉树T的中序序列定义如下： - 先输出$L(T)$的中序序列，并外加一层括号，若$L(T)$为空则跳过这步。 - 再输出一个*。 - 最后输出$R(T)$的中序序列，并外加一层括号，若$R(T)$为空则跳过这步。

将所有二叉树按照上述规则从小到大排序，第10小的二叉树的中序序列是什么？（ ） {{ select(6) }}

• $(*)$$(*)$
• $(*)$*$(*)$
• $*\left(\left(\left(^{*}\right)^{*}\right)^{*}\right)$
• $\left(^{*}\left(^{*}\right)\right)^{*}\left(^{*}\right)$

7. 下述哪个关于欧拉图和哈密顿图的说法正确？（ ） {{ select(7) }}

• 一张图不能同时称为欧拉图和哈密顿图
• 欧拉图不一定含有欧拉回路
• 只有有向图拥有欧拉回路
• 无向连通图G是欧拉图，当且仅当G有零个、一个或两个奇数度的结点

8. 老师现在需要给3名学生分配25颗糖果，要求分给这3名学生分别不少于1颗、2颗、3颗糖果，问一共有多少种分法？（ ） {{ select(8) }}

• 120
• 150
• 210
• 231

9. 在双向链表中定位删除一个元素的平均复杂度为（ ）。 {{ select(9) }}

• $O(1)$
• $O(n)$
• $O(log n)$
• $O(n log n)$

10. G是一个非连通简单无向图，共有28条边，则该图至少有（ ）个顶点。 {{ select(10) }}

• 10
• 9
• 8
• 7

11. 堆排序建堆最快所需要的时间复杂度是（ ）。 {{ select(11) }}

• $O(1)$
• $O(n log n)$
• $O(log n)$
• $O(n)$

12. 学校里有4个盒子，第1个盒子有3朵花，第2个盒子有3朵花，第3个盒子有3朵花，第4个盒子有6朵花。同一个盒子内花的颜色相同，不同盒子内的花颜色不同。现要从中选出4朵花组成一束花，共有多少种方案？若两束花中相同颜色的花的数量都相同，则认为方案相同。（ ） {{ select(12) }}

• 33
• 25
• 30
• 27

13. 树状数组是解决区间问题常用的数据结构，其原理是使用C数组去求A数组的前缀和。如下图所示：$C[1]=A[1]$，$C[2]=C[1]+A[2]$，$C[4]=C[2]+C[3]+A[4]$。现定义概念组成值和被组成值，例如$C[2]=C[1]+A[2]$，那么$C[1]$、$A[2]$都是$C[2]$的组成值，反过来说$C[2]$就是它俩的被组成值。可以发现，每一项C或者每一项A都最多成为别人的组成值一次。现请问$C[11]$的被组成值是多少？（ ）

{{ select(13) }}

• 112
• 113
• 111
• 127

14. 下图的拓扑序列结果有多少种？（ ）

{{ select(14) }}

• 1
• 7
• 6
• 9

15. 现有4枚硬币，甲乙两人轮流给硬币未涂色的一面涂上颜色（红或者黑），当8次涂色完成后，所有硬币被全部抛出。如果红色面向上更多则甲胜，否则乙胜；如果两种颜色面向上的数量相等，则没有获胜方。如果甲乙两人均采取最优策略使得各自获胜的概率最大，则甲获胜的概率为（ ）。 {{ select(15) }}

• $\frac{5}{16}$
• $\frac{3}{8}$
• $\frac{3}{16}$
• $\frac{1}{2}$

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填x；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

01 #include <iostream>
02 using namespace std;
03 
04 typedef long long ll;
05 
06 const int N = 25, mod = 1e9 + 7;
07 
08 ll a[N];
09 
10 ll cal(ll a, ll b) {
11     if (a < b) return 0;
12     ll x = 1;
13     for (ll i = a; i > a - b; i--) {
14         x *= i;
15         x %= mod;
16     }
17     return x;
18 }
19 
20 ll qmi(ll a, ll b) {
21     ll s = 1;
22     while (b) {
23         if (b & 1) s = s * a % mod;
24         a = a * a % mod;
25         b >>= 1;
26     }
27     return s;
28 }
29 
30 int main() {
31     int n; ll m;
32     cin >> n >> m;
33     for (int i = 0; i < n; i++) {
34         cin >> a[i];
35     }
36 
37     ll s = 1;
38     for (int i = 1; i <= n - 1; i++) {
39         s = s * i % mod;
40     }
41     s = qmi(s, mod - 2);
42 
43     ll ans = 0;
44     for (int i = 0; i < (1 << n); i++) {
45         ll h = n + m - 1; int sign = 1;
46         for (int j = 0; j < n; j++) {
47             if (i & (1 << j)) {
48                 h -= a[j] + 1;
49                 sign = ~sign + 1;
50             }
51         }
52         h = cal(h, n - 1);
53         ans += h * s * sign % mod;
54         ans %= mod;
55     }
56 
57     cout << (ans % mod + mod) % mod << endl;
58     return 0;
59 }

■ 判断题 16. 将第39行改成s *= i % mod，结果不会改变。（ ） {{ select(16) }}

• 正确
• 错误

17. 将第49行改成sign = 1 - sign，结果不会改变。（ ） {{ select(17) }}

• 正确
• 错误

18. 在不考虑mod的情况下，当n固定时，增大m，最后输出的值一定增大。（ ） {{ select(18) }}

• 正确
• 错误

19. 该程序运用的思想是容斥思想。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题 20. 当输入4 4 3 3 3 6时，程序输出（ ）。 {{ select(20) }}

• 30
• 31
• 32
• 33

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

• $O(n log n)$
• $O\left(2^{n} n\right)$
• $O\left(2^{n} log n\right)$
• $O\left(2^{n}(n + log n)\right)$

(2)

01 #include <iostream>
02 using namespace std;
03 
04 int phi[40005];
05 
06 int get(int n) {
07     int sum = n;
08     for (int i = 2; i < n; i++) {
09         if (n % i == 0) {
10             sum -= sum / i;
11             while (n % i == 0) n /= i;
12         }
13     }
14     if (n > 1) sum -= sum / n;
15     return sum;
16 }
17 
18 int main() {
19     int n;
20     scanf("%d", &n);
21     if (n == 1)
22         return 0;
23 
24     for (int i = 2; i <= n; i++)
25         phi[i] = i;
26 
27     for (int i = 2; i <= n; i++) {
28         if (phi[i] == i) {
29             for (int j = i; j <= n; j += i)
30                 phi[j] = phi[j] / i * (i - 1);
31         }
32     }
33     int ans = 0;
34     for (int i = 1; i < n; i++) ans += phi[i];
35 
36     int ans2 = 0;
37     for (int i = 2; i <= n - 1; i++) ans2 += get(i);
38 
39     printf("%d %d", ans * 2 + 1, ans2 * 2 + 3);
40     return 0;
41 }

■ 判断题 22. 求解phi数组的算法的时间复杂度为$O(n log n)$。（ ） {{ select(22) }}

• 正确
• 错误

23. 将第8行代码改成for (int i = 2; i * i <= n; i++)不会导致答案错误。（ ） {{ select(23) }}

• 正确
• 错误

24. （3分）最后输出的两个值总是相等。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题 25. 求解ans2值的算法的时间复杂度为（ ）。 {{ select(25) }}

• $O\left(n^{2}\right)$
• $O\left(n^{2} \sqrt{n}\right)$
• $O\left(n^{2} log n\right)$
• $O(n log n)$

26. 若输入20，程序输出（ ）。 {{ select(26) }}

• 241 241
• 239 241
• 255 257
• 205 205

27. 当输入35时，phi[36]与get(36)分别等于（ ）。 {{ select(27) }}

• 12 12
• 0 0
• 11 12
• 0 12

(3)

01 #include <iostream>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05 #define MOD 1000000007
06 char s[1200000];
07 int nt[1200000];
08 int jp[21][1200000];
09 
10 int main() {
11     scanf("%s", s + 1);
12     nt[1] = 0;
13     int l = strlen(s + 1);
14     for (int i = 2; i <= l; ++i) {
15         int j = nt[i - 1];
16         while (j && s[i] != s[j + 1]) j = nt[j];
17         if (s[i] == s[j + 1]) nt[i] = j + 1;
18         else nt[i] = 0;
19         jp[0][i] = nt[i];
20     }
21     for (int j = 1; j < 20; ++j)
22         for (int i = 1; i <= l; ++i)
23             jp[j][i] = jp[j - 1][jp[j - 1][i]];
24     int ans = 1;
25     for (int i = 2; i <= l; ++i) {
26         int tt = i;
27         for (int j = 19; j >= 0; --j)
28             if (jp[j][tt] * 2 > i) tt = jp[j][tt];
29         int gg = 0;
30         for (int j = 19; j >= 0; --j)
31             if (jp[j][tt]) { gg += 1 << j; tt = jp[j][tt]; }
32         ans = 1LL * ans * (gg + 1) % MOD;
33     }
34     printf("%d\n", ans);
35     return 0;
36 }

■ 判断题 28. （3分）当输入的字符串为abcaabcaab时，nt[10]为5。（ ） {{ select(28) }}

• 正确
• 错误

29. 当输入的字符串为abcaabcaab时，第16行中的j = nt[j]一共执行1次。（ ） {{ select(29) }}

• 正确
• 错误

30. 该程序最后的输出结果可能为0。（ ） {{ select(30) }}

• 正确
• 错误

■ 选择题 31. 当输入为aaaaa时，程序的输出为（ ）。 {{ select(31) }}

• 12
• 24
• 36
• 48

32. （4分）若不考虑% MOD，字符串长度至少为（ ），程序的输出大于100。 {{ select(32) }}

• 5
• 6
• 7
• 8

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

(1) 一共有n个数，第i个数(x_{i})可以取([a_{i}, b_{i}])中的任意值。设(S = \sum x_{i}^{2})，求S的种类数。(1 ≤ n, a_{i}, b_{i} ≤ 100)。考虑极限情况下S最大为100000。DP解题。题目时限1s，空间限制为256MB。

01 #include <bits/stdc++.h>
02 #define maxn 1000005
03 using namespace std;
04 bitset<maxn> bit1, bit2;
05 int a[105], b[105];
06 
07 int main() {
08     int n;
09     scanf("%d", &n);
10     for (int i = 1; i <= n; i++) {
11         scanf("%d%d", &a[i], &b[i]);
12     }
13     for (int i = 1; i <= n; i++) {
14         int l = a[i], r = b[i];
15         for (int j = l; j <= r; j++) {
16             if (i == 1)
17                 ①;
18             else
19                 ②;
20         }
21         if (i == 1)
22             bit2 = bit1;
23         bit1 = bit2;
24         ③;
25     }
26     printf("%d\n", ④);
27 }

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

• bit1.set(j * j)
• bit2.set(j * j)
• bit1.set(i * i)
• bit2.set(i * i)

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

• bit2 = bit1 << (j * j)
• bit2 += bit1 << (j * j)
• bit2 |= bit1 << (j * j)
• bit2 ^= bit1 << (j * j)

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

• bit1.reset()
• bit2.reset()
• bit2.set(0)
• bit1.set()

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

• bit1
• bit2.count()
• bit1.count()
• ~bit1.count()

(2) 有n个人，每个人的空闲时间为([a_{i}, b_{i}])，现需要将n个人分至k个组别中。每个组的成员能一起玩的时间是所有人空闲时间的交集。现希望知道怎么分组才能使得组成员一起玩的时间总和最大。需要注意的是，每个组一起玩的时间至少要大于一分钟，每个组的成员至少为1位。

01 #include <iostream>
02 #include <cstring>
03 #include <algorithm>
04 #include <map>
05 #include <vector>
06 using namespace std;
07 
08 const int N = 5e3 + 10;
09 int n, k;
10 struct node {
11     int l, r;
12     bool operator<(const node& p) const {
13         if (l == p.l) return r > p.r;
14         return l < p.l;
15     }
16 } a[N], b[N];
17 
18 int seg[N];
19 int dp[N][N]; // 前i个数用了j个片段
20 int q[N][N], tail[N], head[N];
21 
22 int main() {
23     cin >> n >> k;
24     for (int i = 1; i <= n; i++) {
25         cin >> a[i].l >> a[i].r;
26     }
27 
28     sort(a + 1, a + n + 1);
29 
30     int cnt = 0, tot = 1;
31     int maxr = 0x3f3f3f3f;
32     for (int i = n; i >= 1; i--) {
33         if (maxr <= a[i].r) {
34             seg[tot++] = a[i].r - a[i].l;
35         } else {
36             b[++cnt] = a[i];
37             ①;
38         }
39     }
40     memset(dp, -0x3f, sizeof dp);
41     sort(b + 1, b + cnt + 1);
42     ②;
43 
44     dp[0][0] = 0;
45     for (int i = 1; i <= k; i++) tail[i] = -1;
46     for (int i = 1; i <= cnt; i++) {
47         for (int l = k; l >= 1; l--) {
48             while (tail[l] >= head[l] && dp[q[l][tail[l]] - 1][l - 1] + ③ <= dp[i - 1][l - 1] + b[i].r - b[i].l) {
49                 --tail[l];
50             }
51             q[l][++tail[l]] = i;
52             while (④ && head[l] <= tail[l]) {
53                 ++head[l];
54             }
55             dp[i][l] = max(dp[i][l], dp[q[l][head[l]] - 1][l - 1] + ⑤);
56         }
57     }
58 
59     int sum = 0;
60     int maxn = dp[cnt][k];
61     for (int i = 1; i < tot && i <= k; i++) {
62         sum += seg[i];
63         maxn = max(maxn, ⑥);
64     }
65 
66     if (maxn > 0) cout << maxn << endl;
67     else cout << 0 << endl;
68 
69     return 0;
70 }

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

• maxr = a[i].l
• seg[++tot] = maxr - a[i].l
• maxr = a[i].r
• --tot

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

• sort(seg + 1, seg + tot, greater<int>())
• sort(seg + 1, seg + tot + 1, less<int>())
• sort(seg + 1, seg + tot + 1, greater<int>())
• sort(seg, seg + tot, less<int>())

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

• dp[i - 1][l - 1] + b[i].r
• dp[i - 1][l - 1] + b[i].l
• dp[i - 1][l - 1] + b[i - 1].r
• dp[i - 1][l - 1] + b[i - 1].l

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

• b[q[l - 1][head[l - 1]]].r <= b[i].l
• b[q[l - 1][tail[l - 1]]].r <= b[i].l
• b[q[l][tail[l]]].r <= b[i].l
• b[q[l][head[l]]].r <= b[i].l

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

• b[q[l][head[l]]].l - b[i].l
• b[q[l - 1][head[l - 1]]].r - b[i - 1].l
• b[q[l - 1][head[l - 1]]].r - b[i].l
• b[q[l][head[l]]].r - b[i].l

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

• sum + dp[cnt][k]
• sum + dp[cnt][k - i]
• sum + dp[k - i][cnt]
• sum + dp[i][cnt]

---