2023年图灵编程CSP-J初赛模拟卷6

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

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

• $(1011011101)_2$
• $(11010)_5$
• $(20213)_4$
• $(308)_{16}$

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

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

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]]++; //① 
8       for (int i = 1; i <= lim; i++) { 
9           if (b[i]) //② 
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]; //③ 
37          lim = max(a[i], lim); //④ 
38      } 
39      solve1(); 
40      for (int i = 1; i <= n; i++) 
41          a[i] = a1[i]; 
42      solve2(); 
43      return 0; 
44  }

已知，$𝟏 ≤ 𝒏 ≤ 𝟏𝟎^𝟔, 𝟏 ≤ 𝒂_𝒊 ≤ 𝟏𝟎^𝟔。$完成下面的判断题和单选题：

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

20. 下列哪组数据，会使得 solve1 函数与 solve2 函数的输出结果不同？（ ）（假设已经输入了 𝑛 = 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

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

• ①
• ②
• ③
• ④

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，完成下面的判断题和单选题：

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

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

• $Θ(𝑛 + 𝑚)$
• $Θ(𝑛 + 𝑚^2)$
• $Θ(𝑛^2 + 𝑚)$
• $Θ(𝑛^2 + m^2)$

27. 给程序分别输入选项 ( ) 的两组输入数据，得到的输出不同。 {{ 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

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  }

以下程序的输入数据的绝对值均不超过$10^3$。完成下面的判断题和单选题：

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

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

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

32. （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

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

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          ①;
15      }
16      ②;
17      for (int i = 1; i <= n; i++)
18          ③
19              f[j] = ④;
20      int ans = 0;
21      for (int i = 1; i <= m; i++)
22          if (⑤) ans++;
23      cout << ans;
24      return 0;
25  }

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

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

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

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

36. ③ 处应填（ ）。 {{ 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--)

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

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

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

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

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

例如，给定 𝑛 = 5, $𝑎_1$ = 1, $𝑎_2$ = 4, $𝑎_3$ = 5, $𝑎_4$ = 9, $𝑎_5$ = 8，则 $−𝑎_1 − 𝑎_2 + 𝑎_3 + 𝑎_4 + 𝑎_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 ①;
14  }
15  
16  int main() {
17      scanf("%d", &n);
18      for (②) scanf("%d", a + i);
19      for (int s=0, upperBound = ③; s <= upperBound; ++s) {
20          ④;
21          for (int j = 0; j < n; ++j) if (getBit(s, j) == 1) {
22              sum += a[j];
23          } else {
24              ⑤;
25          }
26          if (int(sum) == aim) {
27              ans = true;
28              break;
29          }
30      }
31      printf("%s\n", ans ? "Yes" : "No");
32  }

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

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

40. ② 处应填（ ）。 {{ 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

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

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

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

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

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

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