2025 CSP-J 初赛模拟试卷（一）

---

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

1. 下列数中最大的数是（ ） {{ select(1) }}

• $\text {(10010101)}_2$
• $(236)_8$
• $(66)_{16}$
• $(142)_5$

2. 微型计算机的以下选项中，（ ）的存取速度最快。 {{ select(2) }}

• 内存储器
• 外存储器
• 高速缓存
• 寄存器

3. 对于中缀表达式 (3 + 5) * 25 - 34 / (7 - 5)的后缀表达式为（ ） {{ select(3) }}

• 3 5 + 25 * 34 7 5 - / -
• 3 5 25 34 7 5 + * - / -
• 3 5 25 + * 34 7 5 - / -
• 3 5 25 + * - 34 / 7 5 -

4. 定义一棵有根树的深度：根节点的深度为 0，其余节点的深度等于该节点的父亲节点的深度 +1.一棵深度为 9 的完全二叉树至少包含（ ）个节点。 {{ select(4) }}

• 511
• 512
• 1023
• 1024

5. 下面程序的时间复杂度为（ ）。

int m, n, s = 0;
cin >> m >> n;
for (int i = 0; i < m; i++)
    for (int j = 1; j <= n; j *= 2)
        s++;

{{ select(5) }}

• $O(m^2)$
• $O(n^2)$
• $O(nm)$
• $O(m\,\log_2\,n)$

6. 下列各排序法中，最坏情况下的时间复杂度最低的是（ ） {{ select(6) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序

7. 已知一棵二叉树的中序遍历为 DEGHFCABI ，后序遍历为 HGFEDCIBA ，则这棵二叉树的前序遍历为（ ） {{ select(7) }}

• ABCDEFGHI
• ACDEFHGBI
• ADCEFGHBI
• ACDEFGHBI

8. 设栈 $S$ 的初始状态为空，若干个元素 {a,b,c,d,e,f} 依次入栈 $S$ ，出栈序列为 {b,d,f,e,c,a} ，根据出栈的序列求栈 $S$ 的最小容量为（ ） {{ select(8) }}

• 2
• 3
• 4
• 5

9. 小明想开个造纸飞机的公司，于是雇了 5 个人。接着他要去购买原材料了，已知一包 A1 纸中有 4 张纸，一张 A1 纸能折 7 架飞机，每位员工要制造 100 架飞机。因为制造飞机需要一个相对安静的环境，所以员工之间不能相互借纸，也不能提前裁纸。但是老板小明可以把一包纸拆开分给员工，以确保分给每个员工的纸张数量是一样的，又尽可能的少用原材料。求小明至少要买（ ）包 A1 纸。 {{ select(9) }}

• 16
• 17
• 18
• 19

10. 中国古代的历史故事“田忌赛马”是大家所熟知的。话说齐王和田忌又要赛马了，他们各派出 10 匹马，每场比赛，输的一方将要给赢的一方 10 两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多（ ）两黄金。第一行的 10 个整数表示田忌的马的速度。第二行的 10 个整数为齐王的马的速度。

田忌的马	100	95	90	85	80	75	70	65	60	55
齐王的马	98	97	92	88	85	81	55	50	44	40

{{ select(10) }}

• 60
• 70
• 80
• 90

11. 设 W=true，X=Y=false，Z=true，以下逻辑运算表达式值为真的是（ ）。 {{ select(11) }}

• W V (Z V Y) ^ X
• W ^ (X V Y V !Z) V !Z
• (W ^ X) V (Y ^ Z V !W)
• (W ^ X V Y) ^ Z

12. 汉诺塔问题：目标是将 A 柱上的盘子移到 C 柱上，但是大的盘子不能放到小的盘子上面。现在规定：A 柱上的盘子只能移到 B 柱，B 只能移到 C，C 只能移到 A。现在 A 柱上有 3 个盘子，要把这些盘子按照上述规则都挪到 C 柱上，每次移动一个盘子，至少要移动（ ）次。 {{ select(12) }}

• 7
• 17
• 21
• 31

13. 有 5 本不同的书放在书架上。现重新摆放，使每本书都不在原来的位置。有（ ）种摆法。 {{ select(13) }}

• 40
• 42
• 44
• 46

14. 字符串 zhangnahz ，本质上不同的子串个数为（ ） {{ select(14) }}

• 40
• 41
• 42
• 43

15. 一棵无向树 $T$ 有 7 片树叶，3 个 3 度顶点，其余顶点均为 4 度，则 $T$ 有（ ）个 4 度节点。

{{ select(15) }}

• 1
• 2
• 3
• 4

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

（1）

01 #include <iostream>
02 using namespace std;
03 int main() {
04     int a, b;
05     cin >> a >> b;
06     int anx = 1;
07     while (b) {
08         if (b & 1)  anx = anx * a;
09         a = a * a;
10         b >>= 1;
11     }
12     cout << anx << endl;
13     return 0;  
14 }

【判断题】

16. 输入 10 10 ，能够正确输出答案。（ ） {{ select(16) }}

• √
• ×

17. 第 06 行的 int anx = 1; ，改成 int anx = 0; 不会影响最终结果。（ ） {{ select(17) }}

• √
• ×

18. 将第 08 行与第 09 行交换位置，不会影响最终结果。（ ） {{ select(18) }}

• √
• ×

19. 将第 10 行改成 b /= 2 ，不会影响最终结果。（ ） {{ select(19) }}

• √
• ×

【选择题】

20. 如果输入的 a = 2 ，下列哪个数字最可能为该程序的输出结果（ ）。 {{ select(20) }}

• 14
• 15
• 16
• 17

21. 如果输入 9 9 ，则输出结果为（ ）。 {{ select(21) }}

• 387420489
• 387420191
• 388420489
• 3774204890

（2）

01 #include <bits/stdc++.h>
02 using namespace std;
03 struct num {
04     int a,b;
05 }
06 void fun(struct num s[], int n) {
07     int index, j, k;
08     struct num temp;
09     for (k = 0; k < n - 1; k++) {
10         index = k;
11         for (j = k + 1; j < n; j++) {
12             if (s[j].b < s[index].b)  index = j;
13         if (index != k) {
14             temp = s[index];
15             s[index] = s[k];
16             s[k] = temp;
17         }
18     }
19 }
20 int main() {
21     int count, i, k, m, n, no;
22     struct num s[100];
23     cin >> n >> m >> k;
24     for (i = 0; i < n; i++) {
25         s[i].a = i + 1;
26         s[i].b = 0;
27     }
28     i = 0;
29     count = no = 0;
30     while (no < n) {
31         if (s[i].b == 0)
32             count++;
33         if (count == m) {
34             no++;
35             s[i].b = no;
36             count = 0;
37         }
38         i++;
39         if (i == n)
40             i = 0;
41     }
42     fun(s, n);
43     printf("%d:%d\n", s[k - 1].b, s[k - 1].a);
44     return 0;
45 }

【判断题】

22. 若输入为 0 0 0 时，程序运行会出错。（ ） {{ select(22) }}

• √
• ×

23. 若输入为 1 2 3 时，则输出为 3:1 。（ ） {{ select(23) }}

• √
• ×

24. 若把第 13 行的 index != k 改为 1 ，不会影响程序运行结果。（ ） {{ select(24) }}

• √
• ×

25. 若去掉第 39 行和第 40 行，不会影响程序输出结果。（ ） {{ select(25) }}

• √
• ×

【选择题】

26. 程序运行时，若输入为 5 4 3 ，则输出为（ ）。 {{ select(26) }}

• 3:5
• 2:3
• 1:2
• 4:1

27. 程序运行时，若输入为 7 5 2 ，则输出为（ ）。 {{ select(27) }}

• 1:5
• 6:1
• 2:3
• 2:4

（3）

01 #include <iostream>
02 using namespace std;
03 long long a[100010], b[100010], ans;
04 void mmm(int L, int R)
05 {
06     if (L == R)  return 0;
07     int mid = (L + R) >> 1;
08     mmm(L, mid);
09     mmm(mid + 1, R);
10     int i = L, j = mid + 1, k = L;
11     while (i <= mid && j <= R)
12     {
13         if (a[i] > a[j])
14         {
15             ans += j - k;
16             b[k++] = a[j++];
17         }
18         else
19             b[k++] = a[i++];
20     }
21     while (i <= mid)  b[k++] = a[i++];
22     while (j <= R)  b[k++] = a[j++];
23     for (i = L; i <= R; i++)  a[i] = b[i];
24 }
25 int main()
26 {
27     int i, n;
28     cin >> n;
29     for (i = 1; i <= n; i++)
30         cin >> a[i];
31     mmm(1, n);
32     cout << ans << endl;
33     return 0;
34 }

【判断题】

28. 去掉第 06 行，程序运行结果相同。（ ） {{ select(28) }}

• √
• ×

29. 第 21 行与第 22 行交换位置，程序运行结果相同。（ ） {{ select(29) }}

• √
• ×

30. 第 07 行改为 int mid = (L + R) / 2; ，程序运行结果相同。（ ） {{ select(30) }}

• √
• ×

31. 该算法的原理是归并排序。（ ） {{ select(31) }}

• √
• ×

【选择题】

32. 该程序的时间复杂度为（ ）。 {{ select(32) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(n\sqrt n)$

33. 若程序输入为 4 3 2 3 2 ，则输出为（ ）。 {{ select(33) }}

• 2
• 3
• 4
• 5

34. （4分）若程序输入为 4 6 5 2 4 ，则执行到第 32 行时，数组 a[] 的数据为（ ）。 {{ select(34) }}

• 6 5 2 4
• 6 5 4 2
• 2 4 6 5
• 2 4 5 6

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

（1）第一行输入一个正整数 $n$ ，第二行输入 $n$ 个整数，判断这些数是否构成等比数列。试补全程序。

01 #include <bits/stdc++.h>
02 using namespace std;
03 int main()
04 {
05     int cur, q, n, pre;
06     cin >> n;
07     _____①_____
08     _____②_____
09     pre = cur;
10     for (int i = 3; i <= n; i++) {
11         cin >> cur;
12         if (_____③_____)
13             break;
14         q = cur / pre;
15         _____④_____
16     }
17     if (_____⑤_____)
18         cout << "Yes" << endl;
19     else
20         cout << "No" << endl;
21     return 0;
22 }

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

• cin >> pre >> cur;
• cin >> pre;
• cin >> cur;
• cin >> cur >> pre;

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

• q = 1;
• q = 0;
• q = cur / pre;
• q = pre / cur;

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

• cur > pre
• cur == pre * q
• cur < pre
• cur != pre * q

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

• cur = pre
• cur = q
• pre = cur
• pre = q

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

• i > n
• i >= n
• i < n
• i <= n

（2）（次大值之和）给定一个 $1$ 到 $n$ 的数字各出现一次的排列 a[1], a[2], …, a[n] ，定义 f(l, r) 表示 a[l], a[l + 1], a[l + 2], …,a[r] 中的次大值，你需要求出对于所有的 $1\le i < j \le n(n\le10^5)$ ， f(i, j) 的和。

输入第一行包含一个整数 $n$ ，第二行 $n$ 个整数表示 a[i] ，输出所有的 f(i, j) 之和。

【样例#1 输入】

3
1 2 3

【样例#1 输出】

5

【样例#2 输入】

8
8 2 7 3 4 5 6 1

【样例#2 输出】

136

提示：采用双向链表方式来存放读入的顺序，分别用数组 pre[] 和 nxt[] 来存放。试补全程序。

01 #include <bits/stdc++.h>
02 #define LL long long
03 using namespace std;
04 const int MAXN = 100005;
05 struct T {
06     int v, id;//v 存放读入元素值，id 存放读入顺序号
07 }x[MAXN];
08 int pre[MAXN], nxt[MAXN];
09 int cmp(T t1, T t2)
10 {
11     return t1.v < t2.v;
12 }
13 void del(int p)
14 {
15     int L = pre[p], r = nxt[p];
16     nxt[L] = r;
17     pre[r] = L;
18 }
19 int main()
20 {
21     int m, n, k;
22     cin >> n;
23     for (int i = 1; i <= n; i++) {
24         cin >> x[i].v;
25         x[i].id = _____①_____;
26         pre[i] = i - 1;
27         nxt[i] = i + 1;
28     }
29     nxt[0] = 1;
30     pre[n + 1] = n;
31     _____②_____;
32     LL ans = 0;
33     for (int i = 1; i <= n; i++) {
34         LL L1, L2, r1, r2;
35         L1 = pre[x[i].id];
36         if (L1)  L2 = pre[L1];
37         else  L2 = -1;
38         r1 = nxt[x[i].id];
39         if (r1 != n + 1)  r2 = nxt[r1];
40         else  r2 = -1;
41         if (L2 != -1)  ans += _____③_____ * i;
42         if (r2 != -1)  ans += _____④_____ * i;
43         del(_____⑤_____);
44     }
45     printf("%lld", ans);
46     return 0;
47 }

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

• -1
• 0
• i
• n

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

• sort(x, x + n)
• sort(x, x + n, cmp)
• sort(x, x + n + 1, cmp)
• sort(x + 1, x + n + 1, cmp)

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

• (L2 - L1) * (L2 - x[i].id)
• (L1 - L2) * (r1 - x[i].id)
• (L1 - L2) * (x[i].id - r1)
• (L2 - L1) * (x[i].id - L1)

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

• (r2 - r1) * (L1 - x[i].id)
• (r1 - r2) * (r1 - x[i].id)
• (r1 - r2) * (x[i].id - r2)
• (r2 - r1) * (x[i].id - L1)

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

• i
• L1
• x[i].id
• r1