2026 CSPJ 初赛模拟 5（JH）

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

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

1. （2 分）冯·诺依曼结构计算机的基本组成中不包含（ ）。

{{ select(1) }}

• 运算器
• 存储器
• 通讯器
• 控制器

2. （2 分）下列四个数中，与其他三项数值不同的是（ ）。

{{ select(2) }}

• $(111011)_2$
• $(59)_{10}$
• $(71)_8$
• $(3B)_{16}$

3. （2 分）两个 8 位带符号整数的补码分别为 10101011 和 01001100，它们的和用十进制表示为（ ）。

{{ select(3) }}

• 247
• -247
• 9
• -9

4. （2 分）下列哪个中缀表达式的后缀形式是 abcd+*+？

{{ select(4) }}

• (a+b)*(c+d)
• a+b*(c+d)
• (a+b)*c+d
• a+b*c+d

5. （2 分）逻辑变量 A、B 为真，C、D 为假。下列逻辑表达式中值为真的是（ ）。

{{ select(5) }}

• $(¬A∧B)∨(C∧D)$
• $(A∧B∧C)∨(B∧C∧¬D)$
• $(A∨B)∧(B∨C)∧(C∨D)$
• $(A∨¬B∨C)∧(¬B∨C∨¬D)$

6. （2 分）下列排序算法中，平均时间复杂度最高的是（ ）。

{{ select(6) }}

• 快速排序
• 归并排序
• 堆排序
• 选择排序

7. （2 分）在常见的 32 位 int 环境中，长度为 1000000 的 int 数组约占用多少空间？

{{ select(7) }}

• 1 MB
• 4 MB
• 32 MB
• 64 MB

8. （2 分）已知大写字母 A 的 ASCII 码为 65，则大写字母 K 的 ASCII 码是（ ）。

{{ select(8) }}

• 74
• 75
• 76
• 以上都不是

9. （2 分）元素 a、b、c、d 按此顺序入栈，允许进栈和出栈交替，合法的出栈序列共有多少种？

{{ select(9) }}

• 10
• 12
• 14
• 16

10. （2 分）根结点深度为 0。一棵深度为 $h$ 的 $k$ 叉树（$k>1$）中，每个结点要么没有孩子，要么恰有 $k$ 个孩子。其最少结点数是（ ）。

{{ select(10) }}

• $(k^{h+1}-1)/(k-1)$
• $(k^{h+1}-1)/(k-1)+k$
• $kh+1$
• $k(h-1)+1$

11. （2 分）一个含 6 个顶点的完全图至少删掉多少条边，才能变成森林？

{{ select(11) }}

• 8
• 10
• 11
• 14

12. （2 分）函数 solve(x) 在 x=0 时返回 0，否则返回 solve(x-(x&-x))+1。调用 solve(87) 的返回值是（ ）。

{{ select(12) }}

• 4
• 5
• 6
• 7

13. （2 分）把 8 个相同的球放进 3 个不同的袋子，允许空袋，共有多少种放法？

{{ select(13) }}

• 21
• 45
• 336
• 512

14. （2 分）结点标识互不相同。一棵非空二叉树的前序遍历和中序遍历完全相同，当且仅当它是（ ）。

{{ select(14) }}

• 根结点没有右子树的二叉树
• 根结点没有左子树的二叉树
• 只有一个结点，或每个非叶结点都只有左孩子
• 只有一个结点，或每个非叶结点都只有右孩子

15. （2 分）甲、乙、丙、丁、戊、己 6 人排成一排，甲乙必须相邻，丙丁不得相邻，共有多少种排法？

{{ select(15) }}

• 96
• 120
• 144
• 192

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

阅读程序（一）

输入第一行是正整数 $T$，接下来 $T$ 行每行给出整数 $a,b$，满足 $1\le b\le a\le5000000$。阅读以下程序，回答问题。

#include <cstdio>

const int MAXN = 5000007;
int prime[MAXN], tot;
int sum[MAXN];
bool vis[MAXN];

void sieve() {
    for (int i = 2; i < MAXN; ++i) {
        if (!vis[i]) {
            prime[++tot] = i;
            sum[i] = 1;
        }
        for (int j = 1; j <= tot && 1LL * prime[j] * i < MAXN; ++j) {
            vis[prime[j] * i] = true;
            sum[prime[j] * i] = sum[i] + 1;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 1; i < MAXN; ++i) sum[i] += sum[i - 1];
}

int main() {
    sieve();
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", sum[a] - sum[b]);
    }
    return 0;
}

16. （2 分）把外层循环的初值 i=2 改为 i=1，程序结果不变。

{{ select(16) }}

• 正确
• 错误

17. （2 分）删除内层循环末尾的 break，程序结果仍正确，但运行速度可能变慢。

{{ select(17) }}

• 正确
• 错误

18. （2 分）程序的输出结果不可能为 0。

{{ select(18) }}

• 正确
• 错误

19. （3 分）令 N = MAXN - 1 为可变的筛选上界，不计输入输出，函数 sieve() 的紧确渐近时间复杂度是（ ）。

{{ select(19) }}

• $Θ(N)$
• $Θ(\log N)$
• $Θ(N\log N)$
• $Θ(N^2)$

20. （3 分）输入为 1 10 1 时，程序输出（ ）。

{{ select(20) }}

• 13
• 14
• 15
• 16

阅读程序（二）

采用 ASCII 字符编码。输入一个只含英文字母的非空字符串，长度不超过 100000。阅读以下程序，回答问题。

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

int main() {
    string s, t;
    cin >> s;
    for (int i = 0; i < (int)s.size(); ++i) {
        int a;
        if ('A' <= s[i] && s[i] <= 'Z')
            a = (s[i] - 'A' + 25) % 26;
        else
            a = (s[i] - 'a' + 1) % 26;
        char c;
        if (i & 2) c = a + 'a';
        else c = a + 'A';
        t += c;
    }
    cout << t << '\n';
    return 0;
}

21. （1.5 分）删掉判断条件中的 'A' <= s[i]，输出结果会出现英文字母以外的字符。

{{ select(21) }}

• 正确
• 错误

22. （1.5 分）如果输入字符串长度为偶数，输出中大写字母和小写字母的数量一定相同。

{{ select(22) }}

• 正确
• 错误

23. （1.5 分）输出字符串的长度总与输入字符串的长度相同。

{{ select(23) }}

• 正确
• 错误

24. （3 分）输入 abcdEFGH 时，输出是（ ）。

{{ select(24) }}

• ZAbcFGhi
• zaBCfgHl
• BCdeDEfg
• bcDEdeFG

25. （3 分）把条件 i & 2 替换为下列哪一项，不影响输出？

{{ select(25) }}

• i % 4 % 2 == 0
• i % 4 % 2 == 1
• i % 2 == 1
• i / 2 % 2 == 1

26. （3 分）若输出 t="AZabGPds"，下列哪个输入 s 不可能产生该输出？

{{ select(26) }}

• BABCfocr
• zABaHoEr
• zABCHQCT
• zyzCfQcr

阅读程序（三）

输入整数 $1\le n\le1000$，以及 $n$ 个绝对值不超过 $10^9$ 的整数。全局数组初值为 0。阅读以下程序，回答问题。

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

int n, a[1001], index_[1001], mark[1001];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        index_[i] = i;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n - i; ++j)
            if (a[index_[j]] > a[index_[j + 1]]) {
                int t = index_[j];
                index_[j] = index_[j + 1];
                index_[j + 1] = t;
            }
    int now = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        now += mark[i];
        mark[index_[i]] = 1;
        if (index_[i] <= i) ++now;
        if (now == i) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

27. （1.5 分）程序输出至少为 1。

{{ select(27) }}

• 正确
• 错误

28. （1.5 分）在最后一个循环中，变量 now 始终不超过 i。

{{ select(28) }}

• 正确
• 错误

29. （1.5 分）当 n=100 时，程序的输出最大可以达到 100。

{{ select(29) }}

• 正确
• 错误

30. （3 分）设 $n\ge4$ 且程序最终输出为 1。每轮最后一个 for 循环的循环体执行完、尚未执行 ++i 时观察变量；在 ans=0 的观测中，i 的最大值是（ ）。

{{ select(30) }}

• $n$
• $n-1$
• 2
• 1

31. （4 分）若 n=50，a 是 1 到 50 的一个排列，且 a[50]=50，则答案至少为（ ）。

{{ select(31) }}

• 0
• 1
• 2
• 20

32. （3 分）若 n=6，a 依次为 3 2 1 6 4 7，程序输出（ ）。

{{ select(32) }}

• 1
• 3
• 5
• 6

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

完善程序（一）：拔河分组

每组有 $3\le n\le15$ 名同学，体重在 1 到 10000 之间。选至少 1 人当裁判，其余同学全部分入两支拔河队；两队都至少 1 人且人数相差不超过 1，目标是使两队体重和之差最小。请补全代码。

示例输入：2 / 3 / 30 31 100 / 4 / 30 38 67 1（斜线表示换行）；示例输出为两行 1。

输入第一行是正整数 T，表示数据组数；每组先输入 n，再输入 n 个体重。枚举时要求 st 恰好遍历 n 位集合，l 只遍历 st 的非空子集且不重复。

#include <bits/stdc++.h>
using namespace std;

int n, a[20];

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        int ans = 10000 * n;
        for (int st = 0; st < ①; ++st) {
            for (int l = st; l; l = ②) {
                int r = st ^ l;
                int cntl = 0, cntr = 0, cntp = 0;
                int wl = 0, wr = 0;
                for (int i = 0; i < n; ++i) {
                    if (③) {
                        ++cntl;
                        wl += a[i];
                    } else if ((1 << i) & r) {
                        ++cntr;
                        ④
                    } else {
                        ++cntp;
                    }
                }
                if (⑤) ans = min(ans, abs(wl - wr));
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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

{{ select(33) }}

• n
• 1 << (n-1)
• n+1
• 1 << n

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

{{ select(34) }}

• (l-1) ^ st
• 0
• (l-1) & st
• (l-1) | st

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

{{ select(35) }}

• (1 << (i+1)) & l
• (1 << i) & l
• (1 << (i+1)) | l
• (1 << i) | l

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

{{ select(36) }}

• wr += a[i];
• wl += a[i];
• wr -= a[i];
• wr = a[i];

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

{{ select(37) }}

• cntp>0 || abs(cntl-cntr)<=1
• cntp>0 && abs(cntl-cntr)<=1
• cntl>0 && cntr>0 && cntp>0 && abs(cntl-cntr)<=1
• (cntl>0 || cntr>0 || cntp>0) && abs(cntl-cntr)<=1

完善程序（二）：迷宫最短路

在 $n\times m$ 迷宫中，S 是起点，T 是终点，# 不可通过，. 可以通过。每步可向上下左右移动一格，求最少步数；无法到达输出 -1。输入满足 $1\le n,m\le500$。请补全代码。

示例输入为 3 3 / S.. / ##. / .T.（斜线表示换行），输出为 5。

保证恰好有一个 S 和一个 T，位于不同格子，其余字符只能为 . 或 #；因此格子数至少为 2。输入第一行是 n、m，接下来 n 行，每行恰有 m 个字符。

#include <bits/stdc++.h>
using namespace std;

char a[1007][1007];
int x, y, n, m;
int dx[4] = { ① };
int dy[4] = {0, 0, 1, -1};
bool vis[1007][1007], flag;

struct Node { int row, col, dis; };
queue<Node> que;

bool check(int s, int t) {
    if (②) return false;
    if (vis[s][t]) return false;
    if (a[s][t] == '#') return false;
    return true;
}

void bfs() {
    que.push({x, y, 0});
    vis[x][y] = true;
    while (!que.empty()) {
        Node p = que.front();
        que.pop();
        if (a[p.row][p.col] == 'T') {
            cout << p.dis << '\n';
            flag = true;
            break;
        }
        for (int i = 0; i < 4; ++i) {
            if (check(p.row + dx[i], p.col + dy[i])) {
                ③
                vis[p.row + dx[i]][p.col + dy[i]] = true;
            }
        }
    }
    ④
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (⑤) { x = i; y = j; }
    bfs();
    return 0;
}

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

{{ select(38) }}

• 0,-1,0,1
• 1,-1,0,0
• 0,0,1,-1
• 1,0,-1,0

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

{{ select(39) }}

• s<0 || s>=n || t<0 || t>=m
• s>=1 && s<=n && t>=1 && t<=m
• s<1 || s>n || t<1 || t>m
• s>=0 && s<n && t>=0 && t<m

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

{{ select(40) }}

• que.push({p.row,p.col,p.dis+1});
• que.push({p.row+dx[i],p.col+dy[i],p.dis+1});
• que.push({p.row,p.col,p.dis});
• que.push({p.row+dx[i],p.col+dy[i],p.dis});

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

{{ select(41) }}

• while (!que.empty()) que.pop();
• if (flag) cout << -1 << '\n';
• return;
• if (!flag) cout << -1 << '\n';

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

{{ select(42) }}

• a[i][j] == '.'
• a[i][j] == '#'
• a[i][j] == 'S'
• a[i][j] == 'T'