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

1. 以下选项中，（ ）不属于Linux操作系统。 {{ select(1) }}

• Debian
• Harmony
• Ubuntu
• Fedora

2. 下面的C++代码构成的是（ ）类型的数据结构。

typedef struct LinkList {
    int value;
    LinkList* lft;
    LinkList* rgt;
} LinkList, LinkNode;
bool ListInit(LinkList*& LL) {
    LL = new LinkNode;
    if (!LL) return false;
    LL->lft = NULL;
    LL->rgt = NULL;
    LL->value = -1;
    return true;
}

{{ select(2) }}

• 双向链表
• 单向链表
• 循环链表
• 双向栈

3. 后缀表达式1 3 4 + 5 * 5 6 7 / -的前缀表达式为（ ）。 {{ select(3) }}

• 1 + 3 4 * 5 - 5 6 / 7
• - * 1 + 3 4 5 / 5 6 7
• - * + 1 3 4 5 / 5 6 7
• - 1 + 3 4 * 5 5 6 / 7

4. 以下选项中属于面向对象的解释型高级语言的是（ ）。 {{ select(4) }}

• C++
• C
• Fortran
• Python

5. 高斯消元法不能用于求解（ ）。 {{ select(5) }}

• 线性方程组
• 逆矩阵
• 第k个质数
• 行列式

6. 以下哪个说法是正确的？（ ） {{ select(6) }}

• 在CSP-J/S初赛中交卷后，考试结束前，可以回考场取遗忘的身份证
• IOI参赛选手可携带已关机的手机并放在自己座位后面的包里
• IOI参赛选手在比赛时间内去厕所的时候可携带手机
• CCF的全称是中国计算机学会

7. 下列关于树的描述中正确的是（ ）。 {{ select(7) }}

• 在含有n个结点的最小生成树中，边数只能是$n-1$条
• 在哈夫曼树中，叶子结点的个数比非叶子结点的个数多1或2
• 完全二叉树一定是二叉排序树
• 在二叉树的后序遍历序列中，若结点u在结点v之前，则u一定是v的祖先

8. 有11个黑球和9个红球，将球依次取出，剩下的球全是一种颜色就结束，最后只剩下红球的概率为（ ）。 {{ select(8) }}

• 5/12
• 2/5
• 1/2
• 9/20

9. 关于图$G=(V, E)$，顶点数为n，边数为m，下列说法中正确的是（ ）。 {{ select(9) }}

• Prim算法用到了二分算法的思想
• Kruskal算法和Prim算法只有一种用到了贪心算法的思想
• 如果使用邻接表来存储图G，并使用优先队列进行优化，Prim算法的时间复杂度可以从$O(n^2)$缩减为$O(m \log n)$
• 基于并查集的Kruskal算法的时间复杂度为$O(m \log n)$

10. 对长度为x的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为（ ）。 {{ select(10) }}

• x/2
• (x+1)/2
• (x-1)/2
• x/3

11. 下列选项中哪个不属于与初等数论有关的定理或者算法？（ ） {{ select(11) }}

• 欧拉定理
• 裴蜀定理
• 中国剩余定理
• 欧拉路

12. 有如下递归代码（假设非负整数$a ≤ b$）：

int fun(int a, int b) {
    while (a > 0) {
        int tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}

最坏情况下程序的时间复杂度为（ ）。 {{ select(12) }}

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

13. 一堆卡片共3234张，若每次取相同的质数张，若干次后刚好取完，不同的取法有A种；若每次取相同的奇数张，若干次后刚好取完，不同的取法有B种。则$A + B =（ ）$。 {{ select(13) }}

• 17
• 16
• 15
• 14

14. 从乘法算式$1×2×3×4×…×26×27$中最少要删掉（ ）个数，才能使得剩下的数的乘积是完全平方数。共有（ ）种不同的删除方法。 {{ select(14) }}

• 4；3
• 5；3
• 5；2
• 4；2

15. A是一个两位数，它的6倍是一个三位数B，如果把B放在A的左边或者右边得到两个不同的五位数，并且这两个五位数的差是一个完全平方数（整数的平方），那么A的所有可能取值之和为（ ）。 {{ select(15) }}

• 135
• 144
• 145
• 146

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 10;
04 
05 priority_queue<int> q1;
06 priority_queue<int, vector<int>, greater<int>> q2;
07 int n, a;
08 int main() {
09     cin >> n;
10     cin >> a;
11     cout << a << " ";
12     q1.push(a);
13     for (int i = 2; i <= n; i++) {
14         cin >> a;
15         if (a > q1.top()) q2.push(a);
16         else q1.push(a);
17         while (abs((int)(q1.size() - q2.size()) > 1)) {
18             if (q1.size() > q2.size()) {
19                 q2.push(q1.top());
20                 q1.pop();
21             } else {
22                 q1.push(q2.top());
23                 q2.pop();
24             }
25         }
26         if (i % 2) {
27             cout << (q1.size() > q2.size() ? q1.top() : q2.top()) << " ";
28         }
29     }
30     return 0;
31 }

■ 判断题

16. 若程序输入5 3 2 1 4 5，则最终输出为3 2 3。（ ） {{ select(16) }}

• 正确
• 错误

17. （2分）若将第15行中的>改为>=，程序输出一定不会改变。（ ） {{ select(17) }}

• 正确
• 错误

18. 若将头文件#include <bits/stdc++.h>改成#include <stdio.h>，程序仍能正常运行。（ ） {{ select(18) }}

• 正确
• 错误

■ 选择题

19. 若输入4 3 5 2 7，则输出是什么？（ ） {{ select(19) }}

• 3 3 3 3
• 3 3
• 3 3 5
• 3 5

20. （4分）若将第26行改为i % 2 == 0，则输入4 3 5 2 7时，输出是什么？（ ） {{ select(20) }}

• 3 3
• 3 5 3
• 3 2 3
• 3 5 5

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define INF 0x3f3f3f3f
04 const int N = 1e2 + 10, M = 5e3 + 10;
05 
06 int n, m;
07 int a[N][N];
08 int d[N], f[N];
09 void p() {
10     for (int i = 1; i <= n; i++) {
11         f[i] = 0;
12         d[i] = INF;
13     }
14     f[1] = 0;
15     d[1] = 0;
16     for (int i = 1; i < n; i++) {
17         int mn = INF;
18         int t;
19         for (int j = 1; j <= n; j++) {
20             if (!(f[j] ^ 1) && d[j] < mn) {
21                 t = j;
22                 mn = d[j];
23             }
24         }
25         f[t] = 1;
26         for (int j = 1; j <= n; j++) {
27             if (a[t][j] + 1 == 0) continue;
28             d[j] = min(d[j], mn + a[t][j]);
29         }
30     }
31 }
32 int dd[N];
33 int dfs(int u) {
34     if (u == 1) return 0;
35     for (int i = 1; i <= n; i++) {
36         if (a[i][u] == -1) continue;
37         if (a[i][u] + d[i] == d[u]) {
38             a[i][u] <<= 1;
39             a[u][i] <<= 1;
40             for (int j = 1; j <= n; j++) {
41                 f[j] = 0;
42                 dd[j] = INF;
43             }
44             f[1] = 0;
45             dd[1] = 0;
46             for (int j = 1; j <= n; j++) {
47                 int mn = INF;
48                 int id;
49                 for (int k = 1; k <= n; k++) {
50                     if ((f[k] ^ 1) || dd[k] >= mn) continue;
51                     id = k;
52                     mn = dd[k];
53                 }
54                 f[id] ^= 1;
55                 if (id == n) break;
56                 for (int k = 1; k <= n; k++) {
57                     if (a[id][k] <= -1) continue;
58                     dd[k] = min(dd[k], mn + a[id][k]);
59                 }
60             }
61             int tmp = dd[n];
62             a[i][u] >>= 1;
63             a[u][i] >>= 1;
64             return max(tmp, dfs(i));
65         }
66     }
67     return 0;
68 }
69 int main() {
70     memset(a, -1, sizeof a);
71     cin >> n >> m;
72     for (int i = 0; i < m; i++) {
73         int u, v, w;
74         cin >> u >> v >> w;
75         a[u][v] = a[v][u] = w;
76     }
77     p();
78     int ans = d[n];
79     cout << dfs(n) - ans;
80     return 0;
81 }

程序输入为一张带权无向连通图且没有重边，其中$n(n ≤ 100)$为顶点数，m为边数，边权不超过1000000，完成下面的判断题和选择题。

■ 判断题

21. 函数p的时间复杂度为$O(n^2)$。（ ） {{ select(21) }}

• 正确
• 错误

22. 第70行中a数组的初始值为$2^{31}-1$。（ ） {{ select(22) }}

• 正确
• 错误

23. 最终的输出值可能为负。（ ） {{ select(23) }}

• 正确
• 错误

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

• 正确
• 错误

■ 选择题

25. 若将第14行改为f[1] = 1，则按照第24题的输入，最终的输出为（ ）。 {{ select(25) }}

• 2
• -6
• 1061109567
• -1061109567

26. 若将第38行和第39行中的<<= 1改为*= 3，第62行和第63行中的>>= 1改为/= 3，则按照第24题的输入，最终的输出为（ ）。 {{ select(26) }}

• 6
• 8
• 2
• 1

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e2 + 10;
04 
05 int n, m;
06 int fx[] = {-1, 1, 0, 0};
07 int fy[] = {0, 0, -1, 1};
08 vector<pair<int, int>> f[N][N];
09 int vis[N][N], a[N][N];
10 int main() {
11     cin >> n >> m;
12     for (int i = 0; i < m; i++) {
13         int x, y, xx, yy;
14         cin >> x >> y >> xx >> yy;
15         f[x][y].push_back({xx, yy});
16     }
17     int ans = 1;
18     a[1][1] = 1;
19     queue<pair<int, int>> q;
20     q.push({1, 1});
21     vis[1][1] = 1;
22     while (!q.empty()) {
23         pair<int, int> u = q.front();
24         q.pop();
25         for (int i = 0; i < 4; i++) {
26             int xx = u.first + fx[i], yy = u.second + fy[i];
27             if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
28             if (vis[xx][yy]) continue;
29             vis[xx][yy] = 1;
30             q.push({xx, yy});
31         }
32         for (int i = 0; i < f[u.first][u.second].size(); i++) {
33             pair<int, int> v = f[u.first][u.second][i];
34             if (vis[v.first][v.second]) continue;
35             if (a[v.first][v.second] == 0) ans++;
36             else continue;
37             a```cpp
[v.first][v.second] = 1;
38             for (int j = 0; j < 4; j++) {
39                 int xx = v.first + fx[j], yy = v.second + fy[j];
40                 if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
41                 if (vis[xx][yy]) {
42                     q.push({v.first, v.second});
43                     vis[v.first][v.second] = 1;
44                     break;
45                 }
46             }
47         }
48     }
49     cout << ans;
50     return 0;
51 }

假设程序的输入是一个$N×N$的网格，$N$不超过100，$M$是对网格的$M$种相同的约束，$M$不超过200000。

■ 判断题

27. 若将第27行中的if语句改为if (vis[xx][yy] || !a[xx][yy])，输出结果不变。（ ） {{ select(27) }}

• 正确
• 错误

28. 若输入为3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1，则输出为5。（ ） {{ select(28) }}

• 正确
• 错误

■ 选择题

29. 该算法的时间复杂度为（ ）。 {{ select(29) }}

• $O\left(N^2\right)$
• $O(M)$
• $O(N + M)$
• $O\left(N^2 + M\right)$

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

• 6
• 7
• 8
• 9

31. 若将第25行到第31行注释掉，输入与第30题相同的数据，则输出为（ ）。 {{ select(31) }}

• 6
• 7
• 8
• 9

32. （4分）如果不在第35行进行ans++，而是在第29行和第43行进行ans++，然后输入与第30题相同的数据，则输出为（ ）。 {{ select(32) }}

• 6
• 7
• 8
• 9

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

(1) 题目描述： 小J有一个长度为$n(1 ≤ n ≤ 1000)$的a数组，小P有一个长度为$m(1 ≤ m ≤ 1000)$的b数组。现在小J与小P要分别从各自的数组中选出$k(1 ≤ k ≤ 10)$个数字，小J选出的数字中最大的数字与小P选出的数字中最大的数字进行比较，小J选出的数字中次大的数字与小P选出的次大的数字进行比较，以此类推。如果小J选出的每个数字都比相对应的小P选出的数字大的话，小J就获得了胜利。请求出在所有选出k个数字的情况中，有多少种情况小J可以获胜，输出方案数对1000000009取模的结果。

01 #include <bits/stdc++.h>
02 #define ll long long
03 using namespace std;
04 const int N = 1e3 + 10;
05 const ll mod = 1e9 + 9;
06 
07 int n, m, k;
08 int a[N], b[N];
09 ll f[2][N][20];
10 int main() {
11     cin >> n >> m >> k;
12     for (int i = 1; i <= n; i++) cin >> a[i];
13     for (int i = 1; i <= m; i++) cin >> b[i];
14     sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + m);
15     for (int i = 0; i <= 1; i++) {
16         for (int j = 0; j <= m; j++) {
17             f[i][j][0] = 1;
18         }
19     }
20     for (int i = 1; i <= n; i++) {
21         int id = i % 2;
22         for (int j = 1; j <= m; j++) {
23             for (int t = 1; t <= k; t++) {
24                 ①;
25                 ②;
26                 ③;
27                 if (a[i] > b[j]) {
28                     ④;
29                 }
30             }
31         }
32     }
33     cout << ⑤;
34     return 0;
35 }

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

• f[i][j][t] = 0
• f[i][j][t] = f[i - 1][j - 1][t - 1]
• f[id][j][t] = 0
• f[id][j][t] = f[id - 1][j - 1][t - 1]

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

• f[id][j][t] += f[id - 1][j][t]
• f[id][j][t] = (f[id][j][t] + f[id - 1][j][t]) % mod
• f[id][j][t] += f[id ^ 1][j][t]
• f[id][j][t] = (f[id][j][t] + f[id ^ 1][j][t]) % mod

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

• f[id][j][t] = (f[id][j][t] - f[id ^ 1][j - 1][t] + mod) % mod
• f[id][j][t] = (f[id][j][t] - f[id ^ 1][j - 1][t - 1] + mod) % mod
• f[id][j][t] = (f[id][j][t] - f[id ^ 1][j - 1][t - 1] + mod) % mod
• f[id][j][t] = (f[id][j][t] - f[id ^ 1][j - 1][t] + mod) % mod

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

• f[id][j][t] = (f[id][j][t] + 1) % mod
• f[id][j][t] = (f[id][j][t] + f[id ^ 1][j - 1][t]) % mod
• f[id][j][t] = (f[id][j][t] + f[id ^ 1][j - 1][t - 1] + 1) % mod
• f[id][j][t] = (f[id][j][t] + f[id ^ 1][j - 1][t - 1]) % mod

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

• f[n ^ 1][n][k]
• f[n ^ 1][m][k]
• f[n ^ 1][m][k]
• f[n][m][k]

(2) 题目描述： 小J想要制造$k(1 ≤ k ≤ 100000)$台机器人，每台机器人有$N(1 ≤ N ≤ 100000)$个位置必须装上控制器，小J可以选择不同型号的控制器安装在每个位置上，每种型号的花费不同。为了让k台机器人看起来不那么相同，小J希望没有两台机器人的控制器是完全相同的。对于任意两台机器人来说，至少要有一个位置，在这个位置上两台机器人安装了不同的控制器（题目保证控制器种类总能满足需求）。现在小J希望他的机器人造价尽可能低，请计算最小费用。

输入$m[] (1 ≤ m[i] ≤ 10)$表示第i个位置可以安装的控制器数，$p[i][] (1 ≤ p[i][j] ≤ 1000000000)$表示在第i个位置安装第j种控制器的花费。

01 #include <bits/stdc++.h>
02 #define fi first
03 #define se second
04 #define ll long long
05 using namespace std;
06 typedef pair<int, int> PII;
07 const int N = 1e5 + 10;
08 
09 int n, k;
10 int m[N], p[N][20], tmp[N];
11 int a[N][20];
12 struct node {
13     int x, y, v;
14     bool operator<(const node t) const {
15         ①;
16     }
17 };
18 int main() {
19     cin >> n >> k;
20     vector<PII> t;
21     for (int i = 1; i <= n; i++) {
22         cin >> m[i];
23         for (int j = 1; j <= m[i]; j++) {
24             cin >> p[i][j];
25         }
26         sort(p[i] + 1, p[i] + 1 + m[i]);
27         if (m[i] > 1) {
28             ②;
29         } else {
30             t.push_back({-p[i][1], i});
31         }
32     }
33     sort(t.begin(), t.end());
34     for (int i = 1; i <= n; i++) {
35         int id = t[i - 1].se;
36         for (int j = 1; j <= m[id]; j++) {
37             a[i][j] = p[id][j];
38         }
39         tmp[i] = m[id];
40     }
41     for (int i = 1; i <= n; i++) m[i] = tmp[i];
42     int x, y, v = 0;
43     for (int i = 1; i <= n; i++) {
44         v += a[i][1];
45     }
46     for (int i = 1; i <= n; i++) {
47         if (t[i - 1].fi >= 0) {
48             x = i;
49             break;
50         }
51     }
52     ll ans = v;
53     priority_queue<node> q;
54     k--;
55     ③;
56     while (!q.empty() && k) {
57         k--;
58         node u = q.top();
59         q.pop();
60         x = u.x, y = u.y, v = u.v;
61         ans += v;
62         if (y < m[x]) {
63             ④;
64         }
65         if (x < n) {
66             q.push({x + 1, 2, v - a[x + 1][1] + a[x + 1][2]});
67         }
68         if (x < n && y == 2) {
69             ⑤;
70         }
71     }
72     cout << ans;
73     return 0;
74 }

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

• return v < t.v
• return v > t.v
• return x > t.x
• return y > t.y

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

• t.push_back({-p[i][1], i})
• t.push_back({p[i][1], i})
• t.push_back({p[i][m[i]] - p[i][1], i})
• t.push_back({p[i][2] - p[i][1], i})

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

• q.push({x, 1, 0})
• q.push({x, 1, v})
• q.push({x, 2, a[x][2] - a[x][1]})
• q.push({x, 2, v})

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

• q.push({x, y + 1, v - a[x][y] + a[x][y + 1]})
• q.push({x, y + 1, v + a[x][y + 1]})
• q.push({x, y, v - a[x][y] + a[x][y + 1]})
• q.push({x, y, a[x][y + 1] - a[x][y]})

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

• q.push({x + 1, y + 1, v + a[x + 1][y + 1] - a[x + 1][y]})
• q.push({x + 1, 2, v - a[x][2] + a[x][1] - a[x + 1][1] + a[x + 1][2]})
• q.push({x + 1, 2, v + a[x][2] - a[x][1] + a[x + 1][2] - a[x + 1][1]})
• q.push({x + 1, 2, v + a[x + 1][2] - a[x + 1][1]})

---