CSP-J 初赛模拟题

（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 >> 1
• x | x – 1
• x ^ 1

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

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

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

1. p -> pre -> nxt = s;
2. p -> pre = s;
3. s -> pre = p -> pre;
4. s -> nxt = p; {{ select(3) }}

• 4 3 1 2
• 4 3 2 1
• 2 1 4 3
• 2 1 3 4

4. 有 $4$ 个不同的盒子，编号为 $1\sim 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) }}

• $1011\ 1111$
• $1100\ 0001$
• $1100\ 0000$
• $1100\ 0101$

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(n\log n)$
• $O(n)$
• $O(\log n)$

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 
04 int n;
05 const int N = 16;
06 int f[1 << N], g[1 << N];
07 
08 int main() {
09   cin >> n;
10   for (int i = 1; i < (1 << n); i++) {
11       f[i] = f[i ^ (i & -i)] + 1;
12   }
13   for (int i = 1; i < (1 << n); i++) {
14      for (int j = i; j; j = i & (j – 1)) {
15         g[i] = max(g[i],  g[j] + 1);
16      }
17   }
18   cout << f[n] << ' ' << g[n] <<endl;
19   return 0;
20 }

假设输入的所有数都是不超过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(n\cdot 2^n)$)
• $O(2^n)$
• $O(3^n)$
• $O(4^n)$

26. 若输入 $10$，则输出是（ ）？ {{ select(26) }}

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

阅读程序第三题

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

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

判断题

27. 第 $31$ 行的 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$

三、 完善程序（单选题，每小题 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\leq N,M\leq 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)%=n

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