2026 CSPJ 初赛模拟 3（JH）

本卷共 42 题，总分 100 分，建议用时 90 分钟。

一、单项选择题

共 15 题，每题 2 分，共 30 分。

1. 阅读下面代码，输出结果是？

bool x = false;
cout << x;

{{ select(1) }}

• 0
• 1
• false
• 程序无法通过编译

2. 二进制数 $101011_2$ 与八进制数 $36_8$ 的和对应的十进制值是？

{{ select(2) }}

• 71
• 72
• 73
• 74

3. 阅读下面代码，输出结果是？

int a = 3, b = 4;
cout << (a += b) << " " << a;

{{ select(3) }}

• 7 7
• 7 3
• 3 7
• 3 3

4. 一个队列初始为空，依次执行 push(2), push(5), pop(), push(7)，此时从队首到队尾依次为（ ）。

{{ select(4) }}

• 2 5 7
• 5 7
• 7 5
• 7

5. 在单向链表中，若指针 p 指向某个结点，且 p->next 存在。若要删除 p 后面的直接后继结点，通常应执行哪条语句？

{{ select(5) }}

• p = p->next;
• p->next = p->next->next;
• p->next = p;
• p = p->next->next;

6. 一棵二叉树有 13 个结点，并且每个结点的孩子数只能是 0 或 2，则这棵树有多少个叶子结点？

{{ select(6) }}

• 5
• 6
• 7
• 8

7. 有向无环图包含边 $1\to2,1\to3,2\to4,3\to4$。下面是合法拓扑序的是（ ）。

{{ select(7) }}

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

8. 中缀表达式 $a + (b - c) \times d$ 对应的后缀表达式是？

{{ select(8) }}

• abc-+d*
• ab-cd*+
• abc-d*+
• a+bc-d*

9. 有 4 个字符，其出现频率分别为 $2, 4, 7, 9$。若使用哈夫曼编码，则频率为 2 的字符编码长度为？

{{ select(9) }}

• 1
• 2
• 3
• 4

10. 已知一棵二叉树的前序遍历为 A B D C E，中序遍历为 D B A E C，则其后序遍历为？

{{ select(10) }}

• D E B C A
• D B E C A
• B D E C A
• D B C E A

11. 采用每轮进行一次关键字比较、随后将搜索区间缩小约一半的标准二分查找，对含有 1025 个元素的有序数组查找一个元素，最坏情况下最多比较多少次？

{{ select(11) }}

• 9
• 10
• 11
• 12

12. 下面代码片段的时间复杂度是？

for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= n; j += i)
        cout << i + j << endl;

{{ select(12) }}

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

13. 有 5 名男生和 4 名女生，从中选出 3 人组成小组，要求至少有 2 名女生，共有多少种选法？

{{ select(13) }}

• 30
• 34
• 40
• 44

14. 递归函数定义如下：

f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)+1  (n>=3)

则 $f(5)$ 的值为？

{{ select(14) }}

• 7
• 8
• 12
• 13

15. 下面哪个不能作为 C++ 变量名？

{{ select(15) }}

• sum
• num2026
• return
• _cnt

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填 “✓”，错误填 “✗”。

除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共 40 分。其中第 16 ~ 18 题每题 2 分，第 32 题 4 分。

阅读程序（一）

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;

    while (x) {
        s += x & 1;
        x >>= 1;
    }

    return s;
}

int g(int x) {
    int r = 1;

    while (r * 2 <= x)
        r *= 2;

    return r;
}

int main() {
    int n;
    cin >> n;

    cout << f(n) << " " << g(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 1000000 的正整数。

判断题

16. 当输入为 10 时，程序输出为 2 8。

{{ select(16) }}

• 正确
• 错误

17. 若输入的 $n$ 是 2 的正整数次幂，则 $f(n)$ 的返回值为 $1$。

{{ select(17) }}

• 正确
• 错误

18. 对任意合法输入 $n$，$g(n)$ 的返回值一定是不超过 $n$ 的最大的 2 的幂。

{{ select(18) }}

• 正确
• 错误

单项选择题

19. 当输入为 2026 时，程序输出为？

{{ select(19) }}

• 7 1024
• 8 1024
• 8 2048
• 9 1024

20. 该程序的时间复杂度最准确地表示为？

{{ select(20) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$

阅读程序（二）

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int f(string a, string b) {
    int ans = 0;

    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            int k = 0;

            while (i + k < a.size() && j + k < b.size()
                   && a[i + k] == b[j + k]) {
                k++;
            }

            ans = max(ans, k);
        }
    }

    return ans;
}

bool g(string s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - 1 - i])
            return false;
    }

    return true;
}

int main() {
    string x, y;
    cin >> x >> y;

    cout << f(x, y) << " " << g(x + y) << endl;
    return 0;
}

假设输入的两个字符串只包含小写字母，且长度均不超过 100。

判断题

21. 函数 f 返回两个字符串的最长公共子串长度。

{{ select(21) }}

• 正确
• 错误

22. 若两个输入字符串完全相同，则函数 f 的返回值等于该字符串的长度。

{{ select(22) }}

• 正确
• 错误

23. 函数 g 用于判断字符串是否为回文串。

{{ select(23) }}

• 正确
• 错误

单项选择题

24. 当输入为：

abca bcab

程序输出为？

{{ select(24) }}

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

25. 当输入为：

abc cba

程序输出为？

{{ select(25) }}

• 1 0
• 2 0
• 1 1
• 3 1

26. 设两个输入字符串长度分别为 $n, m$，该程序中函数 f 最坏情况下的时间复杂度为？

{{ select(26) }}

• $O(n + m)$
• $O(nm)$
• $O(nm \log(n + m))$
• $O(nm \min(n, m))$

阅读程序（三）

#include <iostream>
#include <algorithm>
using namespace std;

int a[105], dp[105];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;

        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }

        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
    return 0;
}

假设 $1 \le n \le 100$，输入的所有整数均在 int 范围内。

判断题

27. 该程序求的是最长严格上升子序列长度。

{{ select(27) }}

• 正确
• 错误

28. 若输入的所有数都相等，则程序输出 $n$。

{{ select(28) }}

• 正确
• 错误

29. 程序中的 $dp_i$ 表示以第 $i$ 个数结尾的最长不下降子序列长度。

{{ select(29) }}

• 正确
• 错误

单项选择题

30. 若输入为：

6
3 1 2 2 1 4

程序输出为？

{{ select(30) }}

• 2
• 3
• 4
• 5

31. 若输入为：

7
5 4 3 2 1 1 1

程序输出为？

{{ select(31) }}

• 2
• 3
• 4
• 5

32. 若输入为：

8
2 1 3 2 4 3 5 4

程序输出为？

{{ select(32) }}

• 3
• 4
• 5
• 6

三、完善程序

单项选择题，每题 3 分，共 30 分。

完善程序（一）

下面程序将两个升序数组合并成一个升序数组，请补全程序。

#include <iostream>
using namespace std;

int a[1005], b[1005], c[2010];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= m; i++)
        cin >> b[i];

    int i = 1, j = 1, k = 0;

    while (①) {
        if (②)
            ③;
        else
            c[++k] = b[j++];
    }

    while (i <= n)
        c[++k] = a[i++];

    while (④)
        ⑤;

    for (int t = 1; t <= k; t++)
        cout << c[t] << " ";

    return 0;
}

33. ① 处应填？

{{ select(33) }}

• i <= n || j <= m
• i < n && j < m
• i <= n && j <= m
• i == n && j == m

34. ② 处应填？

{{ select(34) }}

• a[i] <= b[j]
• a[i] >= b[j]
• i <= j
• n <= m

35. ③ 处应填？

{{ select(35) }}

• c[++k] = b[j++]
• c[++k] = a[i++]
• a[++k] = c[i++]
• b[++k] = c[j++]

36. ④ 处应填？

{{ select(36) }}

• i <= n
• i <= m
• j <= m
• j <= n

37. ⑤ 处应填？

{{ select(37) }}

• c[++k] = a[i++]
• c[++k] = b[i++]
• c[++k] = a[j++]
• c[++k] = b[j++]

完善程序（二）

下面程序求两个字符串的最长公共子序列长度，请补全程序。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int dp[105][105];

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    for (int i = 1; i <= ①; i++) {
        for (int j = 1; j <= ②; j++) {
            if (③)
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = ④;
        }
    }

    cout << ⑤ << endl;
    return 0;
}

38. ① 处应填？

{{ select(38) }}

• n - 1
• n
• m
• m - 1

39. ② 处应填？

{{ select(39) }}

• n
• n - 1
• m
• m - 1

40. ③ 处应填？

{{ select(40) }}

• a[i] == b[j]
• a[i - 1] == b[j - 1]
• a[i] != b[j]
• i == j

41. ④ 处应填？

{{ select(41) }}

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

42. ⑤ 处应填？

{{ select(42) }}

• dp[0][0]
• dp[n][0]
• dp[0][m]
• dp[n][m]