一、单项选择题（1~15 题，每题 2 分，共 30 分）
- 一个 32 位无符号整数可以表示的最大值，最接近下列哪个选项？（ ）
{{ select(1) }}
- 4 × 109
- 3 × 1010
- 2 × 109
- 2 × 1010
- 在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？（ ）
{{ select(2) }}
- 函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（ ） int calc(int n) { if (n <= 1) return 1; if (n % 2 == 0) return calc(n / 2) + 1; else return calc(n - 1) + calc(n - 2); }
{{ select(3) }}
- 用 5 个权值 10，12，15，20，25 构造哈夫曼树，该树的带权路径长度是多少？（ ）
{{ select(4) }}
- 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）
{{ select(5) }}
- 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？（ ）
{{ select(6) }}
- 假设 a，b，c 都是布尔变量，逻辑表达式 (a && b) || (a && !c) 的值与下列哪个表达式不始终相等？（ ）
{{ select(7) }}
- a && (b || !c)
- (a || !c) && (a || b)
- a && (!b || !c)
- !(a && (b || c))
- 已知f[0]=1,f[1]=1,并且对于所有n>=2有f[n]=(f(n-1)+f[n-2])%7，那么 f[2025] 的值是多少？（ ）
{{ select(8) }}
- 下列关于 C++ string 类的说法，正确的是？（ ）
{{ select(9) }}
- string 对象的长度在创建后不能改变。
- 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
- string 的 length() 和 size() 方法返回的值可能不同。
- string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。
- 考虑以下 C++ 函数：（ ） void solve(int &a, int b) { a = a + b; b = a - b; a = a - b; } int main() { int x = 5, y = 10; solve(x, y); } 在main函数调用 solve 后，x 和 y 的值分别是？
{{ select(10) }}
- 一个 8 × 8 的棋盘，左上角坐标为 (1,1)，右下角为 (8,8)。一个机器人从 (1,1) 出发，每次只能向右或向下走一格。要到达 (4,5)，有多少种不同的路径？（ ）
{{ select(11) }}
- 某同学用冒泡排序对数组 {6,1,5,2,4} 进行升序排序，请问需要进行多少次元素交换？（ ）
{{ select(12) }}
- 十进制数 72010 和八进制数 2708 的和用十六进制表示是多少？（ ）
{{ select(13) }}
- 一棵包含 1000 个结点的完全二叉树，其叶子结点的数量是多少？（ ）
{{ select(14) }}
- 一个初始为空的整数栈 S 和一个空的队列 P。我们按顺序处理输入的整数队列 A：7, 5, 8, 3, 1, 4, 2。对于队列 A 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 S；如果该数是偶数，且栈 S 非空，则弹出一个栈顶元素，并加入到队列 P 的末尾；如果该数是偶数，且栈 S 为空，则不进行任何操作。当队列 A 中的所有数都处理完毕后，队列 P 的内容是什么？（ ）
{{ select(15) }}
- 5, 1, 3
- 7, 5, 3
- 3, 1, 5
- 5, 1, 3, 7
二、阅读程序（判断题正确填 √、错误填 ×；判断题每题 1.5 分，选择题每题 3 分）
程序 1
1 | #include <algorithm>
2 | #include <cstdio>
3 | #include <cstring>
4 | inline int gcd(int a, int b) {
5 | if (b == 0)
6 | return a;
7 | return gcd(b, a % b);
8 | }
9 | int main() {
10 | int n;
11 | scanf("%d", &n);
12 | int ans = 0;
13 | for (int i = 1; i <= n; ++i)
14 | for (int j = i + 1; j <= n; ++j)
15 | for (int k = j + 1; k <= n; ++k)
16 | if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1)
17 | ++ans;
18 | printf("%d\n", ans);
19 | return 0;
20 | }
- (1分)当输入为 2 时，程序并不会执行第 16 行的判断语句。（ ）
{{ select(16) }}
- 将第16行中的“&&gcd(i,k)==1”删去不会影响运行结果。（ ）
{{ select(17) }}
- 当输入的 n ≥ 3 的时候，程序总是输出一个正整数。（ ）
{{ select(18) }}
- 将第 7 行的 “gcd(b, a % b)” 改为 “gcd(a, a % b)” 后，程序可能出现的问题是（ ）
{{ select(19) }}
- 输出的答案大于原答案。
- 输出的答案小于原答案。
- 程序有可能陷入死循环。
- 可能发生整型溢出问题。
- 当输入为 8 的时候，输出为（ ）
{{ select(20) }}
程序 2
1 | #include <algorithm>
2 | #include <cstdio>
3 | #include <cstring>
4 | inline int gcd(int a, int b) {
5 | if (b == 0)
6 | return a;
7 | return gcd(b, a % b);
8 | }
9 | int main() {
10 | int n;
11 | scanf("%d", &n);
12 | int ans = 0;
13 | for (int i = 1; i <= n; ++i)
14 | for (int j = i + 1; j <= n; ++j)
15 | for (int k = j + 1; k <= n; ++k)
16 | if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1)
17 | ++ans;
18 | printf("%d\n", ans);
19 | return 0;
20 | }
21 | #include <algorithm>
22 | #include <cstdio>
23 | #include <cstring>
24 | #define ll long long
25 | int n, k;
26 | int a[200007];
27 | int ans[200007];
28 | int main() {
29 | scanf("%d%d", &n, &k);
30 | for (int i = 1; i <= n; ++i)
31 | scanf("%d", &a[i]);
32 | std::sort(a + 1, a + n + 1);
33 | n = std::unique(a + 1, a + n + 1) - a - 1;
34 | for (int i = 1, j = 0; i <= n; ++i) {
35 | while (j < i && a[i] - a[j + 1] > k)
36 | ++j;
37 | ans[i] = ans[j] + 1;
38 | }
39 | printf("%d\n", ans[n]);
40 | return 0;
41 | }
- 调用 gcd(36, 42) 会返回（ ）
{{ select(21) }}
- 当输入为 “3 1 3 2 1” 时，输出结果为 2。（ ）
{{ select(22) }}
- 假设输入的 n 为正整数，输出的答案一定小于等于 n，大于等于 1。（ ）
{{ select(23) }}
- 将第 13 行的 “n = std::unique(a + 1, a + n + 1) - a - 1;” 删去后，有可能出现与原本代码不同的输出结果。（ ）
{{ select(24) }}
- 假设输入的 a 数组和 k 均为正整数，执行第 17 行代码时，一定满足的条件不包括（ ）
{{ select(25) }}
- j <= i
- j <= n
- a[i] - a[j] > k
- a[j] < a[i]
- 当输入的 n = 100、k = 2、a = {1, 2, ···, 100} 时，输出为（ ）
{{ select(26) }}
程序 3
1 | #include <algorithm>
2 | #include <cstdio>
3 | #include <cstring>
4 | inline int gcd(int a, int b) {
5 | if (b == 0)
6 | return a;
7 | return gcd(b, a % b);
8 | }
9 | int main() {
10 | int n;
11 | scanf("%d", &n);
12 | int ans = 0;
13 | for (int i = 1; i <= n; ++i)
14 | for (int j = i + 1; j <= n; ++j)
15 | for (int k = j + 1; k <= n; ++k)
16 | if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1)
17 | ++ans;
18 | printf("%d\n", ans);
19 | return 0;
20 | }
21 | #include <algorithm>
22 | #include <cstdio>
23 | #include <cstring>
24 | #define ll long long
25 | int n, k;
26 | int a[200007];
27 | int ans[200007];
28 | int main() {
29 | scanf("%d%d", &n, &k);
30 | for (int i = 1; i <= n; ++i)
31 | scanf("%d", &a[i]);
32 | std::sort(a + 1, a + n + 1);
33 | n = std::unique(a + 1, a + n + 1) - a - 1;
34 | for (int i = 1, j = 0; i <= n; ++i) {
35 | while (j < i && a[i] - a[j + 1] > k)
36 | ++j;
37 | ans[i] = ans[j] + 1;
38 | }
39 | printf("%d\n", ans[n]);
40 | return 0;
41 | }
42 | #include <algorithm>
43 | #include <cstdio>
44 | #include <cstring>
45 | #define ll long long
46 | int f[5007][5007];
47 | int a[5007], b[5007];
48 | int n;
49 | int main() {
50 | scanf("%d", &n);
51 | for (int i = 1; i <= n; ++i)
52 | scanf("%d", &a[i]);
53 | for (int i = 1; i <= n; ++i)
54 | scanf("%d", &b[i]);
55 | for (int i = 1; i <= n; ++i)
56 | for (int j = 1; j <= n; ++j) {
57 | f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
58 | if (a[i] == b[j])
59 | f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
60 | }
61 | printf("%d\n", f[n][n]);
62 | return 0;
63 | }
- 假设输入的 a 数组和 k 均为正整数，但 a 数组不一定有序，则若误删去第 12 行的 “std::sort(a + 1, a + n + 1);”，程序有可能出现的问题有（ ）
{{ select(27) }}
- 输出的答案比原本答案更大
- 输出的答案比原本答案更小
- 出现死循环行为
- 以上均可能发生
- 当输入 “4 1 2 3 4 1 3 2 2” 时，输出为 2。（ ）
{{ select(28) }}
- 当程序运行完毕后，对于所有的 1 ≤ i, j ≤ n，都一定有 f[i][j] <= f[n][n]。（ ）
{{ select(29) }}
- 将第 18 行的 “f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);” 删去后，并不影响程序运行结果。（ ）
{{ select(30) }}
- 输出的答案满足的性质有（ ）
{{ select(31) }}
- 小于等于 n
- 大于等于 0
- 不一定大于等于 1
- 以上均是
- 如果在第 16 行的循环前加上以下两行：std::sort(a + 1, a + n + 1); std::sort(b + 1, b + n + 1); 则答案会（ ）
{{ select(32) }}
- 如果输入的 a = {1, 2, ···, n}，而且 b 数组中数字均为 1~n 中的正整数，则上述代码等价于下面哪个问题：（ ）
{{ select(33) }}
- 求 b 数组去重后的长度
- 求 b 数组的最长上升子序列
- 求 b 数组的长度
- 求 b 数组的最大值
三、完善程序（每题 3 分）
程序 1
1 | #include <cctype>
2 | #include <iostream>
3 | #include <string>
4 | using namespace std;
5 | int main() {
6 | string z;
7 | cin >> z;
8 | string s=””;
9 | for (int i = 0; i < z.length(); i++) {
10 | char ch = z[i];
11 | if (① && isdigit(z[i + 1])) {
12 | i++;
13 | int count = 0;
14 | while (i < z.length() && isdigit(z[i])) {
15 | count = ②;
16 | i++;
17 | }
18 | for (int j = 0; j < ③; ++j)
19 | s+=ch;
20 | } else {
21 | s += ④;
22 | ⑤
23 | }
24 | }
25 | cout << s << endl;
26 | return 0;
27 | }
- ① 处应填（ ）
{{ select(34) }}
- i < z.length()
- i - 1 >= 0
- i + 1 < z.length()
- isdigit(z[i])
- ② 处应填（ ）
{{ select(35) }}
- count = count * 10 + (z[i] - '0')
- count = count * 10 + z[i]
- count = z[i] - '0'
- count + 1
- ③ 处应填（ ）
{{ select(36) }}
- count - 1
- count
- 10
- z[i]-’0’
- ④ 处应填（ ）
{{ select(37) }}
- z[i + 1]
- ch
- (char)(z[i] + 1)
- z.back()
程序 2
1 | #include <cctype>
2 | #include <iostream>
3 | #include <string>
4 | using namespace std;
5 | int main() {
6 | string z;
7 | cin >> z;
8 | string s=””;
9 | for (int i = 0; i < z.length(); i++) {
10 | char ch = z[i];
11 | if (① && isdigit(z[i + 1])) {
12 | i++;
13 | int count = 0;
14 | while (i < z.length() && isdigit(z[i])) {
15 | count = ②;
16 | i++;
17 | }
18 | for (int j = 0; j < ③; ++j)
19 | s+=ch;
20 | } else {
21 | s += ④;
22 | ⑤
23 | }
24 | }
25 | cout << s << endl;
26 | return 0;
27 | }
28 | #include <iostream>
29 | #include <vector>
30 | using namespace std;
31 | bool query(int i, int j);
32 | int N;
33 | int main() {
34 | cin >> N;
35 | int candidate = 0;
36 | int count = ①;
37 | for (int i = 1; i < N; i++) {
38 | if (②) {
39 | candidate = i;
40 | count = 1;
41 | } else {
42 | if (③) {
43 | ④;
44 | } else {
45 | count++;
46 | }
47 | }
48 | cout <<⑤<< endl;
49 | return 0;
50 | }
- ⑤处应填（ ）
{{ select(38) }}
- i--
- i = i + 2
- i++
- 不执行任何操作
- ① 处应填（ ）
{{ select(39) }}
- count == 0
- count == 1
- i < N
- query(candidate, i) == true
- ② 处应填（ ）
{{ select(40) }}
- query(candidate, i)
- count < 0
- count == 0
- query(candidate, i) == false
- ③ 处应填（ ）
{{ select(41) }}
- query(candidate, i) == false
- query(i, candidate) == true
- query(candidate, i) == false && query(i, candidate) == false
- query(candidate, i) == true && query(i, candidate) == true
- ④ 处应填（ ）
{{ select(42) }}
- break
- count++
- count--
- candidate = i
- ⑤ 处应填（ ）
{{ select(43) }}
