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

1. 表达式(8%(-6))与(-8%6)的值为（ ）。 {{ select(1) }}

• -2,-2
• 2,-2
• -2,2
• 2,2

2. 设根结点深度为0，一棵深度为h的满三叉树，即除最后一层无任何子结点外，每一层上的所有结点都有3个子结点的树，共有（ ）个结点。 {{ select(2) }}

• $\left(3^{h+1}-1\right) / 2$
• $3^{h-1}$
• $3^{h}$
• $\left(3^{h-1}-1\right) / 2$

3. 以下不属于调试工具GDB中的命令的是（ ）。 {{ select(3) }}

• printf
• display
• next
• step

4. 以下哪个不属于算法的最本质特征？（ ） {{ select(4) }}

• 有穷性
• 确定性
• 先进性
• 确切性

5. 以下哪个不属于哈希冲突的常见处理方法？（ ） {{ select(5) }}

• 哈希法
• 线性探查法
• 二次探查法
• 固定分配法

6. 单源最短路问题的常用算法不包含（ ）。 {{ select(6) }}

• Bellman-Ford
• Dijkstra
• SPFA
• Kruskal

7. 设某算法的时间复杂度函数的递推方程是$F(n)=F(n-1)+2n$（n为正整数）及$F(0)=0$，则该算法的时间复杂度为（ ）。 {{ select(7) }}

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

8. 一棵二叉树一共有19个结点，其叶子结点不可能有（ ）个。 {{ select(8) }}

• 11
• 10
• 9
• 1

9. 关于拓扑排序，下面的说法哪个是正确的？（ ） {{ select(9) }}

• 拓扑排序只能用广度优先遍历实现
• 每个有向图都至少存在一个拓扑排序
• 拓扑排序一定从入度为0的结点开始
• 拓扑排序的方案一定是唯一的

10. 下列说法中哪个不是树的性质？（ ） {{ select(10) }}

• 任意两个结点之间有且只有一条简单路径
• 树中有可能有一个简单环
• 边的数目恰好是顶点数目减1
• 树中无环

11. 对于完全背包问题（给出n种物品和一个容积为m的背包，每种物品有无限个，单个大小为v[]，价值为$w[i]$，要求选择合适的物品放入背包，满足大小不超过容积且价值最大），设f[]表示用去i的空间能获得的最大价值，倒序枚举i为使用的空间，正序枚举j为物品编号，则可写出动态转移方程（ ）。 {{ select(11) }}

• f[i]=max (f[i], f[i-w[j]]+v[j])
• f[i]=max (f[i], f[i-v[j]]+w[j])
• f[i]=min (f[i], f[i-w[j]]+v[j])
• f[i]=min (f[i], f[i-v[j]]+w[j])

12. 前缀表达式a+bcd的后缀表达式是（ ）。** {{ select(12) }}

• abcd*+*
• abc+d
• axbc+*d
• b+Cad

13. 某学校“信奥”小组有男生和女生各3名，现从中挑选2名学生去参加市科技节编程竞赛，至少有1名男生参加的概率是（ ）。 {{ select(13) }}

• 0.5
• 0.6
• 0.7
• 0.8

14. 四面体的顶点及各棱中点加起来共有10个点，在其中取4个不共面的点，不同的取法共有（ ）种。 {{ select(14) }}

• 150
• 147
• 144
• 141

15. 设全集$E=\{a, b, c, d, e\}$，集合$A=\{a, c\}$，$B=\{a, b, d\}$，$C=\{b, d\}$，则集合$(A \cap B) \cup ~C$为（ ）。 {{ select(15) }}

• [a}
• {c,e}
• {a,e}
• {a,c,e}

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

(1)

01 #include<bits/stdc++.h>
02 using namespace std;
03 
04 int dp[502][502];
05 
06 int main(){
07     string s;
08     cin >> s;
09     for (int j = 0; j <= s.size(); j++) {
10         for (int i = 0; i < s.size() - j; i++) {
11             dp[i][i + j] = dp[i + 1][i + j] + 1;
12             for (int k = i + 1; k <= i + j; k++) {
13                 if (s[k] == s[i]) {
14                     dp[i][i + j] = min(dp[i][i + j], dp[i + 1][k - 1] + dp[k + 1][i + j]);
15                 }
16             }
17         }
18     }
19     cout << dp[0][s.size() - 1] << endl;
20     return 0;
21 }

■ 判断题 16. 将第11行改为dp[i][j]=INT_MAX-1，代码的输出结果会改变。（ ） {{ select(16) }}

• 正确
• 错误

17. 修改第13行为if(s[i]==s[j])，代码的输出结果不变。（ ） {{ select(17) }}

• 正确
• 错误

18. 用贪心算法可以实现与本程序同样的功能。（ ） {{ select(18) }}

• 正确
• 错误

19. 将第12行中for循环的k的初始值从i+1改为1，代码的输出结果不变。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题

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

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

21. 对于输入aagog，本程序的输出为（ ）。 {{ select(21) }}

• 1
• 2
• 3
• 5

(2)

01 #include <bits/stdc++.h>
02 
03 using namespace std;
04 pair<int, int> pi;
05 
06 int parent[100000], sz[100000];
07 
08 int n, m, components;
09 
10 void initialize() {
11     for (int i = 0; i < n; i++) {
12         parent[i] = i;
13         sz[i] = 1;
14     }
15 }
16 
17 int find(int a) {
18     if (parent[a] == a) {
19         return a;
20     }
21     return find(parent[a]);
22 }
23 
24 bool sameDSu(int a, int b) {
25     return find(a) == find(b);
26 }
27 
28 void merge(int a, int b) {
29     a = find(a), b = find(b);
30     if (a == b) return;
31     --components;
32     if (sz[a] > sz[b]) swap(a, b);
33     parent[a] = b;
34     sz[b] += sz[a];
35 }
36 
37 int findsz(int a) {
38     return sz[find(a)];
39 }
40 
41 int main() {
42     cin >> n >> m;
43     initialize();
44     components = n;
45     int maxComponents = 1;
46     for (int i = 0; i < m; i++) {
47         int a, b; cin >> a >> b;
48         merge(a, b);
49         maxComponents = max(maxComponents, findsz(a));
50         cout << components << " " << maxComponents << endl;
51     }
52 }

■ 判断题 22. 如果输入的a和b从1开始编号，程序依然可以正常运行。（ ） {{ select(22) }}

• 正确
• 错误

23. 该程序计算了无向图的连通分量数。（ ） {{ select(23) }}

• 正确
• 错误

24. 合并操作总是将较小树的根结点合并到较大树的根结点下。（ ） {{ select(24) }}

• 正确
• 错误

25. 为了确保该程序不发生错误，需要保证输入的a和b互不相同。（ ） {{ select(25) }}

• 正确
• 错误

■ 选择题 26. 在程序运行结束时，maxComponents变量可以存储的最大值是（ ）。 {{ select(26) }}

• n/2
• n
• m/2
• m

27. 如果合并操作merge总是将结点b合并到结点a，不论它们各自的sz大小如何，程序的最坏运行时间会如何变化？（ ） {{ select(27) }}

• 变快
• 保持不变
• 变慢
• 无法确定

(3)

01 #include<bits/stdc++.h>
02 using namespace std;
03 typedef long long ll;
04 
05 const int MAXN = 2e5 + 7;
06 const int BITS = 30;
07 int numNodes, nodevalues[MAXN];
08 int trieNodeCount, trie[MAXN][2], maxIndex[MAXN][BITS];
09 
10 void insert(int value, int index) {
11     int currentNode = 0;
12     for (int bit = BITS - 1; bit >= 0; bit--) {
13         int currentBit = (value >> bit) & 1;
14         if (!trie[currentNode][currentBit]) {
15             trie[currentNode][currentBit] = trieNodeCount++;
16         }
17         currentNode = trie[currentNode][currentBit];
18         maxIndex[currentNode] = max(maxIndex[currentNode], index);
19     }
20 }
21 
22 int query(int value, int index) {
23     int currentNode = 0, result = 0;
24     for (int bit = BITS - 1; bit >= 0; bit--) {
25         int currentBit = (value >> bit) & 1;
26         if (trie[currentNode][currentBit] && maxIndex[trie[currentNode][currentBit]] >= index) {
27             currentNode = trie[currentNode][currentBit];
28         } else {
29             currentNode = trie[currentNode][1 - currentBit];
30             result += (1 << bit);
31         }
32     }
33     return result;
34 }
35 
36 ll weight;
37 void findMinimumXor(int left, int right, int bitPosition) {
38     if (left == right || bitPosition < 0) return;
39     int mid = left;
40     while (mid < right && (nodevalues[mid] >> bitPosition) & 1) {
41         mid++;
42     }
43     findMinimumXor(left, mid, bitPosition - 1);
44     findMinimumXor(mid, right, bitPosition - 1);
45     if (mid == right || mid == left) return;
46     int minEdgeweight = INT_MAX;
47     for (int i = left; i < mid; i++) {
48         minEdgeweight = min(minEdgeweight, query(nodevalues[i], mid) ^ nodevalues[i]);
49     }
50     weight += minEdgeweight;
51 }
52 
53 int main() {
54     trieNodeCount = 1;
55     cin >> numNodes;
56     for (int i = 0; i < numNodes; i++) cin >> nodevalues[i];
57     sort(nodevalues, nodevalues + numNodes);
58     for (int i = 0; i < numNodes; i++) insert(nodevalues[i], i);
59     findMinimumXor(0, numNodes, BITS - 1);
60     cout << weight << endl;
61     return 0;
62 }

注：输入的$n ≤1000$，(a,b)代表一条边，输入保证所有的边会组成一棵树。

■ 判断题 28. （2分）当输入的任意一个nodeValues[]为0时，程序会发生越界。（ ） {{ select(28) }}

• 正确
• 错误

29. （2分）如果将第55行改为sort(nodeValues,nodeValues+numNodes, greater<int>());，那么代码的输出结果不变。（ ） {{ select(29) }}

• 正确
• 错误

30. （3分）输入的nodevalues数组中的每个元素必须互不相同。（ ） {{ select(30) }}

• 正确
• 错误

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

• 5
• 8
• 1
• 4

32. 如果增大BITS常量，程序将受什么影响？（ ） {{ select(32) }}

• 运行速度将提高
• 能处理更大的整数
• 需要更多的内存空间
• 不会有任何变化

33. 如果输入的nodeValues全为0，则weight的值将是（ ）。 {{ select(33) }}

• 0
• numNodes-1
• BITS
• 无法确定

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

(1) 输入一个整数N和N个$[0, 2^{21}-1]$范围内的整数，求出从任意位置开始的最大区间异或和。如果有多个这样的子区间，则选择最短子区间，输出区间的左右端点。

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 1e5 + 10;
04 const int MAXM = MAXN * 21;
05 int n, X;
06 int s[MAXN], id[MAXM];
07 int tree[MAXM][2], idx;
08 
09 void insert(int x, int k) {
10     int p = 0;
11     for (int i = 20; i >= 0; i--) {
12         int u = (X >> i) & 1;
13         if (!tree[p][u])
14             _______;
15         _______;
16     }
17     id[p] = k;
18 }
19 
20 int query(int x) {
21     int p = 0;
22     for (int i = 20; i >= 0; i--) {
23         int u = (X >> i) & 1;
24         if (_______) p = tree[p][u ^ 1];
25         else p= tree[p][u];
26     }
27     return id[p];
28 }
29 
30 int main() {
31     cin >> n;
32     insert(s[0], 0);
33     int res = -1;
34     int l, r;
35     for (int i = 1; i <= n; ++i) {
36         cin >> X;
37         s[i] = s[i - 1] ^ x;
38         int k = query(s[i]);
39         int maxn = _______;
40         if (maxn > res) {
41             res = maxn;
42             l = k + 1, r = i;
43         }
44         _______;
45     }
46     cout << res << " " << l << " " << r << endl;
47     return 0;
48 }

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

• tree[p][u]=++idx
• tree[p][u]=- tree[p][u^1]
• tree[p][u]=++p
• tree[p+1][u]=++idx

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

• p=idx
• p=u
• p=tree[p][u]
• p=++p

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

• tree[p][u]
• !tree[p][u^1]
• !tree[p][u]
• tree[p][u^1]

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

• s[i]^s[k]
• s[r]^s[k]
• s[i]^x
• s[l]^s[r]

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

• insert(s[i],i)
• insert(s[r],r-1)
• insert(s[r],r)
• insert(s[i],i-1)

(2) 给定一个$n ×m$的矩阵，将$r ×c$的矩阵分成$r' ×c$和$r \times(c-c')$的矩阵需要$r^{2}$的代价。求分出一个大小和为k的矩阵所需的最小代价。

输入样例1： 2 2 1 输出样例1： 5

输入样例2： 2 2 3 输出样例2： 5

样例1解释：一共需要进行2次操作。 i. 把2×2的矩阵分为两个2x1的矩阵，代价为$2^2=4$。 ii. 把2x1的矩阵分为两个1x1的矩阵，代价为$1^2=1$，此时得到1x1的矩阵的和为1，总代价为$1+4=5$。

样例2解释：一共需要进行2次操作。 i. 把2×2的矩阵分为两个2x1的矩阵，代价为$2^2=4$。 ii. 把2x1的矩阵分为两个1x1的矩阵，代价为$1^2=1$，此时得到1x1的矩阵和2x1的矩阵的和为3，总代价为$1+4=5$。

01 #include <bits/stdc++.h>
02 #define LL long long
03 using namespace std;
04 
05 const int INF = 0x3f3f3f3f;
06 const int MAXN = 37;
07 int n, m, k, f[MAXN][MAXN][MAXN];
08 int solve(int x, int y, int z) {
09     if (f[x][y][z])
10         return _______;
11     if (_______ || !z)
12         return 0;
13     int res = _______;
14     for (int i = 1; i <= x - i; ++i)
15         for (int j = 0; j <= z; ++j)
16             res = min(res, _______);
17     for (int i = 1; i <= y - i; ++i)
18         for (int j = 0; j <= z; ++j)
19             res = min(res, x * x + solve(x, i, j) + solve(x, y - i, z - j));
20     return _______;
21 }
22 
23 int main() {
24     cin >> n >> m >> k;
25     cout << solve(n, m, k);
26     return 0;
27 }

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

• f[x-1][y-1][z-1]
• f[x][y][z]
• f[x%2][y%2][z%2]
• f[MAXN-x][MAXN-y][MAXN-z]

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

• z==1
• z==x * y
• z==x+y
• z>= MAXN

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

• INF
• -MAXN
• 0
• MAXN

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

• y * y+solve(y, i, j)+solve(x-i, y, z-j)
• y * y+solve(i, y, j)+solve(x-i, y, z-j)
• (x-i) *(x-i)+solve(x-i, i, j)+solve(x-i, y, z)
• (x-i) *(x-i)+solve(i, x-i, j)+solve(x, y-i, z-j)

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

• res =f[x][y][z]
• f[x-1][y-1][z-1]= res
• f[x][y][z]= res
• res +=f[x][y][z]

---