2026 CSPJ 初赛模拟 4（JH）

本卷共 42 题，总分 100 分，建议用时 90 分钟。判断题选“正确”或“错误”。

一、单项选择题（15 题，每题 2 分，共 30 分）

1. （2 分）通常所说的“冯·诺依曼体系结构”与下列哪位科学家的名字对应？

{{ select(1) }}

• 克劳德·香农
• 戈登·摩尔
• 查尔斯·巴比奇
• 冯·诺依曼

2. （2 分）在计算机内部，数据和指令通常都以哪种形式进行传送、存储和处理？

{{ select(2) }}

• 十进制编码
• 二进制编码
• 拼音编码
• 五笔字型编码

3. （2 分）按 1 GB = 1024 MB、1 MB = 1024 KB 估算，8 GB 的 U 盘大约能存储多少张 500 KB 的照片？

{{ select(3) }}

• 8000
• 16000
• 32000
• 64000

4. （2 分）正整数 1000 的二进制表示（不含前导零）共有多少位？

{{ select(4) }}

• 9
• 10
• 11
• 12

5. （2 分）在字长为 16 位的系统中，一个带符号整数的补码为 1111111111101101，其十进制值是（ ）。

{{ select(5) }}

• 19
• -19
• 18
• -18

6. （2 分）用递归方式实现深度优先搜索时，系统主要借助哪种数据结构保存尚未返回的调用状态？

{{ select(6) }}

• 链表
• 栈
• 队列
• 散列表

7. （2 分）根结点深度为 0。一棵深度为 $n$ 的完全二叉树至少有多少个结点？

{{ select(7) }}

• $2^n-1$
• $2^n+1$
• $2^n$
• $2^{n-1}+1$

8. （2 分）某二叉树的前序遍历为 ABDHECFGJKI，中序遍历为 HDBEAFJGKCI，其后序遍历是（ ）。

{{ select(8) }}

• IKJGFCEHDBA
• HDEBJKGFICA
• ABCDEFGHIJK
• ICKGJFAEBDH

9. （2 分）在比较模型中，对 $n$ 个互异元素排序，以下哪个是最坏情况下所需比较次数的最紧渐近下界？

{{ select(9) }}

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

10. （2 分）用数字 0、1、2、2、3 可以组成多少个不同的五位数？

{{ select(10) }}

• 120
• 60
• 48
• 32

11. （2 分）元素 R1、R2、R3、R4、R5 按此顺序入栈。若第一个出栈的是 R3，则第五个出栈的不可能是（ ）。

{{ select(11) }}

• R1
• R2
• R4
• R5

12. （2 分）前缀表达式 + 3 * 2 + 5 12 的值是（ ）。

{{ select(12) }}

• 23
• 25
• 37
• 65

13. （2 分）双向链表结点含 llink 和 rlink，分别指向前驱和后继。设 p 的前驱、后继均存在，下面删除 p 的语句序列中错误的是（ ）。

{{ select(13) }}

• p->rlink->llink=p->rlink; p->llink->rlink=p->llink; delete p;
• p->llink->rlink=p->rlink; p->rlink->llink=p->llink; delete p;
• p->rlink->llink=p->llink; p->rlink->llink->rlink=p->rlink; delete p;
• p->llink->rlink=p->rlink; p->llink->rlink->llink=p->llink; delete p;

14. （2 分）5 个人排成一排，其中指定的两个人必须相邻，共有多少种排法？

{{ select(14) }}

• 120
• 64
• 48
• 24

15. （2 分）给一个五边形的 5 条边染色，只能使用红、绿、蓝三色，且相邻边不同色，共有多少种染色方法？（5 条边的位置有固定编号；旋转后颜色对应位置不同，视为不同方案。）

{{ select(15) }}

• 24
• 28
• 30
• 32

二、阅读程序（17 题，共 40 分）

阅读程序（一）

输入整数 $n,m$，满足 $1\le n\le m\le10^9$。阅读以下程序，回答问题。

#include <iostream>
using namespace std;

int rSum(int x) {
    int result = 0;
    while (x != 0) {
        result = result * 10 + x % 10;
        x /= 10;
    }
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = n; i < m; ++i)
        if (i == rSum(i)) cout << i << ' ';
    return 0;
}

16. （2 分）对循环中任意一次取到的正整数 i，恒有 rSum(i) >= i。

{{ select(16) }}

• 正确
• 错误

17. （2 分）把 rSum 中的循环条件由 x != 0 改为 x >= 0，程序会出错。

{{ select(17) }}

• 正确
• 错误

18. （2 分）若输入的 n 等于 m，程序一定没有输出。

{{ select(18) }}

• 正确
• 错误

19. （3 分）若希望程序输出的最后一个数字是 99，输入的 m 有多少种可能？（假设 n<=99）

{{ select(19) }}

• 2
• 3
• 11
• 12

20. （3 分）输入 1000 2000 时，程序会输出多少个数字？

{{ select(20) }}

• 20
• 9
• 10
• 11

阅读程序（二）

输入整数 $1\le n\le49$。全局数组初值为 0。阅读以下程序，回答问题。

#include <cstdio>
using namespace std;

const int MAXN = 50;
const int MOD = 2009;
int c[MAXN][MAXN];

int main() {
    int n;
    scanf("%d", &n);
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        c[i][i] = 1;
    }
    int s = 0;
    for (int i = 0; i <= n; ++i) s = (s + c[n][i]) % MOD;
    printf("%d\n", s);
    return 0;
}

21. （1.5 分）当 n 足够大时，对任意合法的 i,j 都有 c[i][j] >= c[i][j-1]。

{{ select(21) }}

• 正确
• 错误

22. （1.5 分）固定 j 后，i 越大，c[i][j] 就一定越大。

{{ select(22) }}

• 正确
• 错误

23. （1.5 分）对任意整数 $x$，$3<x\le10$，以及任意 $1\le i\le x-1$，$\gcd(c[x][i],x)>1$。

{{ select(23) }}

• 正确
• 错误

24. （3 分）输入 10，程序完成杨辉三角构造后，数组 c 中出现的最大值是（ ）。

{{ select(24) }}

• 120
• 188
• 252
• 320

25. （3 分）输入 11，程序输出（ ）。

{{ select(25) }}

• 1
• 11
• 24
• 39

26. （3 分）输入 4，程序输出（ ）。

{{ select(26) }}

• 16
• 8
• 10
• 24

阅读程序（三）

输入一个只含英文字母、长度为 1 到 10 的字符串，字符可以重复。全局数组初值为 0。阅读以下程序，回答问题。

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

char s[100], tmp[100];
bool vis[100];
int n;

void dfs(int step) {
    if (step == n) {
        cout << tmp << '\n';
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            vis[i] = true;
            tmp[step] = s[i];
            dfs(step + 1);
            vis[i] = false;
        }
    }
}

int main() {
    cin >> s;
    n = strlen(s);
    dfs(0);
    return 0;
}

27. （1.5 分）把递归出口 step == n 改为 step >= n，不会影响输出结果。

{{ select(27) }}

• 正确
• 错误

28. （1.5 分）对任意合法输入，与输入字符串完全相同的文本在输出中恰好出现一次。

{{ select(28) }}

• 正确
• 错误

29. （1.5 分）删除回溯语句 vis[i] = false 后，程序只输出一行，并且这一行与输入字符串相同。

{{ select(29) }}

• 正确
• 错误

30. （3 分）输入 abc，输出的第 4 行是（ ）。

{{ select(30) }}

• cab
• bca
• cba
• abc

31. （4 分）若输出的第 2 行是 abcde，则输出的第 5 行是（ ）。

{{ select(31) }}

• abedc
• abecd
• abdce
• abdec

32. （3 分）输入 aa 时，程序一共输出多少行？

{{ select(32) }}

• 1
• 2
• 4
• 0

三、完善程序（10 题，每题 3 分，共 30 分）

完善程序（一）：哥德巴赫猜想验证

程序先枚举不超过 $n$ 的质数，再统计区间 $[4,n]$ 中能表示为两个质数之和的偶数个数。输入满足 $4\le n\le5000$。请补全代码。

#include <iostream>
using namespace std;

int main() {
    const int SIZE = 1000;
    int n, r, p[SIZE], ans;
    bool tmp;
    cin >> n;
    r = 1;
    p[1] = 2;
    for (int i = 3; i <= n; ++i) {
        ①
        for (int j = 1; j <= r; ++j)
            if (i % ② == 0) {
                tmp = false;
                break;
            }
        if (tmp) {
            ++r;
            ③
        }
    }
    ans = 0;
    for (int i = 2; i <= n / 2; ++i) {
        tmp = false;
        for (int j = 1; j <= r; ++j)
            for (int k = j; k <= r; ++k)
                if (i + i == ④) {
                    tmp = true;
                    break;
                }
        if (tmp) ++ans;
    }
    cout << ans << '\n';
    return 0;
}

33. （3 分）①处应填（ ）。

{{ select(33) }}

• tmp = true;
• tmp = false;
• tmp++;
• r = sqrt(n);

34. （3 分）②处应填（ ）。

{{ select(34) }}

• j
• p[j]
• p[j+1]
• p[i]

35. （3 分）③处应填（ ）。

{{ select(35) }}

• p[r] = i;
• p[r-1] = i;
• p[r] = j;
• p[r-1] = j;

36. （3 分）④处应填（ ）。

{{ select(36) }}

• p[k]
• p[i] + p[k]
• p[i] + p[i]
• p[j] + p[k]

37. （3 分）若输入 2010，输出多少表示验证成功？

{{ select(37) }}

• 1003
• 1004
• 1005
• 1006

完善程序（二）：寻找等差数列

有若干个长度相同的等差数列，每项均为 0 到 59 的整数。把所有项打乱后给出，求这些数能被重新分组时，公共长度 $L$ 的最大可能值。输入 $1\le n\le60$。请补全代码。 输入第一行是项数 n，第二行是 n 个整数；允许不同数列的公差不同，也允许公差为 0，每个给定项必须恰好使用一次。

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

int cnt[60];
int n, x, ans, maxnum;

int work(int now) {
    int first, second, delta, ok;
    while (① && !cnt[now]) ++now;
    if (now > maxnum) return 1;
    first = now;
    for (second = first; second <= maxnum; ++second) {
        if (cnt[second]) {
            delta = ②;
            if (first + delta * (③) > maxnum) break;
            if (delta == 0) ok = ④;
            else {
                ok = 1;
                for (int i = 0; i < ans; ++i)
                    ok = ⑤ && cnt[first + delta * i];
            }
            if (ok) {
                for (int i = 0; i < ans; ++i) --cnt[first + delta * i];
                if (work(first)) return 1;
                for (int i = 0; i < ans; ++i) ++cnt[first + delta * i];
            }
        }
    }
    return 0;
}

int main() {
    memset(cnt, 0, sizeof(cnt));
    cin >> n;
    maxnum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        ++cnt[x];
        if (x > maxnum) maxnum = x;
    }
    for (ans = n; ans >= 1; --ans)
        if (n % ans == 0 && work(0)) {
            cout << ans << '\n';
            break;
        }
    return 0;
}

38. （3 分）①处应填（ ）。

{{ select(38) }}

• now
• now <= maxnum
• now <= n
• now < maxnum

39. （3 分）②处应填（ ）。

{{ select(39) }}

• maxnum - first
• second - first
• maxnum - second
• cnt[second] - cnt[first]

40. （3 分）③处应填（ ）。

{{ select(40) }}

• ans
• ans - 1
• now
• now - 1

41. （3 分）④处应填（ ）。

{{ select(41) }}

• cnt[second] >= ans
• ok
• first + delta*(ans-1)
• cnt[first] == ans

42. （3 分）⑤处应填（ ）。

{{ select(42) }}

• ok
• ok && (cnt[first + delta*i] > 1)
• cnt[second + delta*i]
• !ok