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

1. 已知x为int类型的变量，下列表达式中不符合语法的是（ ）。 {{ select(1) }}

• x + 8
• x++9
• 18 + x
• x--7

2. 在简单图中，有n个顶点的有向强连通图最多有（ ）条边，最少有（ ）条边。 {{ select(2) }}

• n*(n-1)/2；n-1
• n*(n-1)/2；n
• n*(n-1)；n*(n-1)/2
• n*(n-1)；n

3. STL中pair定义在（ ）头文件中。 {{ select(3) }}

• map
• utility
• set
• algorithm

4. 以下属于TCP/IP协议族中应用层协议的是（ ）。 {{ select(4) }}

• UDP
• ARP
• SMTP
• ICMP

5. 下面有关数据结构并查集的说法中，错误的是（ ）。 {{ select(5) }}

• 并查集里面的结点信息通常用字典树进行存储
• 并查集支持的主要操作是查询两个元素是否属于同一个集合，将两个不同的集合合并为一个集合
• 并查集中一般估价函数与集合内结点的数量或表示集合的树的最大深度相关
• 带权并查集一般也支持路径压缩和启发式合并

6. 关于下面C++代码的说法中不正确的是（ ）。

int Value(BiTree root) {
    if (root == NULL) return 0;
    else {
        int x = Value(root->lchild);
        int y = Value(root->rchild);
        if (x > y) return x + 1;
        else return y + 1;
    }
}

{{ select(6) }}

• 该代码可用于求二叉树的高度
• 代码中函数Value()的参数root表示根结点，非根结点不可以作为参数
• 代码中函数Value()采用了递归的方法
• 代码中的函数Value()可用于计算二叉树的高度，但前提是该二叉树的结点都有lchild和rchild属性

7. Floyd-Warshall算法的时间复杂度是（ ）。 {{ select(7) }}

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

8. 前缀表达式“+ 13 * 2 + 15 12”的值是（ ）。 {{ select(8) }}

• 67
• 56
• 53
• 233

9. 下面有关C++类和对象的说法中，错误的是（ ）。 {{ select(9) }}

• 以struct声明的类中的成员默认为public形式
• 以class声明的类中的成员默认为private形式
• 类的成员函数具有访问类内所有成员的权限
• 类可以实例化为对象，通常通过~访问对象的成员

10. 一个无向图包含n个顶点，则其最小生成树包含多少条边？（ ） {{ select(10) }}

• n
• n - 1
• n / 2
• n - 1或不存在

11. 一个盒子装有红、白、蓝、绿四种颜色的玻璃球，每种颜色的玻璃球至少有一个。从中随机拿出四个玻璃球，这四个球都是红色的概率为p1，恰好有三个红色和一个白色的概率为p2，恰好有两个红色、一个白色和一个蓝色的概率为p3，四种颜色各有一个的概率为p4。若恰好有$p1 = p2 = p3 = p4$，则这个盒子里玻璃球的个数的最小值等于（ ）。 {{ select(11) }}

• 17
• 19
• 21
• 23

12. 考虑下列32个数：1!，2!，3!，…，32!，请你去掉其中的一个数，使得其余各数的乘积为一个完全平方数，则划去的那个数是（ ）。 {{ select(12) }}

• 12!
• 14!
• 16!
• 18!

13. 下面关于C++语言中指针的说法正确的是（ ）。 {{ select(13) }}

• 在32位计算机中一个指针变量占4字节
• 指针运算实际上是地址操作，只能取地址和间接访问，不能进行加减运算
• 数组名不是指向数组元素的指针变量
• 指针只可以静态申请内存空间

14. 以下关于搜索算法的说法中（ ）是错误的。 {{ select(14) }}

• 记忆化搜索算法通常使用数组、映射等作为状态存储的数据结构
• 剪枝优化算法消耗的时间和空间一定都比原算法更少
• 启发式搜索算法通常需要定义一个启发式函数
• 当搜索空间较大，目标解深度未知时，迭代加深搜索在时间复杂度方面优于深度优先搜索，在空间复杂度方面优于广度优先搜索

15. 若一个三位数的各位数字之和为10，则称这个数为SQSM数，如208，136，370都是SQSM数。现从所有三位数中任取一个数恰好为SQSM数的概率是（ ）。 {{ select(15) }}

• 1/20
• 7/90
• 3/50
• 1/15

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn = 2e5 + 5;
04 string str;
05 int num[30], n;
06 long long F[maxn];
07 long long comb(int n, int m) {
08     if (m < 0 || m > n) return 0;
09     return F[n] / F[m] / F[n - m];
10 }
11 long long dfs(int len, int now) {
12     if (len == n - 1) return 1;
13     if (len == -1 && now < str[len] - 'A') {
14         int need = n - len - 1;
15         long long tmp = 1;
16         for (int i = 0; i < 26; i++)
17             if (num[i]) {
18                 tmp *= comb(need, num[i]);
19                 need -= num[i];
20             }
21         return tmp;
22     }
23     long long tmp = 0;
24     for (int i = 0; i < 26; i++) {
25         if (i <= str[len + 1] - 'A' && num[i]) {
26             num[i]--;
27             tmp += dfs(len + 1, i);
28             num[i]++;
29         }
30     }
31     return tmp;
32 }
33 int main() {
34     F[0] = 1;
35     cin >> str;
36     n = str.size();
37     for (int i = 1; i <= n; i++) {
38         F[i] = F[i - 1] * i;
39     }
40     for (int i = 0; i < n; i++)
41         num[str[i] - 'A']++;
42     cout << dfs(-1, 30);
43 }

■ 判断题

16. 若删除第8行，程序运行结果一定不变。（ ） {{ select(16) }}

• 正确
• 错误

17. 若将第38行改为F[i + 1] = F[i] * i，程序运行结果一定不变。（ ） {{ select(17) }}

• 正确
• 错误

18. 若输入的字符串长度大于20，则程序可能产生未定义行为。（ ） {{ select(18) }}

• 正确
• 错误

19. 若删除第34行，则无论输入什么，输出都为0。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题

20. 若输入的字符串为CCCCCCCCCC（10个C），则输出为（ ）。 {{ select(20) }}

• 1
• 10
• 55
• 3628800（10的阶乘）

21. 若输入的字符串为DBDC，则输出为（ ）。 {{ select(21) }}

• 2
• 4
• 8
• 24

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int n;
04 int dfs(vector<int> a, int l = 0, int r = n - 1) {
05     if (l == r || l == n / 2) return 0;
06     int t = a[rand() % (r - l + 1)];
07     vector<int> low, up;
08     for (int i = 0; i < r - l + 1; i++) {
09         if (a[i] < t) {
10             low.push_back(a[i]);
11         } else if (a[i] > t) {
12             up.push_back(a[i]);
13         }
14     }
15     if (l + (int)low.size() - 1 >= n / 2)
16         return dfs(low, l, l + low.size() - 1);
17     else if (r - up.size() + 1 <= n / 2)
18         return dfs(up, l + low.size() + 1, r);
19     else
20         return t;
21 }
22 int main() {
23     cin >> n;
24     vector<int> a(n);
25     for (int i = 0; i < n; i++) {
26         cin >> a[i];
27     }
28     cout << dfs(a);
29 }

■ 判断题

22. 若将第6行改为int t = a[0]，程序运行结果不会发生改变。（ ） {{ select(22) }}

• 正确
• 错误

23. 若将第4行的后两个参数改为int l, int r，程序运行结果不会发生改变。（ ） {{ select(23) }}

• 正确
• 错误

24. 第5行的后面应该再加一个判断语句if (l > r) return 0;，否则程序可能会发生死循环。（ ） {{ select(24) }}

• 正确
• 错误

25. 若输入的n的值为1，则无论输入什么，输出都为0。（ ） {{ select(25) }}

• 正确
• 错误

■ 选择题

26. 该程序的期望时间复杂度为（ ）。 {{ select(26) }}

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

27. （4分）若输入为6 1 10 7 8 2 2，则输出为（ ）。 {{ select(27) }}

• 6
• 8
• 2
• 7

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define ll long long
04 const int maxm = 1e6 + 5;
05 class hash_map {
06 public:
07     struct node {
08         ll u;
09         ll v, next;
10     } e[maxm << 1];
11     ll head[maxm], nume, numk, id[maxm];
12     ll operator[](ll u) {
13         int hs = u % maxm;
14         for (int i = head[hs]; i; i = e[i].next)
15             if (e[i].u == u) return e[i].v;
16         if (!head[hs]) id[++numk] = hs;
17         e[++nume] = {u, 0, head[hs]}, head[hs] = nume;
18         return e[nume].v;
19     }
20     void clear() {
21         for (int i = 1; i <= numk; i++)
22             head[id[i]] = 0;
23         numk = nume = 0;
24     }
25 } m;
26 int main() {
27     int n;
28     ll a, b, c;
29     cin >> n;
30     while (n--) {
31         cin >> a;
32         if (a == 1) {
33             cin >> b >> c;
34             m[b] = c;
35         } else {
36             cin >> b;
37             cout << m[b] << endl;
38         }
39     }
40 }

■ 判断题

28. 该hash_map只能存储整数与整数的对应关系，无法存储字符串或小数与整数的对应关系。（ ） {{ select(28) }}

• 正确
• 错误

29. 首先输入1使得n = 1，然后再输入2 3，则输出为0。（ ） {{ select(29) }}

• 正确
• 错误

30. 若输入的所有a都为1，则程序没有输出。（ ） {{ select(30) }}

• 正确
• 错误

31. 若先输入3，然后输入1 2 3\n1 2 4\n2 2（其中\n为换行符），则输出为4。（ ） {{ select(31) }}

• 正确
• 错误

■ 选择题

32. 该代码解决哈希冲突的方式为（ ）。 {{ select(32) }}

• 链地址法
• 线性探测再哈希法
• 再哈希法
• 该代码不解决冲突，只是避免了冲突的发生

33. 若已插入元素的数量为n，数组大小为m（本代码中m为$10^6$），则调用clear()函数的时间复杂度为（ ）。 {{ select(33) }}

• $O(n)$
• $O(m)$
• $O(n + m)$
• $O(nm)$

34. 若已插入元素的数量为n，且n的大小约为$m/100$，则单次调用[]的平均时间复杂度和最坏情况下的时间复杂度为（ ）。 {{ select(34) }}

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

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

(1) 题目描述： （树的重心）给出一棵无根树，求树的重心。树的重心的定义是：在一棵树中，当删除某个特定结点以及与该结点相连的所有边后，剩余的各个连通块中，最大连通块所包含的结点数量达到最小，具有这种特性的结点就是树的重心。若有多个符合条件的结点，则输出编号最小的那个。

思路：对每一个结点的每一棵子树求最大值，找到最大子树最小的结点即可。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn = 2e4 + 5;
04 int son[maxn], n, ans = 1, size = 1e5;
05 vector<int> G[maxn];
06 void dfs(int now, int pre) {
07     int tmp = 0;
08     son[now] = 1;
09     for (int i = 0; i < G[now].size(); i++) {
10         int nxt = G[now][i];
11         if (nxt != pre) {
12             dfs(nxt, now);
13             son[now] += ①;
14             tmp = max(tmp, ②);
15         }
16     }
17     tmp = max(tmp, ③);
18     if (④) {
19         ans = now;
20         size = tmp;
21     }
22 }
23 int main() {
24     cin >> n;
25     for (int i = 1; i < n; i++) {
26         int u, v;
27         cin >> u >> v;
28         G[u].push_back(v);
29         G[v].push_back(u);
30     }
31     dfs(1, -1);
32     cout << ans << endl;
33 }

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

• son[nxt]
• son[nxt] + 1
• 1
• son[now]

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

• son[now]
• son[now] + 1
• son[nxt] + 1
• son[nxt]

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

• son[now]
• n - son[now]
• n - son[now] - 1
• son[now] + 1

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

• tmp < size
• tmp <= size
• tmp * maxn + now < size * maxn + ans
• now * maxn + tmp < ans * maxn + size

(2) 题目描述： （数字游戏）Alice和Bob正在玩数字游戏。初始时两个人手中的数字分别为a和b，两个人轮流操作，每次操作要么将手中的数字加上对方手中的数字，然后对n求余；要么用手中的数字乘以对方手中的数字，然后对n求余。得到的新数字替换自己手上原来的数字。假设$n = 5$，$a = 2$，$b = 3$，那么Alice可以用第一种操作使得自己手中的数字变成$(2 + 3) \% 5 = 0$，或者用第二种操作让自己手中的数字变成$(2 * 3) \% 5 = 1$。谁先让自己手中的数字变为0，谁就获胜。输出1表示先手必胜，0表示平局，-1表示后手必胜。

01 #include <bits/stdc++.h>
02 using namespace std;
03 vector<int> g[1100000];
04 int f[1100000];
05 int n, k, a, b;
06 #define id(a, b) (a * n + b)
07 int cnt[1100000];
08 void init(int n) {
09     for (int i = 1; i < n; i++)
10         for (int j = 1; j < n; j++)
11             g[id(j, ①)].push_back(id(i, j));
12     for (int i = 1; i < n; i++)
13         for (int j = 1; j < n; j++)
14             g[id(j, (i + j) % n)].push_back(id(i, j));
15 }
16 int main() {
17     cin >> n;
18     init(n);
19     queue<pair<int, int>> Q;
20     for (int i = 0; i <= n * n; i++)
21         cnt[i] = ②;
22     for (int i = 1; i < n; i++)
23         Q.push(③);
24     while (!Q.empty()) {
25         pair<int, int> x = Q.front();
26         Q.pop();
27         for (int y : g[x.first]) {
28             if (④) continue;
29             if (!x.second) {
30                 f[y] = 1;
31                 Q.push({y, 1});
32             } else {
33                 cnt[y]--;
34                 if (!cnt[y]) {
35                     f[y] = -1;
36                     Q.push(⑤);
37                 }
38             }
39         }
40     }
41     cin >> a >> b;
42     cout << f[⑥] << endl;
43 }

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

• i + j % n
• i + j
• i * j
• (i * j) % n

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

• 2
• 1
• n
• n / 2

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

• {i, 0}
• {i, 1}
• {n * i, 0}
• {n * i, 1}

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

• f[y] == 0
• f[y] != 0
• f[x.second] != 0
• f[x.second] == 0

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

• {y, 0}
• {y, -1}
• {y, 1}
• {y, n}

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

• a + b
• a * b % n
• (a + b) % n
• id(a, b)

---