CSP-J 2024 初赛模拟05

（语言：C++ 满分：100分 考试时间：120分钟）

一、单项选择题（每题只有一个正确选项，每题2分，共30分）

1. 运行以下代码片段，下列选项中描述正确的是（ ）

int x = 101;
int y = 201;
int *p = &x;
int **q = &p;

{{ select(1) }}

• 将 x 的值赋值为 201
• 将 y 的值赋值为 101
• 将 p 的值赋值为 x
• **q 的值为 101

2. 下面的lowbit(x)函数返回整数在二进制表示下最低位的1和后面所有0对应的整数，换句话说，也就是 x 二进制下最低位的 1 所在的权重，比如 lowbit(5) = 1，lowbit(12) = 4。

int lowbit(x) {
   return______;
}

则可填入横线处的正确代码为（ ）。

{{ select(2) }}

• x & -x
• x & -x1
• x | x - 1
• x ^ 1

3. 假设有一个链表的节点定义如下：

struct node {
  int data;
  node * pre, * nxt;
};

现在有一个双向循环链表，指针p指向双向循环链表中的某一个节点，如果要在p所指向的节点前面插入指针s所指的节点，以下代码正确的执行顺序为 （ ）。

① p -> pre -> nxt = s;

② p -> pre = s;

③ s -> pre = p -> pre;

④ s -> nxt = p;

{{ select(3) }}

• ④③①②
• ④③②①
• ②①④③
• ②①③④

4. 有4个不同的盒子，编号为1-4，其中编号为x的盒子中存在一个编号为x的小球，现在所有小球拿出，在随机放入盒子内，使得每个盒子和其盒子内的小球编号都不相同的方案数为（ ）。

{{ select(4) }}

• 18
• 9
• 16
• 12

5. 在一个具有n个顶点的有向图中，构成强连通图至少有（ ）条边。

{{ select(5) }}

• n-1
• n*(n-1)
• n*n
• n

6. 如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（ ）。

{{ select(6) }}

• 完全图
• 一棵树
• 连通图
• 有环图

7. 十进制数 -63的补码为（ ）。

{{ select(7) }}

• 10111111
• 11000001
• 11000000
• 11000101

8. 已知一棵二叉树的中序遍历为 ADEFGHMZ，后序遍历为 AEFDHZMG，则其前序遍历应该是（ ）。

{{ select(8) }}

• GDEMHAFZ
• MHGFDZAE
• GDAFEMHZ
• AFGEZMHD

9. 已知某表达式的前缀形式为 - * + 3 4 5 6，则其对应的后缀表达式为（ ），其中 +、-、* 是运算符。

{{ select(9) }}

• 3 4 + 5 * 6 -
• 3 4 5 6 + * -
• 3 + 4 * 5 - 6
• 3 4 5 * + 6 -

10. 基于比较的排序算法的时间复杂度的下限为（序列长度为n）（ ）

{{ select(10) }}

• $O(n^2)$
• $O(nlogn)$
• $O(n)$
• $O(logn)$

11. 阅读下列代码片段，其中 sizeof(u) 的值为（ ）

union U {
    bool flag1, flag2, flag3, flag4;
    int a, b, c;
    double d;
    enum E {
        rank1 = 'A', rank2 = 'B', rank3 = 'C'
    } e;
} u;

{{ select(11) }}

• 28
• 27
• 16
• 8

12. 以下关于栈和队列的描述错误的是（ ）

{{ select(12) }}

• 栈的操作方式是先进后出
• 队列的操作方式是先进先出
• 栈只能在栈顶插入删除元素
• 队列若删除元素则只能在队尾进行

13. 字符串ABCCABA有多少个本质不同的子串（ ）

{{ select(13) }}

• 16
• 23
• 35
• 30

14. 十进制数245对应其他进制数中不对的是（ ）

{{ select(14) }}

• 四进制：3311
• 八进制：365
• 十六进制：E5
• 三十二进制：7L

15. 1+ ((2 + 3) * 4) - 5转化成波兰表达式为（ ）

{{ select(15) }}

• + 1 - 5 * + 2 3 4
• + 1 - 5 + * 2 3 4
• - + 1 * 2 3 + 4 5
• - 1 + 5 + 2 3* 4

二、程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

阅读程序第一题（12分）

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 void sswap(int &x, int &y) {
05   for (int i = 31; i >= 0; i--) {
06      int bx = x >> i & 1;
07      int by = y >> i & 1;
08      if (bx ^ by) {
09        x ^= 1 << i, y ^= 1 << i;
10      }
11   }
12 }
13 
14 int main(){
15   int x, y, z;
16   cin >> x >> y >> z;
17   sswap(x, y);
18   sswap(x, z);
19   sswap(y, z);
20   cout << x << ' ' << y << ' ' << z << '\n';
21   return 0;
22 }

判断题

16. 若程序输入 1 2 3，则最终输出为 3 2 1。（ ）

{{ select(16) }}

• 正确
• 错误

17. 若将04行的两个&符号删除，程序输出结果一定不会改变。（ ）（2分）

{{ select(17) }}

• 正确
• 错误

18. 若将头文件#include<bits/stdc++.h>改成#include<stdio.h>，程序仍能正常运行（ ）

{{ select(18) }}

• 正确
• 错误

单选题

19. 若输入 3 6 9，则输出是什么？（ ）

{{ select(19) }}

• 3 9 6
• 6 9 3
• 9 6 3
• 6 3 9

20. 若将第09行改为bx ? y ^= 1 << i : x ^= 1 << i，则输入 3 6 9，输出是什么？（ ）（4分）

{{ select(20) }}

• 15 15 15
• 6 9 3
• 9 12 15
• 6 3 9

阅读程序第二题（12分）

01 #include <bits/stdc++.h>
02 using namespace std;
03 int n;
04 const int N = 16;
05 int f[1<<N], g[1<<N];
06 
07 int main(){
08   cin >> n;
09   for (int i = 1; i < (1 << n); i++) {
10       f[i] = f[i^(i&-i)] + 1;
11   }
12   for (int i = 1; i < ( 1 << n); i++) {
13      for (int j = i; j; j = i & (j – 1)) {
14         g[i] = max(g[i], g[j]+1);
15      }
16   }
17   cout<<f[n]<< ' ' << g[n] <<endl;
18   return 0;
19 }

假设输入的所有数都是不超过15的正整数，完成下面的判断题和单选题。

判断题

21. f和g数组的值不超过n（ ）

{{ select(21) }}

• 正确
• 错误

22. 计算f数组的时间复杂度为 $O(2^n)$（ ）

{{ select(22) }}

• 正确
• 错误

23. 无论输入的n是多少，输出的两个值一定相同。（ ）

{{ select(23) }}

• 正确
• 错误

24. 若把计算g数组的循环的条件改为j>=0，则数组会越界 （ ）

{{ select(24) }}

• 正确
• 错误

单选题

25. 计算g数组的时间复杂度为（ ）

{{ select(25) }}

• $O(n2^n)$
• $O(2^n)$
• $O(3^n)$
• $O(4^n)$

26. 若输入10，则输出是（ ）

{{ select(26) }}

• 1 1
• 1 2
• 2 1
• 2 2

阅读程序第三题（16分）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 vector<int> v[1005];
05 string s;
06 
07 void dfs1(int x) {
08 	printf("%d", x);
09 	for(int i = 0; i < v[x].size(); i++) {
10 		dfs1(v[x][i]);
11 	}
12 }
13 
14 void dfs2(int x) {
15 	for(int i = 0; i < v[x].size(); i++) {
16 		dfs2(v[x][i]);
17 	}
18 	printf("%d", x);
19 }
20 
21 int main() {
22 	cin >> s;
23	s = '(' + s + ')';
24 	stack<int> stk;
25	int ans = 0, cnt = 0;
26 	for(int i = 0; i < s.size(); i++) {
27 		if (s[i] == '(') {
28 			stk.push(++cnt);
29 			ans += stk.size();
30 		} else{
31 			int x = stk.top(); stk.pop();
32 			if(!stk.empty()) {
33 				v[stk.top()].push_back(x);
34 			}
35 		}
36 	}
37 	printf("%d\n", ans);
38 	dfs1(1);
39 	printf("\n");
40 	dfs2(1);
41 	return 0;
42 }

假设程序输入的是一个合法的小括号匹配的序列，长度不超过2000。

判断题

27. 第32行的if语句只可能得到true。（ ）

{{ select(27) }}

• 正确
• 错误

28. 如果s的长度是2n，那么输出的第二行一定是1到n的自然数，按照从小到大的顺序输出。（ ）

{{ select(28) }}

• 正确
• 错误

单选题

29. 如果输入 ()()(()())，那么输出的第一行是：（ ）

{{ select(29) }}

• 13
• 14
• 15
• 16

30. 如果s的长度是20，那么输出的第一行的最大值是：（ ）

{{ select(30) }}

• 45
• 55
• 66
• 78

31. 如果s的长度为100，并且s有且仅有两个子串是"()"，那么输出的第一行的最小值是：（ ）。

{{ select(31) }}

• 699
• 701
• 703
• 705

32. 如果输出的第三行是4 5 3 6 2 7 1，那么输出的第一行可能是（ ）。（4分）

{{ select(32) }}

• 17
• 18
• 19
• 20

三、 程序完善题（共2大题，每个选择题3分，共计30分）

1.题目描述： 小 Z 有一个字符串刷子，他可以将一个字符串中的一个连续子串刷成任意想要的字符组成的子串。例如，有一个字符串 "abcdef"，小 Z 可以将子串 "bcd" 全部刷成 "zzz" 得到字符串 "azzzef"，使用一次刷子需要消耗的代价为1。

小 Y 现在有两个长度相同的字符串 s,t，他想要请小 Z 帮忙，让小 Z 使用刷子将字符串 s 刷成t，问小 Z 消耗的代价最少是多少。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int maxn = 105;
05 int dp[maxn][maxn], f[maxn], n;
06 char s[maxn], t[maxn];
07 
08 int main() {
09     scanf("%s %s", s + 1, t + 1);
10     n = strlen(s + 1);
11     memset(dp, 0x3f, sizeof(dp));
12     memset(f, 0x3f, sizeof(f));
13     for(int i = 1; i <= n; ++i) ①;
14    for(int len = 2; len <= n; ++len) {
15         for(int i = 1; i + len - 1 <= n; ++i) {
16             int j = i + len - 1;
17             if(t[i] == t[j]) {
18                 dp[i][j] = ②;
19                 continue;
20             }
21             for(int k = i; k < j; ++k) { 
22                 dp[i][j] = min(dp[i][j], ③);
23             }
24         }
25     }
26     ④; 
27     for(int i = 1; i <= n; ++i) {
28         f[i] = dp[1][i];
29         if(s[i] == t[i]) f[i] = min(f[i], f[i - 1]);
30         for(int j = 1; j < i; ++j) f[i] = min(f[i], ⑤);
31     }
32     cout<<f[n];
33     return 0;
34 }

33. ①处应填（ ）

{{ select(33) }}

• dp[i][i] = 0
• dp[i][i] = 1
• dp[i][i + 1] = 0
• dp[i][i + 1] = 1

34. ②处应填（ ）

{{ select(34) }}

• min(dp[i + 1][j], dp[i][j - 1])
• max(dp[i + 1][j], dp[i][j - 1])
• dp[i + 1][j - 1] + 2
• dp[i + 1][j - 1] + 1

35. ③处应填（ ）

{{ select(35) }}

• dp[i + 1][k] + dp[k + 1][j]
• dp[i + 1][k - 1] + dp[k][j]
• dp[i][k] + dp[k + 1][j]
• dp[i][k - 1] + dp[k][j]

36. ④处应填（ ）

{{ select(36) }}

• f[0] = 0
• f[0] = 1
• f[1] = 0
• f[1] = dp[1][1]

37. ⑤处应填（ ）

{{ select(37) }}

• dp[i][j] + dp[j + 1][i]
• dp[1][j] + dp[j + 1][i]
• f[j] + dp[j + 1][i]
• f[j] + dp[j][i]

2. 题目描述: 在一个N*M的由非负整数构成的数字矩阵中，你需要取出若干数字，使得取出的任意两个数字不相邻（若一个数字在另一个数字相邻的8个格子中则认为相邻），求取出数字和最大（1<=N,M<=6);

01 #include <bits/stdc++.h>
02 using namespace std;
03 int n, m, a[10][10], vis[10][10];
04 int ans = 0;
05 void dfs(int x, int y, int tot) {
06   if (x > ①) {
07     ans = max(ans, tot);
08     return;
09   }
10   int nx = x, ny = y + 1;
11   if (ny > m) {
12     ②;
13     ny = 1;
14   }
15   bool can = true;
16   for (int dx : {-1, 0, 1}) {
17     for (int dy : {-1, 0, 1}) {
18       if (dx == 0 && dy == 0) continue;
19       if (vis[x + dx][y + dy]) can = false;
20     }
21   }
22   if (can) {
23     vis[x][y] = 1;
24     dfs(nx, ny, tot + ③);
25     vis[x][y] = ④;
26   }
27   dfs(nx, ny, tot);
28 }
29 int main() {
30   cin >> n >> m;
31   for (int i = 1; i <= n; i++)
32     for (int j = 1; j <= m; j++)
33       cin >> a[i][j];
34   dfs(1, ⑤, 0);
35   cout << ans << endl;
36 }

38. ①处应填写（ ）

{{ select(38) }}

• n
• m
• n+1
• m+1

39. ②处应填写（ ）

{{ select(39) }}

• nx=1
• nx++
• nx--
• (nx+1)%=m

40. ③处应填写（ ）

{{ select(40) }}

• 0
• 1
• a[x][y]
• a[nx][ny]

41. ④处应填写（ ）

{{ select(41) }}

• 0
• 1
• a[x][y]
• a[nx][ny]

42. ⑤处应填写（ ）

{{ select(42) }}

• m
• 1
• n
• 2