信息学奥赛 CSP-J 2026 初赛模拟卷 1

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

1. 启动计算机引导操作系统是将操作系统（　　）。 {{ select(1) }}

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

2. $Windows\ 9x$ 是一种（　　）操作系统。 {{ select(2) }}

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

3. 在 $24\times24$ 点阵的字模中，汉字"一"与"编"的字模占用字节数分别是（　　）。 {{ 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. 假设我们用向量 $\boldsymbol{d}=(a_1,a_2,\cdots,a_5)$ 表示无向连通图 $G$ 的 $5$ 个顶点的度数，下面给出的（　　）组 $\boldsymbol{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)

1  #include <iostream>
2  #include <cmath>
3  using namespace std;
4  bool IsPrime(int num) {
5      for (int i=2; i<=sqrt(num); i++) {
6          if (num % i == 0) return false;
7      }
8      return true;
9  }
10 int main() {
11     int num = 0;
12     cin >> num;
13     if (IsPrime(num)) cout << "YES" << endl;
14     else cout << "NO" << endl;
15     return 0;
16 }

判断题

16. 输入 $97$ 时，输出为 $NO$。　　（　　） {{ select(16) }}

• √
• ×

17. 输入 $119$ 时，输出为 $YES$。　　（　　） {{ select(17) }}

• √
• ×

18. 若将第 $5$ 行的 <= 改成 <，程序输出不会改变。　　（　　） {{ select(18) }}

• √
• ×

19. 当程序执行第 $8$ 行时，$i$ 的值为 $sqrt(\text{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)

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int mod = 2048;
4  long long c,n;
5  long long kasumi(long long x,long long mi) {
6      long long res=1;
7      while (mi) {
8          if (mi & 1) {
9              res = (res * x) % mod;
10         }
11         x = (x * x) % mod;
12         mi >>= 1;
13     }
14     return res;
15 }
16 int main() {
17     cin >> n >> c;
18     if (n == 3) {
19         printf("%lld", c * (c - 1));
20         return 0;
21     }
22     long long ans = ((kasumi(c-1,n) + (c-1) * kasumi(-1,n)) % mod + mod) % mod;
23     cout << ans << endl;
24     return 0;
25 }

判断题

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)

1  #include <cstdio>
2  int n,r,num[10000];
3  bool mark[10000];
4  void print() {
5      for (int i=1; i<=r; i++)
6          printf("%d ", num[i]);
7      printf("\n");
8  }
9  void search(int x) {
10     for (int i=1; i<=n; i++)
11         if (!mark[i]) {
12             num[x] = i;
13             mark[i] = true;
14             if (x == r) print();
15             search(x + 1);
16             mark[i] = false;
17         }
18 }
19 int main() {
20     scanf("%d%d", &n, &r);
21     search(1);
22 }

判断题

27. 程序结束时，对任意 $1 \le i \le n$，都有 $\text{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$ 条边为止。

1  #include <iostream>
2  #include <algorithm>
3  using namespace std;
4  struct point { int x, y, v; } a[10000];
5  int cmp(const point &a, const point &b) {
6      if ( ① ) return 1;
7      return 0;
8  }
9  int fat[101];
10 int father(int x) {
11     if (fat[x] != x) return fat[x] = ② ;
12     return fat[x];
13 }
14 void unionn (int x, int y){
15     int fa = father(x), fb = father(y);
16     if (fa != fb) fat[fa] = fb;
17 }
18 int main() {
19     int i,j,n,m, k=0, ans=0, cnt=0;
20     cin >> n;
21     for (i=1; i<=n; i++)
22         for (j=1; j<=n; j++) {
23             cin >> m;
24             if (m != 0) {
25                 k++; a[k].x=i; a[k].y=j; a[k].v=m;
26             }
27         }
28     sort(a+1, a+1+k, ③ );
29     for (i=1; i<=n; i++) fat[i] = i;
30     for (i=1; i<=k; i++){
31         if (father(a[i].x) != ④ ) {
32             ans += a[i].v;
33             unionn(a[i].x, a[i].y);
34             cnt++;
35         }
36         if ( ⑤ ) break;
37     }
38     cout << ans << endl;
39     return 0;
40 }

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)

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

1  #include <iostream>
2  using namespace std;
3  int G[5][5];
4  int visited[5][5];
5  int n = 5;
6  void euler(int u) {
7      for (int v=0; v<n; v++) {
8          if (G[u][v] && ① ) {
9              cout << u << "->" << v << endl;
10             visited[u][v] = visited[v][u] = ② ;
11             ③
12         }
13     }
14 }
15 int main() {
16     G[1][2] = G[2][1] = G[1][3] = ④ = 1;
17     G[2][4] = G[4][2] = G[3][4] = ⑤ = 1;
18     euler(1);
19     return 0;
20 }

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]