该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2026 CSP-J/S 初赛模拟题三

说明： s组训练需做附加题，j组不做附加题

一、单项选择题

• 共 15 题，每题 2 分，共计 30 分
• 每题有且仅有一个正确选项

1. $(2025)_8 + (2025)_{16}$ 与以下哪个选项相等（ ）。 {{ select(1) }}

• A. $(9244)_{10}$
• B. $(210022)_4$
• C. $(10010000111010)_2$
• D. $(234A)_{16}$

2. 以下（ ）函数声明是合法的。 {{ select(2) }}

• A. int Bubblesort(char a[][n], int n)
• B. int Bubblesort(char a[10][], int n)
• C. int Bubblesort(char a[][20], int n)
• D. int Bubblesort(char [][], a, int n)

3. 设循环队列中数组的下标范围是 $0 \sim n-1$，其头尾指针分别为 $f$ 和 $r$，则其元素个数为（ ）。 {{ select(3) }}

• A. $r - f$
• B. $r - f + 1$
• C. $(r - f)$
• D. $(r - f + n)$

4. 后缀表达式 1 2 + 3 * 14 7 / - 对应的前缀表达式为（ ）。 {{ select(4) }}

• A. 1 + 2 * 3 - 14 / 7
• B. - * 1 + 2 3 / 14 7
• C. - * + 1 2 3 / 14 7
• D. - 1 + 2 * 3 14 / 7

5. 给定一棵二叉树，其前序遍历结果为 abdecfg，中序遍历结果为 deb acfg，则这棵树的后序遍历结果为（ ）。 {{ select(5) }}

• A. edbgfca
• B. edgbfca
• C. debgfca
• D. dbegfca

6. 下列关于数据结构的说法的法不正确的是（ ）。 {{ select(6) }}

• A. 数据结构是带有结构的数据元素的集合
• B. 线性表的顺序存储结构优于链式存储结构
• C. 队列是一个先进先出的线性表
• D. 队列只能在一端插入，另一端删除的线性表

7. 已知无向图 G 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。G 所含的顶点个数至少是（ ）。 {{ select(7) }}

• A. 10
• B. 11
• C. 13
• D. 15

8. 下面关于指针的说法正确的是（ ）。 {{ select(8) }}

• A. 在 64 位计算机中一个指针变量占 4 字节
• B. 指针运算实际上是指地操作，只能取地址和间接访问，不能进行加减运算
• C. 数组名不是指向数组首元素的指针变量
• D. 指针可以以静态申请内存空间

9. 方程 $a \times b = (a\ \mathrm{or}\ b) \times (a\ \mathrm{and}\ b)$，在 $a, b$ 取 $[0, 31]$ 中的整数时，共有（ ）组解。 {{ select(9) }}

• A. 32
• B. 256
• C. 454
• D. 512

10. 双向链表中有两个指针域，llink 和 rlink，分别指向前驱及后继。设 $p$ 指向链表中的一个结点，$q$ 指向一待插入结点，现要求在 $p$ 前插入 $q$，则正确的操作为（ ）。 {{ select(10) }}

• A. p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink;
• B. q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink;
• C. p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q;
• D. q->rlink = p; p->rlink = q; q->llink = p; q->rlink = q;

11. 将 $2, 6, 10, 17$ 分别存储到某个地址区间为 $0 \sim 10$ 的哈希表中，如果哈希函数 $h(x) =$（ ）时不会产生冲突，其中 $a\ \mathrm{mod}\ b$ 表示 $a$ 除以 $b$ 的余数。 {{ select(11) }}

• A. $x\ \mathrm{mod}\ 11$
• B. $x^2\ \mathrm{mod}\ 11$
• C. $(2x)\ \mathrm{mod}\ 11$
• D. $\lfloor \sqrt{x} \rfloor\ \mathrm{mod}\ 11$

12. 输入有 $n$ 个不等的数据组成的数组 $a$，输出 $a$ 中第二小的数。在最坏的情况下，该算法需要做（ ）次比较。

if (a[1] < a[2])
{
    min1 = a[1];
    min2 = a[2];
}
else
{
    min1 = a[2];
    min2 = a[1];
}
for(int i = 3; i <= n; i++)
    if (a[i] < min2)
        if (a[i] < min1)
        {
            min2 = min1;
            min1 = a[i];
        }
        else
        {
            min2 = a[i];
        }

{{ select(12) }}

• A. $2n - 1$
• B. $2n - 2$
• C. $2n - 3$
• D. $2n$

13. 整型数组 $a$ 中有 $n$ 个元素，能计算 $a$ 中有多少个数字大于 lower 且小于 upper 的函数，应该将下列线次替换为（ ）。

int solve(int a[], int n, int lower, int upper)
{
    std::sort(a, a + n);
    auto begin = std::___________(a, a + n, lower);
    auto end = std::____________(a, a + n, upper);
    return end - begin;
}

{{ select(13) }}

• A. lower_bound, lower_bound
• B. lower_bound, upper_bound
• C. upper_bound, lower_bound
• D. upper_bound, upper_bound

14. 若 $f_0 = 0, f_1 = 1, f_{n+1} = \frac{f_n + f_{n-1}}{2}$，则随着 $i$ 的增大，$f_i$ 将接近于（ ）。 {{ select(14) }}

• A. $\frac{1}{2}$
• B. $\frac{2}{3}$
• C. $\frac{\sqrt{5} - 1}{2}$
• D. $1$

15. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。 {{ select(15) }}

• A. 6
• B. 7
• C. 8
• D. 9

二、阅读程序

• 判断题 1 分，选择题 3 分，共计 40 分
• 判断题正确填 T，错误填 F

第 1 题

using i64 = long long;
i64 f(i64 n)
{
    i64 s = 1;
    i64 i = 2;
    while (1 * i < n)
    {
        if (n % i == 0) {
            s *= i;
            n /= i;
        }
        else ++i;
    }
    if (i * i == n) s *= i;
    return s;
}

判断题

16. 当 $n = 1$ 时，函数返回 $1$（ ）。 {{ select(16) }}

• A. 正确
• B. 错误

17. 当 $n$ 是质数时，函数返回 $n$（ ）。 {{ select(17) }}

• A. 正确
• B. 错误

18. 存在两个数 $n \ne m$ 且 $f(n) = f(m)$（ ）。 {{ select(18) }}

• A. 正确
• B. 错误

19. 程序的时间复杂度为 $\Theta(\log n)$（ ）。 {{ select(19) }}

• A. 正确
• B. 错误

选择题

20. $f(100)$ 含义进入 while 循环次数是（ ）。 {{ select(20) }}

• A. 7
• B. 8
• C. 9
• D. 10

21. 运行 $f(1024)$ 时，返回值是（ ）。 {{ select(21) }}

• A. 512
• B. 1023
• C. 1024
• D. 2047

第 2 题

int solve(int n, int a[])
{
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int sum = 0;
            for (int k = j; k <= i; ++k)
            {
                sum += a[k];
            }
            ret += sum;
        }
    }
    return ret;
}

判断题

22. 若在进入 solve 函数执行其他操作之前，先对 $a[]$ 排序，则返回值不变（ ）。 {{ select(22) }}

• A. 正确
• B. 错误

23. 当 $n = 1$ 时，函数返回值为 $a[0]$（ ）。 {{ select(23) }}

• A. 正确
• B. 错误

24. 若数组 $a[]$ 中所有元素均为 $0$，则当 $n$ 取 $1$ 到 $100$ 之间的整数时，函数一定返回 $0$（ ）。 {{ select(24) }}

• A. 正确
• B. 错误

选择题

25. 若 $n = 10$ 且 $a = 1, 1, ..., 1, 1$，程序的返回值是（ ）。 {{ select(25) }}

• A. 10
• B. 100
• C. 165
• D. 210

26. 若 $n = 5$，且 $a = 3, 1, 4, 1, 5$，则程序返回（ ）。 {{ select(26) }}

• A. 14
• B. 75
• C. 78
• D. 80

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

• A. $\Theta(n)$
• B. $\Theta(n^2)$
• C. $\Theta(n^2 \cdot \log n)$
• D. $\Theta(n^3)$

28. 如果打算用更好的算法实现 solve 函数，那么最好的算法可以达到的时间复杂度为（ ）。 {{ select(28) }}

• A. $\Theta(n)$
• B. $\Theta(n^2)$
• C. $\Theta(n^2 \cdot \log n)$
• D. $\Theta(\log n)$

第 3 题

using i64 = long long;
i64 solve1(i64 n)
{
    std::vector<i64> c(n);
    c[0] = 0;
    i64 sum = 0;
    for (i64 i = 1; i < n; ++i)
    {
        c[i] = c[i / 2] + (i % 2);
        sum += c[i];
    }
    return sum;
}

std::pair<i64,i64> solve2(i64 n)
{
    if (n == 0)
        return {0, 0};
    auto r = n % 2;
    auto q = n / 2;
    auto [s, c] = solve2(q);
    if (r == 1)
        return {s*2 + q + c, c + 1};
    else
        return {s*2 + q, c};
}

判断题

29. solve1(5) 返回 $5$（ ）。 {{ select(29) }}

• A. 正确
• B. 错误

30. solve2(8) 返回 $[10, 1]$（ ）。 {{ select(30) }}

• A. 正确
• B. 错误

31. 若输入参数 $n$ 在 $0$ 到 $1024$ 之间，则 solve1(n) 的返回值与 solve2(n) 的第一项返回值必定相等（ ）。 {{ select(31) }}

• A. 正确
• B. 错误

选择题

32. solve1(n) 计算的是（ ）。 {{ select(32) }}

• A. $0$ 到 $n - 1$ 之间，全体二进制的数 0 出现的数量
• B. $0$ 到 $n - 1$ 之间，全体二进制的数 1 出现的数量
• C. $0$ 到 $n$ 之间，全体二进制的数 0 出现的数量
• D. $0$ 到 $n$ 之间，全体二进制的数 1 出现的数量

33. solve2(n) 的第二个返回值，计算的是（ ）。 {{ select(33) }}

• A. 参数 $n$ 的二进制长度
• B. 参数 $n$ 的十进制长度
• C. 参数 $n$ 的在二进制表示下，0 的数量
• D. 参数 $n$ 的在二进制表示下，1 的数量

34. solve1 及 solve2 的时间复杂度是（ ）。 {{ select(34) }}

• A. $\Theta(n)$, $\Theta(n)$
• B. $\Theta(n)$, $\Theta(\log n)$
• C. $\Theta(\log n)$, $\Theta(n)$
• D. $\Theta(\log n)$, $\Theta(\log n)$

35. solve1(4096) 的返回值等于（ ）。 {{ select(35) }}

• A. $4096 \times 5$
• B. $4096 \times 6$
• C. $2048 \times 5$
• D. $2048 \times 6$

三、完善程序

• 单选题，每小题 3 分，共计 30 分

第 1 题

两人进行 $N$ 次石头剪刀布游戏，给定对方的出拳序列，由 $R, P, S$ 组成（分别表示石头、剪刀、布）。你的出拳需满足：

• 从未输过（每次非赢即平）。
• 相邻两次出拳不同。

求可能赢的最大对局数（即赢的次数，平局不计入）。

#include<iostream>
int score(int a, int b){
    if(____(1)____) return 0;
    else if(a=='R' and b=='S')return 1;
    else if(____(2)____)return 1;
    else if(a=='P' and b=='R')return 1;
    else return -1000000;
}
int main(){
    int N;
    int n;
    std::cin>>n;
    while(n-->0){
        char c;
        std::cin>>c;
        int newR = ____(4)____;
        int newS = ____(5)____;
        int newP = ____(6)____;
        R=newR;
        S=newS;
        P=newP;
    }
    std::cout<< ____(7)____;
}

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

• A. a != b
• B. a < b
• C. a > b
• D. a == b

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

• A. a=='S' and b=='P'
• B. a=='S' and b=='R'
• C. a=='P' and b=='S'
• D. a=='R' and b=='P'

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

• A. char R,S,P
• B. char R = 'R', S = 'S', P = 'P'
• C. int R = 0, S = 0, P = 0
• D. int R = 'R', S = 'S', P = 'P'

39. (4)(5)(6) 处应填（ ）。 {{ select(39) }}

• A. score(R,c), score(S,c), score(P,c)
• B. score('R',c), score('S',c), score('P',c)
• C. R + score('R',c), S + score('S',c), P + score('P',c)
• D. std::max(S,P)+score('R',c), std::max(R,P)+score('S',c), std::max(R,S)+score('P',c)

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

• A. std::min({std::min(R,S),P})
• B. std::max({std::max(R,S),P})
• C. n - std::min({std::min(R,S),P})
• D. n - std::max({std::max(R,S),P})

第 2 题

给定 $n$ 根火柴的长度 $a_1, a_2, \ldots, a_n$，请用这些火柴围成一个面积最大的三角形。注意所有的火柴都必须用上，不得丢弃。输出最大三角形的面积。假设最大面积积为 $x$，则输出 $16x^2$，$1 \le a_i \le 40$。数据保证至少有一种方案可以围成三角形。

#include<iostream>
using i64 = long long;
int n;
int a[40];
bool mem[40][40*40][40*40];
i64 value[40][40*40][40*40];

i64 solve(int i, int x, int y, int z) {
    if (i < n) {
        if (mem[____(1)____] > 0) return value[____(2)____];
        mem[____(3)____] = 1;
        auto s1 = solve(i+1, x, y, z + a[i]);
        auto s2 = solve(i+1, x + a[i], y, z);
        auto s3 = solve(i+1, x, y + a[i], z);
        return value[____(4)____] = max({s1, s2, s3});
    }
    if (____(6)____) return 0;
    if (i64 p = ____(7)____; p <= 0)
        return ____(8)____;
    return p;
}

int main()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::cout << solve(0, 0, 0, 0);
}

41. (1)、(2)、(3)、(4) 处应填（ ）。 {{ select(41) }}

• A. [i][x][y],[i][x][y],[i][x][y],[i][x][y]
• B. [i][x][y],[x][y][i],[i][x][y],[x][y][i]
• C. [x][y][i],[i][x][y],[x][y][i],[i][x][y]
• D. [x][y][i],[x][y][i],[x][y][i],[x][y][i]

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

• A. s1 + s2 + s3
• B. std::max({s1, s2, s3}.begin(), {s1, s2, s3}.end())
• C. std::max(std::max(s1, s2), std::max(s3, 2))
• D. std::max({std::max(s1, s2), s3})

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

• A. x + y <= z && x + z <= y && y + z <= x
• B. x + y <= z || x + z <= y || y + z <= x
• C. x + y > z || x + z > y || y + z > x
• D. x + y >= z && x + z >= y && y + z >= x

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

• A. x * y * z
• B. x + y + z
• C. (x + y) / 2
• D. (x + y + z) / 2

45. (8) 处应填（ ）。 {{ select(45) }}

• A. p * (p - 2 * x) * (p - 2 * y)
• B. (p / 2) * (p / 2 - x) * (p / 2 - y) * (p / 2 - z)
• C. p * (p - 2 * x) * (p - 2 * y) * (p - 2 * z)
• D. p * (p - 2 * x) + (p - 2 * y) + (p - 2 * z)

四、附加题

• 判断题 1 分，选择题 3 分，共计 30 分
• 判断题正确填 T，错误填 F

第 1 题

int exp();

int term()
{
    char begin, end;
    std::cin >> begin;
    int t = exp();
    std::cin >> end;
    if (t == 0)
        return 1;
    else
        return t * 2;
}

int exp()
{
    if (std::cin.peek() == '(')
    {
        return term() + exp();
    }
    else
    {
        return 0;
    }
}

int main()
{
    std::cout << exp() << '\n';
}

判断题

46. 输入 (()())()，程序运行结果输出 $3$（ ）。 {{ select(46) }}

• A. 正确
• B. 错误

47. 输入 ((())) 输出 $3$（ ）。 {{ select(47) }}

• A. 正确
• B. 错误

48. 输出 $15$ 的最短输入序列之一是 (((())))()()()（ ）。 {{ select(48) }}

• A. 正确
• B. 错误

选择题

49. 若输入是 (()()()(()))，输出（ ）。 {{ select(49) }}

• A. 16
• B. 18
• C. 20
• D. 22

50. 以下哪个输入对应的输出为 $10$（ ）。 {{ select(50) }}

• A. (((())))()
• B. (((()))()())()
• C. ((())(()(())))
• D. ((()))()()()(()))

51. 若输入字符串 (()((()))())，代码执行过程中 term() 函数被调用的次数是（ ）。 {{ select(51) }}

• A. 4
• B. 5
• C. 7
• D. 8

52. 若输入 (()())((()))()，则 exp() 函数总共被调用的次数是（ ）。 {{ select(52) }}

• A. 7
• B. 9
• C. 13
• D. 15

第 2 题

某个投资者有 $m$ 元钱，有 $n$ 个项目等待他的投资，每个项目只能投资一次。 代码中的一个 pair 表示一个项目。其中第 $i$ 个项目要求先支出成本 $c_i$ 元，待项目完成后，可以收回全部成本，且获得 $p_i$ 元利润，若投资者的钱不足 $c_i$，就没法投资这个项目了。 可以用老项目收回的成本及利润支付新项目的成本。若只能投资 $k$ 个项目，那么投资者最终可以积累多少钱呢。

struct pair
{
    int c;
    int p;
};
int solve(int n, int k, int m, pair a[])
{
    auto compare = [] (pair first, pair second) {
        return ____(1)____;
    };
    std::sort(a, a + n, compare);
    std::priority_queue<int> Q;
    int size = 0;
    while (k > 0) {
        while (____(2)____) {
            Q.push(____(3)____);
        }
        if (____(4)____) {
            ____(5)____;
        }
        k--;
    }
    return m;
}

53. (1) 处应填（ ）。 {{ select(53) }}

• A. first.c < second.c
• B. first.c > second.c
• C. first.p < second.p
• D. first.p > second.p

54. (2) 处应填（ ）。 {{ select(54) }}

• A. size < n && a[size].c <= m
• B. size < n && a[size].c < m
• C. size <= n && a[size].c <= m
• D. size < n || a[size].c <= m

55. (3) 处应填（ ）。 {{ select(55) }}

• A. a[size].p
• B. a[size+1].p
• C. a[size+1].c
• D. a[size].c

56. (4) 处应填（ ）。 {{ select(56) }}

• A. !Q.empty()
• B. Q.empty()
• C. size > 0
• D. k > 0

57. (5) 处应填（ ）。 {{ select(57) }}

• A. m += Q.top(); Q.pop();
• B. m += Q.front(); Q.pop();
• C. m += Q.front().p - Q.front().c;
• D. Q.pop(); m += Q.top();