普及组 CSP-J 2026 初赛模拟卷 1

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

1. 启动计算机引导操作系统是将操作系统（　　）。

{{ select(1) }}

• 从磁盘调入中央处理器
• 从存储器调入高速缓冲存储器
• 从软盘调入硬盘
• 从系统盘调入内存

2. Windows 9x 是一种（　　）操作系统。

{{ select(2) }}

• 单任务字符方式
• 单任务图形方式
• 多任务字符方式
• 多任务图形方式

3. 在 24×24 点阵的字模中，汉字"一"与"蝙"的字模占用字节数分别是（　　）。

{{ select(3) }}

• 72　72
• 32　32
• 32　72
• 72　32

4. 计算机的运算速度取决于给定时间内其处理器所能处理的数据量。处理器一次能处理的数据量称为字长。已知 64 位的奔腾处理器一次能处理 64 位，相当于（　　）字节。

{{ select(4) }}

• 8
• 1
• 16
• 2

5. 算式 $(2047)_{10} - (3FF)_{16} + (2000)_8$ 的结果是（　　）。

{{ select(5) }}

• $(2048)_{10}$
• $(2049)_{10}$
• $(3746)_8$
• $(1AF7)_{16}$

6. 计算机的运算速度可以用 MIPS 来描述，它的含义是（　　）。

{{ select(6) }}

• 每秒执行百万条指令
• 每秒处理百万个字符
• 每秒执行千万条指令
• 每秒处理千万个字符

7. 栈 S 的初始状态为空，现有一个由 5 个元素组成的序列 $\{1,2,3,4,5\}$，对该序列在线 S 上依次进行如下操作（从序列的 1 开始，出栈后不再进栈）：进栈、出栈、进栈、进栈、出栈、进栈、出栈、进栈、出栈。出栈的元素序列是（　　）。

{{ select(7) }}

• $\{5,4,3,2,1\}$
• $\{2,3\}$
• $\{2,3,4\}$
• $\{1,3,4\}$

8. 在有 $n$ 个叶子节点的哈夫曼树中，节点总数为（　　）。

{{ select(8) }}

• 不确定
• $2n-1$
• $2n+1$
• $2n$

9. 电线上停着两种鸟（A 和 B），可以看出相邻的两只鸟将电线划分为一个线段。这些线段可分为两类：一类是线段两端的鸟种类相同，另一类是线段两端的鸟种类不同。已知电线的两个端点处恰好停着种类相同的鸟，那么两端的鸟种类不同的线段数目一定是（　　）。

{{ select(9) }}

• 奇数
• 偶数
• 可奇可偶
• 数目固定

10. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为（　　）。

{{ select(10) }}

• 插入排序
• 归并排序
• 选择排序
• 快速排序

11. 对于一棵满二叉树，若其叶节点数为 $m$、分支节点数为 $L$、总节点数为 $n$，则下列关系式成立的是（　　）。

{{ select(11) }}

• $n = L + m$
• $L + m = 2n$
• $m = L - 1$
• $n = 2L - 1$

12. 以下不是操作系统的名字的是（　　）。

{{ select(12) }}

• Windows XP
• Arch/Info
• Linux
• OS/2

13. 以下不是个人计算机硬件组成部分的是（　　）。

{{ select(13) }}

• 主板
• 虚拟内存
• 总线
• 硬盘

14. 已知元素 $\{8,25,14,87,51,90,6,19,20\}$，这些元素以（　　）的顺序全部入栈，再全部出栈，可使栈的出栈顺序满足：8 在 51 之前；90 在 87 之后；20 在 14 之后；25 在 6 之前；19 在 90 之后。

{{ select(14) }}

• 20, 6, 8, 51, 90, 25, 14, 19, 87
• 51, 6, 19, 20, 14, 8, 87, 90, 25
• 19, 20, 90, 8, 6, 25, 51, 14, 87
• 6, 25, 51, 8, 20, 19, 90, 87, 14

15. 假设我们用向量 $\mathbf{d} = (a_1, a_2, \cdots, a_5)$ 表示无向连通图 $G$ 的 5 个顶点的度数，下面给出的（　　）组 $\mathbf{d}$ 值合理。

{{ select(15) }}

• (2,2,2,2,2)
• (1,2,2,1,1)
• (3,3,3,2,2)
• (5,4,3,2,1)

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

(1)

#include <iostream>
#include <cmath>
using namespace std;
bool IsPrime(int num) {
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}
int main() {
    int num = 0;
    cin >> num;
    if (IsPrime(num)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

■ 判断题

16. 输入 97 时，输出为 NO。　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(16) }}

• 正确
• 错误

17. 输入 119 时，输出为 YES。　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(17) }}

• 正确
• 错误

18. 若将第 5 行的 <= 改成 <，程序输出不会改变。　　　　　　　　　　　　　　　（　　）

{{ select(18) }}

• 正确
• 错误

19. 当程序执行第 8 行时，i 的值为 sqrt(num)。　　　　　　　　　　　　　　　　　（　　）

{{ select(19) }}

• 正确
• 错误

■ 选择题

20. 最坏情况下，此程序的时间复杂度是（　　）。

{{ select(20) }}

• $O(\text{num})$
• $O(\text{num}^2)$
• $O(\sqrt{\text{num}})$
• $O(\log \text{num})$

21. 若输入为 20 以内的正整数，则输出 YES 的概率是（　　）。

{{ select(21) }}

• 0.45
• 0.4
• 0.5
• 0.35

(2)

#include <bits/stdc++.h>
using namespace std;
const int mod = 2048;
long long c, n;
long long kasumi(long long x, long long mi) {
    long long res = 1;
    while (mi) {
        if (mi & 1) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        mi >>= 1;
    }
    return res;
}
int main() {
    cin >> n >> c;
    if (n == 3) {
        printf("%lld", c * (c - 1));
        return 0;
    }
    long long ans = ((kasumi(c - 1, n) + (c - 1) * kasumi(-1, n)) % mod + mod) % mod;
    cout << ans << endl;
    return 0;
}

■ 判断题

22. 将第 9 行和第 11 行中的圆括号去掉，程序输出不变。　　　　　　　　　　　　　（　　）

{{ select(22) }}

• 正确
• 错误

23. 将第 12 行的 mi >>= 1 改为 mi *= 0.5，程序输出不变。　　　　　　　　　　　　（　　）

{{ select(23) }}

• 正确
• 错误

24. 若输入 4 4，输出为 78。　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(24) }}

• 正确
• 错误

25. 此程序的时间复杂度为 $O(\log n)$。　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(25) }}

• 正确
• 错误

■ 选择题

26. （4 分）若输入 3 4，输出为（　　）。

{{ select(26) }}

• 8
• 12
• 18
• 19

(3)

#include <cstdio>
int n, r, num[10000];
bool mark[10000];
void print() {
    for (int i = 1; i <= r; i++)
        printf("%d ", num[i]);
    printf("\n");
}
void search(int x) {
    for (int i = 1; i <= n; i++)
        if (!mark[i]) {
            num[x] = i;
            mark[i] = true;
            if (x == r) print();
            search(x + 1);
            mark[i] = false;
        }
}
int main() {
    scanf("%d%d", &n, &r);
    search(1);
}

■ 判断题

27. 程序结束时，对任意 $1 \le i \le n$，都有 mark[i] = 0。　　　　　　　　　　　（　　）

{{ select(27) }}

• 正确
• 错误

28. 若 $n < r$，则程序无输出。　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(28) }}

• 正确
• 错误

29. 若输入 4 3，则输出中数字 1 和 2 的个数不同。　　　　　　　　　　　　　　　　　（　　）

{{ select(29) }}

• 正确
• 错误

30. 此程序的时间复杂度为 $O(n)$。　　　　　　　　　　　　　　　　　　　　　　　　（　　）

{{ select(30) }}

• 正确
• 错误

■ 选择题

31. 若输入 6 3，则函数 print 的执行次数为（　　）。

{{ select(31) }}

• 60
• 120
• 6
• 720

32. 若输入 7 4，则输出的最后一行为（　　）。

{{ select(32) }}

• 4 5 6 7
• 7 6 5 4
• 4 3 2 1
• 1 2 3 4

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

(1)

Kruskal 求最小生成树的思想：首先将 $n$ 个点看作 $n$ 个独立的集合，将所有边排序（从小到大），然后按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于同一集合。若不属于同一集合，则将这条边加入最小生成树中，并将两个点所在的集合合并为一个集合。若属于同一集合，则跳过。直到找到 $n-1$ 条边为止。

#include <iostream>
#include <algorithm>
using namespace std;
struct point { int x, y, v; } a[10000];
int cmp(const point &a, const point &b) {
    if (①) return 1;
    return 0;
}
int fat[101];
int father(int x) {
    if (fat[x] != x) return fat[x] = ②;
    return fat[x];
}
void unionn(int x, int y) {
    int fa = father(x), fb = father(y);
    if (fa != fb) fat[fa] = fb;
}
int main() {
    int i, j, n, m, k = 0, ans = 0, cnt = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++) {
            cin >> m;
            if (m != 0) {
                k++; a[x].x = i; a[k].y = j; a[k].v = m;
            }
        }
    sort(a + 1, a + 1 + k, ③);
    for (i = 1; i <= n; i++) fat[i] = i;
    for (i = 1; i <= k; i++) {
        if (father(a[i].x) != ④) {
            ans += a[i].v;
            unionn(a[i].x, a[i].y);
            cnt++;
        }
        if (⑤) break;
    }
    cout << ans << endl;
    return 0;
}

33. ① 处应填（　　）。

{{ select(33) }}

• a.v < b.v
• a.v > b.v
• a.v >= b.v
• a.v <= b.v

34. ② 处应填（　　）。

{{ select(34) }}

• father(x)
• father(fat[x])
• fat[father(x)]
• x

35. ③ 处应填（　　）。

{{ select(35) }}

• algorithm
• point
• cmp
• sizeof(a)

36. ④ 处应填（　　）。

{{ select(36) }}

• a[i].y
• father(a[i].y)
• fat[a[i].y]
• a[i].x

37. ⑤ 处应填（　　）。

{{ select(37) }}

• cnt > 0
• i == 1
• ans == n-1
• cnt == n-1

(2)

欧拉路径问题是指从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边（一次且仅一次）。算法代码如下。

#include <iostream>
using namespace std;
int G[5][5];
int visited[5][5];
int n = 5;
void euler(int u) {
    for (int v = 0; v < n; v++) {
        if (G[u][v] && ①) {
            cout << u << "->" << v << endl;
            visited[u][v] = visited[v][u] = ②;
            ③
        }
    }
}
int main() {
    G[1][2] = G[2][1] = G[1][3] = ④ = 1;
    G[2][4] = G[4][2] = G[3][4] = ⑤ = 1;
    euler(1);
    return 0;
}

38. ① 处应填（　　）。

{{ select(38) }}

• G[v][u]
• !visited[u][v]
• visited[u][v]
• visited[v][u]

39. ② 处应填（　　）。

{{ select(39) }}

• 1
• 0
• u
• v

40. ③ 处应填（　　）。

{{ select(40) }}

• euler(v);
• euler(u);
• G[u][v] = 0;
• G[v][u] = 0;

41. ④ 处应填（　　）。

{{ select(41) }}

• G[0][1]
• G[1][0]
• G[3][1]
• G[0][3]

42. ⑤ 处应填（　　）。

{{ select(42) }}

• G[0][2]
• G[2][0]
• G[2][1]
• G[4][3]