信息学奥赛 CSP-S 2026 初赛模拟卷 2

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

第 1 题 大多数计算机病毒主要造成计算机（　　）的损坏。 {{ select(1) }}

• 软件和数据
• 硬件和数据
• 硬件、软件和数据
• 硬件和软件

第 2 题 假设有 $253$ 块月饼，把它们装到 $15$ 个盒子里面，那么数量最多的一盒至少装（　　）块月饼。 {{ select(2) }}

• $16$
• $23$
• $15$
• $17$

第 3 题 $ASCII$ 码是由美国国家标准委员会指定的一种包括数字、字母、通用字符和控制符号在内的字符编码集，它是一种（　　）位二进制码。 {{ select(3) }}

• $8$
• $7$
• $4$
• $32$

第 4 题 计算机的硬件主要包括控制器、（　　）、存储器、输入设备、输出设备。 {{ select(4) }}

• 运算器
• 操作系统
• 计算机语言
• 磁盘

第 5 题 字符 'a' 的 $ASCII$ 码是 $97$，下面程序的输出结果是（　　）。

char c = 'a' + 4;
cout << c << "," << (int) c + 3 << endl;

{{ select(5) }}

• $e,h$
• $101,104$
• $e,104$
• $101,h$

第 6 题 操作系统是对（　　）进行管理的软件。 {{ select(6) }}

• 计算机资源
• 软件
• 硬件
• 应用程序

第 7 题 以下选项中，（　　）不是操作系统。 {{ select(7) }}

• $Linux$
• $Windows\ CE$
• $Solaris$
• $Celeron$

第 8 题 以下关于 $C$++ 语言注释的说法中正确的是（　　）。 {{ select(8) }}

• 写 $C$++ 程序时必须书写注释，否则会对程序的功能造成影响
• $C$++ 语言的注释将参与编译器编译，并形成指令
• 可以采用"/* */"的形式书写多行注释，其中的注释内容可以是任何字符
• "// 注释"表示从 // 开始直到本行末尾的所有字符均是注释内容

第 9 题 要使用 putchar 函数实现向显示器输出字符 'A'，可使用（　　）。 {{ select(9) }}

• putchar(65)
• putchar(A)
• putchar('\65')
• putchar("A")

第 10 题 两个指针类型变量（　　）。 {{ select(10) }}

• 可在一定条件下相加
• 如同时指向一个变量，则此后就不能再指向其他变量了
• 任何时候都不能相减
• 可在一定条件下进行相等或不等的比较运算

第 11 题 下列属于 $B$ 类 $IP$ 地址的是（　　）。 {{ select(11) }}

• $27.33.119.2$
• $134.300.12.4$
• $133.201.189.32$
• $192.97.32.121$

第 12 题 现有变量 $a, b, c, d$，取值范围均为 $[0,15]$，假设每个值出现的概率相同，则 a^b^c^d 的值能被 $3$ 整除的概率是（　　）。（这里 ^ 为按位异或运算符。） {{ select(12) }}

• $3/8$
• $1/2$
• $1/4$
• $1/8$

第 13 题 假设以 $S$ 和 $X$ 分别表示进栈和出栈操作，对输入序列 $a, b, c, d, e$ 进行一系列栈操作 $SSXSXSSXXX$ 之后，得到的输出序列为（　　）。 {{ select(13) }}

• $baced$
• $bceda$
• $cbaed$
• $edcba$

第 14 题 某递归算法的执行时间的递推关系如下：当 $n=1$ 时 $T(n)=1$，当 $n>1$ 时 $T(n)=2T(n/2)+1$。则该算法的时间复杂度为（　　）。 {{ select(14) }}

• $O(1)$
• $O(\log_2 n)$
• $O(n)$
• $O(n\log_2 n)$

第 15 题 一棵完全二叉树中有 $501$ 个叶节点，则整棵树至少有（　　）个节点。 {{ select(15) }}

• $501$
• $502$
• $1001$
• $1002$

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

(1)

1  #include <iostream>
2  using namespace std;
3  const int maxn = 100001;
4
5  int N,M,K,x[maxn],y[maxn],d[maxn],c[maxn];
6  int *a[maxn];
7  int main() {
8      cin >> N >> M >> K;
9      for (int i=0; i<K; ++i) {
10         // 表示第 x[i] 行第 y[i] 列值为 d[i]
11         cin >> x[i] >> y[i] >> d[i];
12         c[y[i]]++;
13     }
14     for (int i=1; i<=M; ++i) a[i] = new int[c[i]];
15     for (int i=0; i<K; ++i) {
16         *a[y[i]] = d[i];
17         a[y[i]]++;
18     }
19     for (int i=1; i<=M; ++i) {
20         a[i] = a[i] - c[i];
21         for (int j=0; j<c[i]; ++j, ++a[i])
22             cout << *a[i] << " ";
23     }
24     return 0;
25 }

判断题

第 16 题 程序定义了一个指针数组 $a$，a[i] 表示第 i 列的指针。　　（　　） {{ select(16) }}

• √
• ×

第 17 题 将 *a[y[i]] = d[i] 改成 a[y[i]][0] = d[i] 不影响运算结果。　　（　　） {{ select(17) }}

• √
• ×

第 18 题 第 $12$ 行中，数组 $c$ 用来统计每行中的数据个数。　　（　　） {{ select(18) }}

• √
• ×

第 19 题 在本程序中，采用动态数组以优化空间的利用，每一列数组长度可能不同。　　（　　） {{ select(19) }}

• √
• ×

选择题

第 20 题 该程序的时间复杂度为（　　）。 {{ select(20) }}

• $O(MNK)$
• $O(M+K)$
• $O(M+N)$
• $O(K)$

第 21 题 该程序的空间复杂度为（　　）。 {{ select(21) }}

• $O(M+K)$
• $O(NK)$
• $O(M+N)$
• $O(MN)$

(2)

1  #include <iostream>
2  #include <iomanip>
3  using namespace std;
4  int m[101][101];
5
6  int main() {
7      int a;
8      cin >> a;
9      int c = a * a, i = 1, k = (a+1)/2;
10     for (int j=1; j<=c; j++) {
11         m[i][k] = j;
12         if (j % a == 0) {
13             if (i == a) i = 1; else i++;
14         } else {
15             if (i == 1) i = a; else i--;
16             if (k == a) k = 1; else k++;
17         }
18     }
19     for (int i=1; i<=a; i++) {
20         for (int j=1; j<=a; j++)
21             cout << setw(5) << m[i][j];
22         cout << endl;
23     }
24     return 0;
25 }

判断题

第 22 题 从程序可以看出，$i$ 为被填数，$j$ 和 $k$ 为填数位置。　　（　　） {{ select(22) }}

• √
• ×

第 23 题 填数结束后，数组 $m$ 中的元素互不相同。　　（　　） {{ select(23) }}

• √
• ×

选择题

第 24 题 当 j % a == 0 且 i != a 时，下一步填入的是（　　）。 {{ select(24) }}

• m[1][k]
• m[i+1][k]
• m[k+1][i]
• m[k+1][i+1]

第 25 题 当 j % a != 0、i != 1 且 k == a 时，下一步填入的是（　　）。 {{ select(25) }}

• m[a][1]
• m[i-1][1]
• m[a][k+1]
• m[i-1][k+1]

第 26 题 （$4$ 分）填数后，每行每列及对角线的和均为（　　）。 {{ select(26) }}

• $(a^2+1)a/2$
• $(a^2+1)/2$
• $(a^2+1)a$
• $a^2+1$

(3)

1  #include <iostream>
2  using namespace std;
3  int a[101], d[101];
4
5  int main() {
6      int n = 5;
7      a[1] = d[1] = 1;
8      for (int i=1; i<=n; ++i) {
9          int s = i+1, x = 0;
10         for (int j=1; j<=n+1-i; ++j) {
11             int k = s + x;
12             x++;
13             a[j+1] = a[j] + k;
14             cout << a[j] << ' ';
15         }
16         cout << "..." << endl;
17         a[1] = d[i+1] = d[i] + i;
18     }
19     return 0;
20 }

判断题

第 27 题 该题由两重循环构成，外循环 $i$ 控制列的变化，内循环 $j$ 控制行的变化。　　（　　） {{ select(27) }}

• √
• ×

第 28 题 代码运行结果如下。　　（　　）

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

{{ select(28) }}

• √
• ×

选择题

第 29 题 （$4$ 分）程序在输出时，第 $i$ 行为（　　）个 a[j] 数组的值。 {{ select(29) }}

• n+1-i
• n+1
• n+1+i
• n

第 30 题 （$4$ 分）本题代码的运算结果是输出（　　）行。 {{ select(30) }}

• $4$
• $5$
• $6$
• $7$

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

(1)

形如 $2^P - 1$ 的素数称为梅森素数。若 $2^P - 1$ 是梅森素数，则 $P$ 一定也是素数。但反过来不一定，即如果 $P$ 是素数，$2^P - 1$ 不一定也是素数。到 $1998$ 年年底，人们已找到了 $37$ 个梅森素数。最大的一个是 $2^{3,021,377} - 1$，即 $P = 3,021,377$，它有 $909526$ 位。梅森素数有许多重要应用，它与完全数密切相关。

你的任务：输入 $P$，计算 $2^P - 1$ 的位数及其最后 $500$ 位数字（用十进制高精度数表示）。

输入数据：只包含一个整数 $P$（$1000 < P < 3,100,000$）。

输出要求：第 $1$ 行输出十进制高精度数 $2^P - 1$ 的位数，第 $2\sim 11$ 行输出十进制高精度数 $2^P - 1$ 的最后 $500$ 位数字（每行输出 $50$ 位，共输出 $10$ 行，不足 $500$ 位时高位补 $0$）。

1  #include <cstdio>
2  #include <memory>
3  #include <cmath>
4  #define LEN 125
5
6  void Multiply(int *a, int *b) {
7      int i,j,nCarry,nTmp,c[LEN];
8      memset(c, 0, sizeof(int)* LEN);
9      for (i=0; i<LEN; i++) {
10         nCarry = 0;
11         for(j=0; ___①___; j++) {
12             nTmp = c[i+j] + a[j]*b[i] + nCarry;
13             c[i+j] = nTmp % 10000;
14             nCarry = nTmp / 10000;
15         }
16     }
17     memcpy(a, c, LEN * sizeof(int));
18 }
19
20 int main() {
21     int i, p, anPow[LEN], aResult[LEN];
22     scanf("%d", &p);
23     printf("%d\n", (int)(p *log10(2)) + 1);
24     anPow[0]=2;
25     aResult[0]=1;
26     for (i=1; i<LEN; i++) {
27         anPow[i] = 0;
28         aResult[i] = 0;
29     }
30     while (___②___) {
31         if (___③___) {
32             Multiply(aResult, anPow);
33         }
34         p >>= 1;
35         Multiply(anPow, anPow);
36     }
37     aResult[0]--;
38     for (i=LEN-1; i>=0; i--) {
39         if (___④___)
40             printf("%02d\n%02d", aResult[i]/100, aResult[i]%100);
41         else {
42             printf("%04d", aResult[i]);
43             if (i % 25 == 0) printf("\n");
44         }
45     }
46     return 0;
47 }

第 31 题 ① 处应填（　　）。 {{ select(31) }}

• j < LEN
• j < LEN - i - 1
• i < LEN - i
• j < 1

第 32 题 ② 处应填（　　）。 {{ select(32) }}

• p > 0
• p == 0
• p < 0
• p >= 0

第 33 题 ③ 处应填（　　）。 {{ select(33) }}

• p & 1
• p
• p || 1
• p = 0

第 34 题 ④ 处应填（　　）。 {{ select(34) }}

• i != 0
• i > 0
• i % 10 == 0
• i % 25 == 12

(2)

在遥远的国家佛罗布尼亚，嫌犯是否有罪须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选 $n$ 个人作为陪审团的候选人，然后再从这 $n$ 个人中选出 $m$ 个人组成陪审团。

选出 $m$ 个人的方法：控方和辩方根据对候选人的喜欢程度，给所有候选人打分，分值从 $0$ 到 $20$。为公平起见，法官选出陪审团的原则是选出的 $m$ 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。

输入数据：输入包含多组数据。每组数据的第一行是两个整数 $n$ 和 $m$，$n$ 是候选人数目，$m$ 是陪审团人数。$1 \leqslant n \leqslant 200$，$1 \leqslant m \leqslant 20$，而且 $m \leqslant n$。接下来 $n$ 行每行表示一个候选人的信息，它包含两个整数，分别是控方和辩方对该候选人的打分。候选人按出现的先后从 $1$ 开始编号。两组有效数据之间以空行分隔。最后一组数据 $n = m = 0$。

输出要求：对每组数据，先输出一行，表示答案所属的组号，如 Jury # 1、Jury # 2 等。接下来的一行输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。

1  #include <cstdio>
2  #include <cstdlib>
3  #include <memory>
4  #include <algorithm>
5  int f[30][1000], Path[300][1000];
6  int P[300], D[300], Answer[30];
7
8  int main() {
9      int i,j,k,t1,t2,n,m,nMinPD;
10     int nCaseNo = 0;
11     scanf("%d%d", &n, &m);
12     while (n + m) {
13         nCaseNo++;
14         for (i=1; i<=n; i++) scanf("%d%d", &P[i], &D[i]);
15         memset(f, -1, sizeof(f));
16         memset(Path, 0, sizeof(Path));
17         nMinPD = ___①___;
18         ___②___;
19         for (j=0; j<m; j++) {
20             for (k=0; ___③___; k++)
21                 if (___④___) {
22                     for (i=1; i<=n; i++)
23                         if (___⑤___) {
24                             t1 = j; t2 = k;
25                             while (t1 > 0 && Path[t1][t2] != i) {
26                                 t2 -= P[Path[t1][t2]] - D[Path[t1][t2]];
27                                 t1--;
28                             }
29                             if (t1 == 0) {
30                                 f[j+1][k+P[i]-D[i]] = f[j][k] + P[i] + D[i];
31                                 Path[j+1][k+P[i]-D[i]] = i;
32                             }
33                         }
34             }
35         }
36         i = nMinPD; j = 0;
37         while (f[m][i+j] < 0 && f[m][i-j] < 0) j++;
38         if (f[m][i+j] > f[m][i-j]) k = i + j;
39         else k = i - j;
40         printf("Jury #%d\n", nCaseNo);
41         printf("Best jury has value %d for prosecution and value %d for defence:\n"
42               , (k - nMinPD + f[m][k]) / 2, (f[m][k] - k + nMinPD) / 2);
43         for (i=1; i<=m; i++) {
44             ⑥;
45             k -= P[Answer[j]] - D[Answer[j]];
46         }
47         std::sort(Answer + 1,Answer+m+1);
48         for (i=1; i<=m; i++) printf("%d", Answer[i]);
49         printf("\n\n");
50         scanf("%d%d", &n, &m);
51     }
52     return 0;
53 }

第 35 题 ① 处应填（　　）。 {{ select(35) }}

• nMinPD = m*20
• nMinPD = m
• nMinPD = m*200
• nMinPD = m*n

第 36 题 ② 处应填（　　）。 {{ select(36) }}

• f[0][nMinPD] = 1
• f[0][nMinPD] = 0
• f[0][nMinPD] > 0
• f[0][nMinPD] > 1

第 37 题 ③ 处应填（　　）。 {{ select(37) }}

• k < nMinPD*2
• k < nMinPD
• k <= nMinPD*2
• k <= nMinPD

第 38 题 ④ 处应填（　　）。 {{ select(38) }}

• f[j][k] > 1
• f[j][k] >= 1
• f[j][k] >= 0
• f[j][k] > 0

第 39 题 ⑤ 处应填（　　）。 {{ select(39) }}

• f[j][k] + P[i] + D[i] > f[j+1][k+P[i]-D[i]]
• f[j][k] + P[i] + D[i] > f[j+1][k+P[i]]
• f[j][k] + P[i] > f[j+1][k+P[i]]
• f[j][k] + P[i] > f[j+1][k+P[i]-D[i]]

第 40 题 ⑥ 处应填（　　）。 {{ select(40) }}

• Answer[j] = Path[m-j][k]
• Answer[j] = Path[m-j][k+1]
• Answer[j] = Path[m-j+1][k+1]
• Answer[j] = Path[m-j+1][k]