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

1. 16 人参加 1v1 单打比赛，决出冠军。比赛采用双败淘汰制：第 1 轮随机配对，胜者进入胜者组，败者进入败者组。以后每轮在两组内分别配对进行（除非该组只剩 1 人），如在胜者组战败，则降入败者组；在败者组战败则淘汰，在败者组获胜留在败者组（不会升入胜者组）。如此反复进行直到两组都只剩 1 人，再进行最后一场决赛决出冠军。那么总共要进行（ ）场比赛。 {{ select(1) }}

• A. 15
• B. 30
• C. 31
• D. 120

2. 5 个人穿 5 种颜色的衣服坐在 5 种颜色的椅子上，每人一把椅子。要求每个人的衣服颜色和椅子颜色都不相同。两种坐法不同当且仅当至少有 1 个人坐的椅子不同，则总共有（ ）种可能的坐法。 {{ select(2) }}

• A. 5
• B. 32
• C. 44
• D. 120

3. 正整数 $x$ 和 $y$ 的最大公约数 $\gcd(x,y)$ 定义为能同时整除 $x$ 和 $y$ 的最大正整数。例如，$\gcd(12,18)=6$。那么 $\gcd(12345,54321)=$（ ）。 {{ select(3) }}

• A. 3
• B. 5
• C. 7
• D. 15

4. 1 至 100 的整数的乘积末尾有（ ）个连续的 0。 {{ select(4) }}

• A. 100
• B. 50
• C. 24
• D. 12

5. 在三维直角坐标系里任取 $n$ 个整点（坐标都是整数的点），要保证其中一定存在两个点连线的中点也是整点，$n$ 至少是（ ）。 {{ select(5) }}

• A. 2
• B. 3
• C. 7
• D. 9

6. 同时掷出 3 枚完全相同的六面骰子，每枚骰子上有 1 到 6 的数字。将得到的点数排序后，有（ ）种不同的结果。 {{ select(6) }}

• A. 208
• B. 56
• C. 216
• D. 120

7. 5 个有标号的点在没有重边或者自环的情况下，可组成的不同无向图个数为（ ）。 {{ select(7) }}

• A. 10
• B. 1024
• C. 15
• D. 120

8. 若某算法的计算时间表示为递推关系式 $T(n)=9T(n/3)+n$，且 $T(1)=1$，则该算法的时间复杂度是（ ）。 {{ select(8) }}

• A. $O(n)$
• B. $O(2^n)$
• C. $O(n^2)$
• D. $O(n \log n)$

9. 8 位二进制补码中，$10101011$ 表示的数是十进制下的（ ）。 {{ select(9) }}

• A. 43
• B. $-43$
• C. $-85$
• D. $-84$

10. 下列算法中，完全不涉及贪心思想的算法为（ ）。 {{ select(10) }}

• A. Kruskal 算法（最小生成树）
• B. Floyd 算法（多源最短路）
• C. Dijkstra 算法（单源最短路）
• D. Kahn 算法（拓扑排序）

11. 已知 $a=3$，$b=5$，执行 a^=b^=a^=b 后，$a$ 的值为（ ）。 {{ select(11) }}

• A. 3
• B. 5
• C. 6
• D. 0

12. 已知一个栈的入栈顺序为 $1,2,\cdots,n$（$n \ge 3$），第 1 个出栈的是 3，那么第 2 个出栈的数有（ ）种可能。 {{ select(12) }}

• A. $n-1$
• B. $n-2$
• C. $n-3$
• D. $n-4$

13. 一个 $n$ 节点无向图没有重边和自环，它是一棵无根树的必要条件不包括（ ）。 {{ select(13) }}

• A. 连通
• B. 有 $n-1$ 条边
• C. 没有环
• D. 每个点的度数都大于 0

14. Dijkstra 算法中没有涉及（ ）算法思想。 {{ select(14) }}

• A. 贪心法
• B. 动态规划
• C. 二分法
• D. 调整法

15. 将正整数 $n$ 拆成任意多个正整数之和，使这些加数的乘积最大，则加数中不可能出现（ ）。 {{ select(15) }}

• A. 1
• B. 2
• C. 4
• D. 5

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

(1)

 1 #include <iostream>
 2 using namespace std;
 3 const int N = 1009;
 4 int n, q[N], x[N];
 5 int main() {
 6     cin >> n; // 保证输入的数都是正整数，1≤x[i]≤n≤1000
 7     for (int i=1; i<=n; i++) cin >> x[i];
 8     for (int i=1; i<=n; i++) {
 9         for (int j=i; j>=x[i]+1; j--) q[j] = q[j-1];
10         q[x[i]] = i;
11     }
12     for (int i=1; i<=n; i++)
13         cout << q[i] << " ";
14     return 0;
15 }

判断题

16. 如果输出的每个数都不是 0，那么输入的 x[i] 必须互不相同。 {{ select(16) }}

• A. 正确
• B. 错误

17. 输出的 n 个数一定是 1..n 的一个排列（取值在 1..n 范围内且没有重复）。 {{ select(17) }}

• A. 正确
• B. 错误

18. 输出的 n 个数中除了 0 以外，其他数都互不相同。 {{ select(18) }}

• A. 正确
• B. 错误

19. 如果输入的 x[i] 单调不降，则输出也单调不降。 {{ select(19) }}

• A. 正确
• B. 错误

选择题

20. 固定 n，对各种符合输入限制的 x[i] 情况，最好和最坏情况下代码的时间复杂度分别为（ ）。 {{ select(20) }}

• A. $O(n)$，$O(n^2)$
• B. $O(n^2)$，$O(n^2)$
• C. $O(n)$，$O(n)$
• D. $O(n \log n)$，$O(n^2)$

21. 若输入 8 1 1 2 3 1 1 2 3，则输出为（ ）。 {{ select(21) }}

• A. 1 1 2 3 1 1 2 3
• B. 6 7 8 5 2 3 4 1
• C. 1 6 7 8 5 2 3 4
• D. 5 3 4 1 8 6 7 2

(2)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 10009;
 4 int n, cur, nxt[N];
 5 
 6 int main() {
 7     cin >> n; // 保证 n 是 1..10000 范围内的整数
 8     for (int i=1; i<=n; ++i) nxt[i] = i % n+1;
 9     for (cur=1; n>1; --n) {
10         nxt[cur] = nxt[nxt[cur]];
11         cur = nxt[cur];
12     }
13     cout << cur << endl;
14     return 0;
15 }

判断题

22. 程序运行结束后，除了最后的 cur，其他 nxt 的值都为 0。 {{ select(22) }}

• A. 正确
• B. 错误

23. 若将 for 循环内的两句合并为 cur = nxt[cur] = nxt[nxt[cur]];，则运行结果不会改变。 {{ select(23) }}

• A. 正确
• B. 错误

24. 若将 for 循环中的条件 n>1 改为 n>0，则运行结果不会改变。 {{ select(24) }}

• A. 正确
• B. 错误

25. 假如强行输入 n=-1，程序会异常退出。 {{ select(25) }}

• A. 正确
• B. 错误

选择题

26. 如上代码的时间复杂度是（ ）。 {{ select(26) }}

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n\sqrt n)$
• D. $O(n^2)$

27. 若输入 10000，则输出为（ ）。 {{ select(27) }}

• A. 3616
• B. 3617
• C. 3618
• D. 3619

(3)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll x[10009], s[509][10009], n, m;
 5 
 6 int main() {
 7     cin >> n >> m; // 保证 1≤n≤10000, 1≤m≤250000, 1≤x[i]≤1000000
 8     for (ll i=1; i<=n; i++) cin >> x[i];
 9     ll D = max(1LL, (ll)sqrt(m));
10     for (ll d=1; d<=D; d++)
11         for (ll i=1; i<=n; i++)
12             if (i > d) s[d][i] = s[d][i-d] + x[i];
13             else s[d][i] = x[i];
14     for (ll i,d,k; m--; ) {
15         cin >> i >> d >> k; // 保证输入的 1≤i,d,k≤n
16         k = min(k, (n - i) / d + 1);
17         if (d <= D) {
18             if (i > d) cout << s[d][i+(k-1)*d]-s[d][i-d] << endl;
19             else cout << s[d][i+(k-1)*d] << endl;
20         } else {
21             ll sum = 0;
22             for (int j=0; j<k; ++j) sum += x[i+j*d];
23             cout << sum << endl;
24         }
25     }
26     return 0;
27 }

判断题

28. 将所有整数类型 long long 都换成 int，结果不变，因为输入数据都在 int 范围内。 {{ select(28) }}

• A. 正确
• B. 错误

29. 假如 k 没有截断（去掉 k = min(k, (n - i) / d + 1); 这句），但问询的 i,d,k 保证了 $i+(k-1)*d \le 500$，那么程序结果不会改变。 {{ select(29) }}

• A. 正确
• B. 错误

30. 代码占用的内存空间大致为 5MB。 {{ select(30) }}

• A. 正确
• B. 错误

31. 在不影响时间复杂度的情况下，可以把空间复杂度优化到 $O(n+m)$。 {{ select(31) }}

• A. 正确
• B. 错误

选择题

32. 此代码最坏情况下的时间复杂度是（ ）。 {{ select(32) }}

• A. $O(nm)$
• B. $O(n^2)$
• C. $O(n\sqrt m)$
• D. $O(m\sqrt n)$

33. 假如强行将以下某个变量的值输入为负数（其他变量仍为正数），一定会导致数组下标越界的是（ ）。 {{ select(33) }}

• A. n
• B. i
• C. d
• D. k

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

(1)

（整数拆分）输入正整数 $n$，将其拆分为若干（至少 2 个）连续正整数之和，如 $15=4+5+6$，求有几种拆分方案数。加数不计顺序，如 $2+3$ 和 $3+2$ 算同种方案。$1 \le n \le 100000$。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n, ans, sum;
 4 int main() {
 5     cin >> n;
 6     for (int i=1; ① ; ++i) {
 7         for (j=i, ② ; ③ ; j++) sum += j;
 8         if (④) ans++;
 9     }
10     cout << ans << endl;
11     // 该程序的时间复杂度是 ⑤
12     return 0;
13 }

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

• A. n
• B. n/2
• C. (n+1)/2
• D. n/2+1

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

• A. sum=0
• B. sum=i
• C. sum++
• D. sum+=j

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

• A. j<=n
• B. j<n
• C. sum<=n
• D. sum<n

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

• A. sum >= n
• B. sum + j == n
• C. sum == n
• D. j-i >= 2

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

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n\sqrt n)$
• D. $O(n^2)$

(2)

（绝对众数）一个序列中如果某数值的出现次数超过序列长度的一半，则称这个数值为绝对众数。现输入一个序列 $x_1,\cdots,x_n$，保证存在绝对众数，输出这个数是多少。要求空间复杂度为 $O(1)$。

 1 #include <iostream>
 2 using namespace std;
 3 int n, x, s, cnt;
 4 int main() {
 5     cin >> n;
 6     for (int i=1; i<=n; i++) {
 7         cin >> x;
 8         if (①) ②;
 9         if (③) ④;
10         else ⑤;
11     }
12     cout << s << endl;
13     return 0;
14 }

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

• A. cnt > 0
• B. cnt >= 0
• C. cnt == 0
• D. cnt

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

• A. s = cnt
• B. s = x
• C. s = i
• D. s = n

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

• A. x < s
• B. x > s
• C. x == s
• D. x == cnt

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

• A. cnt++
• B. cnt--
• C. cnt = i
• D. cnt = 0

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

• A. cnt++
• B. cnt--
• C. cnt = i
• D. cnt = 0