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

第 1 题

$(1047)_8$ =（ ）。 {{ select(1) }}

• $(1011011101)_2$
• $(11010)_5$
• $(20213)_4$
• $(308)_ 1$$_6$

第 2 题

若逻辑变量 A、C 为真，B、D 为假，以下逻辑表达式的值为假的是（ ）。

{{ select(2) }}

• $(B∨C∨D)∨D∧A$
• $((﹁A∧B)∨C)∧﹁B$
• $(A∧B)∨﹁(C∧D∨﹁A)$
• $A∧(D∨﹁C)∧B$

第 3 题

小恺编写了如下函数，希望计算斐波那契数列 $f(n)$第 n 项对 $10000$ 取余 数的值：

int f(int x) {
if(x <= 2)
return 1;
int ans = f(x - 1) + f(x - 2);
ans %= 10000;
return ans;
}

在运行空间限制 128MB、栈空间不超过空间限制、运行时限 1 秒的情况 下，在主函数中运行函数 f(12345)，则最有可能首先发生什么问题？

{{ select(3) }}

• 运行时间超时
• 栈溢出
• 访问无效内存
• 返回错误的答案

第 4 题

表达式 a+b*(c-d)/e-f 的后缀表达式为（ ）。 {{ select(4) }}

• $-+a/*b-c-cdef$
• $abcd-*e/+f-$
• $+ab*-cd/e-f$
• $f-e/d-d*b+a$

第 5 题

某个 $MV$ 是一段时长 4 分整的视频文件。它每秒播放 10 帧图像，每帧 图像是一幅分辨率为 $2048×1152$ 像素（长宽比 $16:9$）的 $32$ 位真彩色 图像，其画面没有被压缩。这个视频没有音频。这个视频文件大约需要占 用多大的存储空间？（ ）。

{{ select(5) }}

• $21 GiB$
• $27 GiB$
• $168 GiB$
• $2 GiB$

第 6 题

下图是一棵二叉树，它的后序遍历是( )。

{{ select(6) }}

• $ABDEFC$
• $DBEFAC$
• $DFEBCA$
• $ABCDEF$

第 7 题

五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个 数是 （ ）？

{{ select(7) }}

• $10$
• $1024$
• $15$
• $120$

第 8 题

设元素 $a,b,c,d,e,f$ 依次入栈，则下列不合法的出栈序列为（ ）? {{ select(8) }}

• $d,c,b,e,f,a$
• $f,e,d,c,b,a$
• $c,d,f,e,b,a$
• $e,d,b,a,f,c$

第 9 题

同时扔出 $3$ 枚完全相同的六面骰子，每个骰子上有 $1$ 到 $6$ 的数字。将得 到的点数排序后，有（ ）种不同的结果？

{{ select(9) }}

• $208$
• $56$
• $216$
• $120$

第 10 题

在编程时（使用任一种高级语言，不一定是 C++），如果需要从磁盘文件中 输入一个很大的二维数组（例如 $1000*1000$ 的 $double$ 型数组），按行读 （即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输 入效率上 （ ）。

{{ select(10) }}

• 没有区别
• 按行读的方式更高
• 按列读的方式更高
• 取决于数组的存储方式

第 11 题

不考虑稳定性，下列排序方法中平均时间复杂度最大的是 （ ）。 {{ select(11) }}

• 插入排序
• 希尔排序
• 归并排序
• 快速排序

第 12 题

将数组 $12,23,-1,19,117,-103,79,602$ 中的元素按从大到小的顺序排 列，每次可以交换任意两个元素，最少需要交换（ ）次

{{ select(12) }}

• $4$
• $5$
• $6$
• $7$

第 13 题

$3$ 名男生和 $3$ 名女生围成一个圈，男生和男生不相邻，女生和女生不相邻。 如果两个围成的圈经过旋转可以重合，则视为同一种方案。请问一共有几种 方案？

{{ select(13) }}

• $18$
• $15$
• $12$
• $9$

第 14 题

以下关于 C++字符串的说法，错误的是（ ）。

{{ select(14) }}

• 定义 $string$ 类型的字符串时，不需要预先确定它的最大长度。
• 字符数组和 $string$ 类型的字符串是可以相互转化的。
• 定义字符数组 $char$ $a[100]$ 时并从键盘读入字符串，则读入的字符串长度不能超过$99$。
• 定义一个字符串 $string$ $s$ 后，获得它长度的方式就是$strlen(s)$。

第 15 题

中国计算机协会成立于（ ）年。

{{ select(15) }}

• $1961$
• $1962$
• $1971$
• $1972$

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

1.

1 #include <iostream>
2 using namespace std;
3 const int MAXN = 1000050;
4 int n, a[MAXN], a1[MAXN], b[MAXN], lim;
5 void solve1() {
6 for (int i = 1; i <= n; i++)
7 b[a[i]]++; //（1）
8 for (int i = 1; i <= lim; i++) {
9 if (b[i]) //（2）
10 cout << i << " ";
11 }
12 cout << endl;
13 }
14 void solve2() {
15 int cnt = 0, flag;
16 for (int i = 1; i <= n; i++) {
17 flag = false;
18 for (int j = 1; j <= n - 1; j++) {
19 if (a[j] > a[j + 1]) {
20 swap(a[j], a[j + 1]);
21 cnt++;
22 flag = true;
23 }
24 }
25 //if (flag==false)
26 // break;
27 }
28 for (int i = 1; i <= n; i++)
29 cout << a[i] << " ";
30 cout << endl;
31 }
32 int main() {
33 cin >> n;
34 for (int i = 1; i <= n; i++) {
35 cin >> a[i];
36 a1[i] = a[i]; //（3）
37 lim = max(a[i], lim); //（4）
38 }
39 solve1();
40 for (int i = 1; i <= n; i++)
41 a[i] = a1[i];
42 solve2();
43 return 0;
44 }

已知，$1 ≤ n ≤ 10 ^{6}$ ,$1 ≤ a_i≤ 𝟏𝟎 ^{6}$ 。完成下面的判断题和单选题：

判断题

1. solve2 函数实现了选择排序。（ ） {{ select(16) }}

• 正确
• 错误

2. $solve1$ 函数的时间复杂度为$𝑂(𝑛 + 𝑉)$，其中$𝑉$ 指的是 $a_i$的最大值。 （ ） {{ select(17) }}

• 正确
• 错误

3. 当输入数据为： 7 2 3 5 7 1 4 6 时，solve2 函数中的变量$cnt$ 最终值为 $9$。（ ） {{ select(18) }}

• 正确
• 错误

4. 若将 $solve2$ 函数中的双斜杠全部移除，不会影响输出结果。（ ） {{ select(19) }}

• 正确
• 错误

单选题

5. 下列哪组数据，会使得 solve1 函数与 $solve2$ 函数的输出结果不 同？（ ）（假设已经输入了$n$ =$8$）。 {{ select(20) }}

• 1 10 100 1000 10000 888 8888 88888
• 6321 158987 16305 68486 50556 847 156505 15610$
• 777 888 999 888 777 888 999 666
• 999993 999994 999995 999996 999997 999998 999999 1000000

6. 若要使得 solve1 和 solve2 函数的输出结果相同，则应当修改程序中 的哪一处？ {{ select(21) }}

• $(1)$
• $(2)$
• $(3)$
• $(4)$

2.

1 #include <cstdio>
2 #include <cstring>
3 
4 const int maxn = 1003;
5 
6 int type, n, m;
7 char s[maxn], t[maxn];
8 
9 int main() {
10 scanf("%d %s %s", &type, t, s);
11 n = strlen(s); m = strlen(t);
12 if (type < 2) {
13 for (int i = 0; i < m; ++i) s[i] = t[i];
14 } else if (type == 2) {
15 strcpy(s, t);
16 // 提示：如果此时调用 printf("%s\n", s)，则本次输出结果为整
个 t 字符串和换行，没有其他字符。
17 } else {
18 for (int i = 0; i < m; i += 4) {
19 unsigned int code = 0, pos = i;
20 for (int j = 1; pos < i+4; j*=100, ++pos) {
21 if (pos == m) break;
22 code += t[pos] * j;
23 }
24 pos = i;
25 while (code != 0) {
26 s[pos++] = code % 100;
27 code /= 100;
28 }
29 }
30 }
31 for (int i = 0; i < n; ++i) printf("%c", s[i]);
32 printf("\n");
33 }

输入保证 $t$ 的长度不大于 $s$的长度，且两字符串均只含有大小写字母， 不是空串，$type$ = $1,2,3$，完成下面的判断题和单选题：

判断题

1. 将程序中所有的小于号 $(<)$ 改为不等于号 $(!=)，$则程序对所有符合 要求的输入的输出结果不变。 （ ） {{ select(22) }}

• 正确
• 错误

2. 当输入为 $1$ $xyz$ $abcd$ 时，程序的输出为 $xyzd$。 （ ） {{ select(23) }}

• 正确
• 错误

3. 程序在输入为 $1$ $xyz$ $abcd$ 时的输出与输入为$2$ $xyz$ $abcd$ 的输出相同。（ ） {{ select(24) }}

• 正确
• 错误

4. 将程序第 $25~28$ 行的 $while$ 循环替换为 $do-while$ 循环（判断条件 和循环体不变），则程序对同一合法输入的输出结果一定不变。 {{ select(25) }}

• 正确
• 错误

单选题

5. （2 分）若将程序第 13 行改为 for (int i = 0; i < strlen(t); ++i) s[i] = t[i];，且已知输入的 $type$一定为 $1$ 的情况下，用 $𝑛$ 表示$𝑠$ 的长度，$𝑚$ 表示 $𝑡$的长度，则程序的时间复杂度为（ ）。 {{ select(26) }}

• $Θ(𝑛 + 𝑚)$
• $Θ(𝑛 + 𝑚^{2} ）$
• $Θ(𝑛^{2} + 𝑚)$
• $Θ(𝑛^{2} + m^{2} )$

6. 给程序分别输入选项 ( ) 的两组输入数据，得到的输出不同。 {{ select(27) }}

• $1$　$ab$　$abc$和 $3$　$ab$　$abc$
• $1$　 $AB$　 $ABC$ 和 $3$　$AB$　$ABC$
• $1$　 $de$　 $fgh$ 和 $3$　$de$　$fgh$
• $1$　 $DE$　 $FGH$ 和 $3$　$DE$　$FGH$

3.

1 #include <iostream>
2 using namespace std;
3 
4 const int INF = 1000000000;
5 #define Front 0
6 #define Back 1
7 #define Left 2
8 #define Right 3
9 #define Up 4
10 #define Down 5
11 int w[6], a[1003][1003];
12 const int way1[] = {Up, Right, Down, Left};
13 const int way2[] = {Up, Front, Down, Back};
14 const int way3[] = {Left, Front, Right, Back};
15 int get_max(int &a, int b) {
16 return a = max(a, b);
17 }
18 int right_rotate(int &u) {
19 for (int i = 0; i < 4; ++ i)
20 if (u == way1[i])
21 return u = way1[(i + 1) % 4];
22 return u;
23 }
24 int front_rotate(int &u) {
25 for (int i = 0; i < 4; ++ i)
26 if (u == way2[i])
27 return u = way2[(i + 1) % 4];
28 return u;
29 }
30 const int anchorX = Up;
31 const int anchorY = Front;
32 const int anchorZ = Right;
33 int find_down(int u, int v) {
34 if (u == Down || u == Up) return anchorX ^ (u == Up);
35 if (v == Down || v == Up) return anchorY ^ (v == Up);
36 for (int i = 0; i < 4; ++ i)
37 if (u == way3[i])
38 return anchorZ ^ (v == way3[(i + 1) % 4]);
39 return -1;
40 }
41 int n, m, dp[1003][1003][6][6];
42 int main() {
43 cin >> n >> m;
44 for (int i = 0; i < n; ++ i)
45 for (int j = 0; j < m; ++ j)
46 cin >> a[i][j];
47 for (int i = 0; i < 6; ++ i)
48 cin >> w[i];
49 for (int i = 0; i < n; ++ i)
50 for (int j = 0; j < m; ++ j)
51 for (int a = 0; a < 6; ++ a)
52 for (int b = 0; b < 6; ++ b)
53 dp[i][j][a][b] = -INF;
54 dp[0][0][anchorX][anchorY] = a[0][0] * w[Down];
55 for (int i = 0; i < n; ++ i)
56 for (int j = 0; j < m; ++ j)
57 for (int p = 0; p < 6; ++ p)
58 for (int q = 0; q < 6; ++ q)
59 if (dp[i][j][p][q] != -INF) {
60 int x = dp[i][j][p][q];
61 int u1 = p, v1 = q;
62 right_rotate(u1);
63 right_rotate(v1);
64 get_max(dp[i][j + 1][u1][v1],
65 x + w[find_down(u1, v1)] * a[i][j + 1]);
66 int u2 = p, v2 = q;
67 front_rotate(u2);
68 front_rotate(v2);
69 get_max(dp[i + 1][j][u2][v2],
70 x + w[find_down(u2, v2)] * a[i + 1][j]);
71 }
72 int ans = -INF;
73 for (int p = 0; p < 6; ++ p)
74 for (int q = 0; q < 6; ++ q)
75 ans = max(ans, dp[n - 1][m - 1][p][q]);
76 printf("%d\n", ans);
77 return 0;
78 }

以下程序的输入数据的绝对值均不超过$𝟏𝟎^{3}$

𝟑。完成下面的判断题和单选题：

判断题

1. 存在一种合法的输入数据，使得运行程序时，某次 $find$_$down$ 函数的 返回值是 $-1$。( ) {{ select(28) }}

• 正确
• 错误

2. 该程序的时间复杂度为 $Θ(𝑛^{2}𝑚^{2} )$。( ) {{ select(29) }}

• 正确
• 错误

3. 对于任意$𝑢$ ∈ $[0,6)$，「先执行 front_rotate(u)，再执行 right_rotate(u)」，与「先执行right_rotate(u)，再执行 front_rotate(u)」，最终 𝑢 的值相同。( ) {{ select(30) }}

• 正确
• 错误

单选题

4. 将 $anchorX$、$anchorY$、$anchorZ$ 依次更换为（ ）时，对于全部合法 数据，与改变之前的输出结果无异。 {{ select(31) }}

• $Left$、$Front$、$Down$
• $Left$、$Up$、$Front$
• $Left$、$Down$、$Back$
• $Down$、$Right$、$Front$

5. （2 分）对于以下的输入数据，输出结果为 （ ）。

5 5
2 8 15 1 10
5 19 19 3 5
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1 1

{{ select(32) }}

• $95$
• $97$
• $94$
• $103$

6. （2 分）对于以下的输入数据，输出结果为 （ ）。

2 5
2 8 15 3 10
5 19 19 3 5
1 2 3 4 5 6

{{ select(33) }}

• $194$
• $157$
• $193$
• $201$

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

1. （支付问题）有 $n$ 种纸币，其中第 $i$ 种纸币的面值为 $a_i$ 元。每种纸币只 有一张。求能支付多少种金额（不包括 $0$ 元）。数据范围满足 $n≤200$， $a_i$ 的总和不超过 $5000$。 试补全程序。

1 #include <iostream>
2 
3 using namespace std;
4 
5 const int MAXN = 210;
6 const int MAXM = 5010;
7 int n, m;
8 int f[MAXM], a[MAXN];
9 
10 int main() {
11 cin >> n;
12 for (int i = 1; i <= n; i++) {
13 cin >> a[i];
14 (1);
15 }
16 (2);
17 for (int i = 1; i <= n; i++)
18 (3)
19 f[j] = (4);
20 int ans = 0;
21 for (int i = 1; i <= m; i++)
22 if (5) ans++;
23 cout << ans;
24 return 0;
25 }

1)$(1)$ 处应填（ ）。 {{ select(34) }}

• n += a[i]
• m += a[i]
• n = a[i]
• m = a[i]

2)$(2)$ 处应填（ ）。 {{ select(35) }}

• $f[0] = 1$
• $f[1] = 1$
• $a[0] = 1$
• $a[1] = 1$

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

• $for (int j = a[i]; j <= n; j++)$
• $for (int j = n; j >= a[i]; j--)$
• $for (int j = a[i]; j <= m; j++)$
• $for (int j = m; j >= a[i]; j--)$

4. (4)处应填（ ）。

{{ select(37) }}

• $f[j - 1] + 1$
• $f[j - a[i]] + 1$
• $f[j] || f[j - a[i]]$
• $f[j]$ && $f[j - a[i]]$

5. (5) 处应填（ ）。

{{ select(38) }}

• $f[i]$
• $f[i - 1]$
• $f[i] == f[i + 1]$
• $f[i] == f[i - 1]$

2. （凑出 $17$）给定 $n$($1$ ≤$n$ ≤ $20$) 个互不相同的正整数 $a_1$, $a_2$, … $a_n$ (1 ≤$a_i$ ≤$10^{9}$)，将之排成一行。你需要在每个 $a_i$前加上一个加号(+)或减号(-)，使这 $n$ 个数字组成一个算式。请问是否存在一种添加符号的方案，使该算式的值为 $17$？如果存在，请输出 $Yes$，否则输出 $No$。

例如，给定$n$ = $5$, $a_1$ = 1, $a_2$ = 4, $a_3$ = 5, $a_4$ = 9, $a_5$ = 8,则 -$a_1$-$a_2$+$a_3$+$a_4$+$a_5$ = 17。

提示：使用穷举法解决这个问题。

试补全程序。

1 #include <cstdio>
2 
3 using namespace std;
4 
5 const int maxn = 25;
6 const int aim = 17;
7 
8 int n;
9 int a[maxn];
10 bool ans;
11 
12 int getBit(const int s, int p) {
13 return (1);
14 }
15 
16 int main() {
17 scanf("%d", &n);
18 for ((2)) scanf("%d", a + i);
19 for (int s=0, upperBound = (3); s <= upperBound; ++s) {
20 (4);
21 for (int j = 0; j < n; ++j) if (getBit(s, j) == 1) {
22 sum += a[j];
23 } else {
24 (5);
25 }
26 if (int(sum) == aim) {
27 ans = true;
28 break;
29 }
30 }
31 printf("%s\n", ans ? "Yes" : "No");
32 }

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

• (s >> p) & 1
• (s << p) & 1
• s & (1 << p) & 1
• s & (1 >> p) & 1$

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

• $int$　$i$ = 0; i <= n; ++$i$
• $int$　$i$ = 1; i <= n; ++$i$
• $int$　$i$ = 0; i < n; ++$i$
• $int$　$i$ = 1; i < n; ++$i$

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

• $1 << n$
• $(1 << n) | 1$
• $(1 << n) + 1$
• $(1 << n) -1$

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

• $int$　 $sum$ = $0$
• unsigned　 long 　long　 sum = 0
• $unsigned$　 $short$　 $sum$ = $0$
• $unsigned$　 $int$　 $sum$ = $0$

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

• $sum = a[j] + sum$
• $sum = a[j] - sum$
• $sum = -a[j] + sum$
• $sum = -a[j] - sum$