提高组 CSP-S 2026 初赛模拟卷 3 —— 原题 + 解析

按目录截图字典序（91–99 页）整理。共 20 道：单选 15 + 阅读程序 3 + 完善程序 2（一道程序算一道）。

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

1.

今有一空栈 S，对依序进栈的数据元素序列 1,2,3,4,5,…进行以“进栈、进栈、出栈、进栈、进栈、进栈、出栈”为一轮的操作，一直操作下去，那么在 2019 轮操作后，S 的栈顶元素为（ ）。 A. 10090　B. 10094　C. 10100　D. 10086

答案：B 解：一轮 push 5 个、pop 2 个，净增 3 个，消耗编号 5 个。栈顶是本轮第 4 个数，即 5k-1。k=2019 时 5×2019-1=10094。 注意点：别数错每轮 pop 掉的是刚 push 的；栈顶不是 5k。

2.

对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找，等概率的情况下，查找成功的平均查找长度（平均比较次数）是（ ）。 A. 35/11　B. 34/11　C. 3　D. 34/10

答案：C 解：11 个数，mid 取下整。判定树 1/2/4/4 层分布，比较总数 1+4+12+16=33，33/11=3。 注意点：成功 ASL 分母是 11；失败才数空指针。

3.

以下选项中各有三个数，其中第一个为八进制数，第二个为十进制数，第三个为十六进制数。以下选项中三个数相同的为（ ）。 A. 120 82 50　B. 144 100 68　C. 300 200 C8　D. 1762 1010 3F2

答案：D 解：1762_8=512+448+48+2=1010，3F2_16=768+240+2=1010。 注意点：第一个是八进制，第三个是十六进制，F=15，按权展开逐个验算。

4.

将 {2,6,10,17} 分别存到某个地址区间为 0~10 的哈希表中，如哈希函数 h(x)=（ ），将不会产生冲突。 A. x mod 11　B. x² mod 11　C. 2x mod 11　D. [√x] mod 11

答案：D 解：A：17%11=6 撞 6；B：6²,17² 都余 3；C：2×6,2×17 都余 1；D 得 1,2,3,4 互异。 注意点：[] 是取整；4 个数逐个代入验算。

5.

二分图是指能将顶点分成两个部分，每一部分的顶点内部没有边相连的简单无向图，那么有 12 顶点的二分图至多有（ ）条边。 A. 18　B. 24　C. 36　D. 66

答案：C 解：K_{a,b},a+b=12，边 a×b≤6×6=36。 注意点：别和完全图 12×11/2=66 混。

6.

有一个含有 k 个不同的数的数集 S={x₁,x₂,…,xₖ}，若在 S 中有一个数 xᵢ(1xᵢ₊₁>…>xₖ，则称 xᵢ 为 S 的“峰顶”。S 称为单峰的。下面有几行伪码，请将 a~e 五处代码填入算法之中，使得算法能正确找到 S 的峰顶。

a. S[mid]<S[mid+1]
b. S[mid]>S[mid+1]
c. Search(1,mid-1)
d. Search(mid+1,k)
e. return S[mid]

Search(1,k){
  mid=k/2;
  if (S[mid]>S[mid-1] && ___) { ___; }
  else if (S[mid]>S[mid-1] && ___) { ___; }
  else ___;
}

正确的填空顺序是（ ）。 A. a,c,b,d,e　B. a,d,b,c,e　C. b,e,a,d,c　D. b,e,a,c,d

答案：C 解：先判峰顶 S[mid]>S[mid-1]&&b 则 e；上升段 S[mid]>S[mid-1]&&a 则往右 d；否则往左 c。 注意点：峰顶条件是同时大于两侧，这是唯一 return；截图 C/D 印刷重影，以逻辑为准。

7.

如果不在快速排序中引入随机化，可能导致的结果是（ ）。 A. 数据访问越界　B. 陷入死循环　C. 将排序结果错误　D. 排序时间退化为平方级

答案：D 解：有序数据 + 取端点 pivot 即退化；只影响性能不影响正确性。 注意点：不会死循环 / 越界 / 结果错误。

8.

二进制数 -1101010 的补码是（ ）。 A. 0010101　B. 10010110　C. 10010101　D. 01101010

答案：B 解：幅值 7 位，8 位原码 11101010 → 反码 10010101 → 补码 10010110。 注意点：C 是反码，别选错；注意 8 位符号位。

9.

设二进制数 x 的值是 11001101，若想通过 x&y 运算使 x 中的低 4 位不变，高 4 位清零，则 y 的二进制数是（ ）。 A. 11100000　B. 00001100　C. 00001111　D. 00000010

答案：C 解：&1 保留，&0 清零。要低 4 保留、高 4 清零。 注意点：别和 | 混。

10.

循环链表的主要优点是（ ）。 A. 不需要头指针 B. 已知某个结点的位置后，能很容易找到它的直接前驱结点 C. 在进行删除操作后，能保证链表不断开 D. 从表中任一结点出发都能扫描整个链表

答案：D 解：B 是双向链表优点；A/C 不对。 注意点：关键词“循环”→ 回路可遍历。

11.

若某算法的计算时间表示为递推关系式 T(N)=N+T(N/2)，则该算法的时间复杂度为（ ）。 A. O(N²)　B. O(N log N)　C. O(N)　D. O(1)

答案：C 解：N+N/2+N/4+…=2N。 注意点：Master a=1,b=2 情形。

12.

若某算法的计算时间表示为递推关系式 T(N)=3T(N/4)+n log₂n，则该算法的时间复杂度为（ ）。 A. O(n)　B. O(n log₂n)　C. O(n log₂²n)　D. O(n²)

答案：B 解：n^{log₄3}≈n^0.79 < n log n，Master Case 3，正则条件成立。 注意点：别看到 3T 就选 log²。

13.

由 5 个不同的结点构成的无根树有（ ）种。 A. 3125　B. 125　C. 32　D. 1024

答案：B 解：Cayley n^{n-2}=5³=125。 注意点：结点不同 = 标号树；无标号才 3 种。

14.

2019 年 10 月 14 日是星期一，1978 年 10 月 14 日是（ ）。 A. 星期日　B. 星期五　C. 星期一　D. 星期六

答案：D 解：1978-10-14 到 2019-10-14 共 41 年 + 10 个闰日（含 2000），14975%7=2，周一倒推 2 天即周六。 注意点：2000 是闰年；1980–2016 共 10 个闰日。

15.

有 9 个顶点的简单无向连通图最多有（ ）条边。 A. 40　B. 81　C. 72　D. 36

答案：D 解：9×8/2=36，连通不增加上限。 注意点：A40/B81/C72 是定向 / 自环陷阱。

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

阅读 (1)

1  #include <iostream>
2  using namespace std;
3  int n,m,i,j,a,b,head,tail,ans;
4  int graph[100][100];
5  int degree[100];
6  int len[100];
7  int queue[100];
8  int main() {
9    cin >> n >> m;
10   for (i=0; i<n; i++)
11     for (j=0; j<n; j++) graph[i][j] = 0;
12   for (i=0; i<n; i++) degree[i] = 0;
13   for (i=0; i<m; i++) {
14     cin >> a >> b;
15     graph[a][b]=1;
16     degree[b]++;
17   }
18   tail = 0;
19   for (i=0; i<n; i++)
20     if (!degree[i]) {
21       queue[tail] = i;
22       tail++;
23     }
24   head=0;
25   while (tail < n) {
26     for (i=0; i<n; i++)
27       if (graph[queue[head]][i] == 1) {
28         degree[i]--;
29         if (degree[i] == 0) {
30           queue[tail] = i;
31           tail++;
32         }
33       }
34     ++head;
35   }
36   ans = 0;
37   for (i=0; i<n; i++) {
38     a = queue[i];
39     len[a] = 1;
40     for (j=0; j<n; j++)
41       if (graph[j][a] == 1 && len[j] + 1 > len[a])
42         len[a] = len[j] + 1;
43     if (len[a] > ans) ans = len[a];
44   }
45   cout << ans << endl;
46   return 0;
47 }

■判断题

1. 输入时将 degree[b]++ 改为 degree[a]++，则运行结果不变。　（ ）
2. 该程序的时间复杂度是 O(n)。　（ ）
3. 删除主函数开头对 graph 和 degree 执行清零操作的代码，程序输出不变。　（ ）
4. 若有以下数据，则输出为 3。　（ ）

   4 5
   0 2
   1 3
   0 1
   0 3
   2 3

■选择题

1. graph 存储的是（ ）。 A. 用邻接矩阵存储的图结构　B. 每个结点的入度 C. 拓扑排序结果　D. 以各结点为终点的最长路径长度
2. 这个程序用了（ ）。 A. 基数排序　B. 归并排序　C. 拓扑排序　D. 堆排序

答案：16.X　17.X　18.√　19.√　20.A　21.C 解：邻接矩阵存 DAG，先 Kahn 求拓扑序 queue，再 len[a]=max(len[前驱]+1)，ans 为最长点数。16 改成 degree[a]++ 后入度全错；17 两重 n 循环是 O(n²+m)；18 全局数组默认 0；19 边为 0→2,1→3,0→1,0→3,2→3，最长 0-1-3 长 3。 注意点：第 41 行 graph[j][a] 用结点号当下标，仅当拓扑序恰为数字序时 coincidental 正确，本卷数据满足。

阅读 (2)

1  #include <iostream>
2  #include <string>
3  #define LL long long
4  using namespace std;
5  LL l, r, f[12][10][10][2][2][2], a[20];
6  LL Dfs(LL now, LL p, LL pp, LL _4, LL _8, LL top, LL hw) {
7    if (_4 && _8) return 0;
8    if (!now) return hw;
9    if (!top && f[now][p][pp][_4][_8][hw] != -1)
10     return f[now][p][pp][_4][_8][hw];
11   LL Up = top ? a[now] : 9;
12   LL ret(0);
13   for (LL i=0; i<=Up; ++i)
14     ret += Dfs(now-1, i, p, _4||(i==4), _8||(i==8),
15                top && (i == Up), hw||(pp==p && p==i));
16   if (!top) f[now][p][pp][_4][_8][hw] = ret;
17   return ret;
18 }
19
20 inline LL Solve(LL x) {
21   LL tot(0);
22   while (x) {
23     a[++tot] = x % 10;
24     x /= 10;
25   }
26   if (tot != 11) return 0;
27   LL ret(0);
28   for (LL i=1; i<=a[tot]; ++i)
29     ret += Dfs(tot-1, i, 0, (i==4), (i==8), i==a[tot], 0);
30   return ret;
31 }
32
33 int main() {
34   cin >> l >> r;
35   memset(f, -1, sizeof(f));
36   cout << Solve(r) - Solve(l-1) << endl;
37   return 0;
38 }

■判断题

1. 同时包含 4 和 8 的数都不可能被统计。　（ ）
2. 相邻数位中，超过 3 个位相同的数都不可能被统计。　（ ）

■选择题

1. 下列选项中，（ ）是合法（可能被统计）的数。 A. 2323234823　B. 1015400080　C. 23333333333　D. 10010012022
2. 当输入 12121284000 12121285550 时，程序输出结果为（ ）。 A. 5　B. 457　C. 455　D. 6

答案：22.√　23.X　24.C　25.A 解：数位 DP，统计 11 位数中“不同时出现 4 和 8、且含连续 3 位相同”的个数。Dfs(now,p,pp,_4,_8,top,hw)：_4&&_8 剪 0，!now 返回 hw，hw|=（pp==p&&p==i） 检连续 3 同。Solve(x) 要求 tot==11，答案 Solve(r)-Solve(l-1)。22 即第 7 行；23 中 4 连同必然含 3 连同，反而能被统计，“都不能”错。24：A/B 只有 10 位（tot!=11 return 0）且都同时含 4、8；D 无 3 连同（hw=0）；只有 C 11 位、无 4/8、有 3 连同。25：区间只有 1551 个数，前缀 1212128 固定且已有 8，故后缀禁 4，千位只能取 5；555* 只有 85550 一个（再大超上限）；85XXX 型后三位同只有 5000,5111,5222,5333 四个（5444 含 4 排除，5555 超上限），共 5 个。 注意点：hw 是“有 3 连”才计数，别理解反；tot!=11 直接 0 是大坑；前导已有 8 则后边禁 4。

阅读 (3)

1  #include <iostream>
2  using namespace std;
3  int n, i, j, x, y, nx, ny;
4  int a[40][40];
5  int main() {
6    for (i=0; i<40; i++)
7      for (j=0; j<40; j++) a[i][j] = 0;
8    cin >> n;
9    y = 0;
10   x = n - 1;
11   n = 2 * n - 1;
12   for (i=1; i<=n*n; i++) {
13     a[y][x] = i;
14     ny = (y - 1 + n) % n;
15     nx = (x + 1) % n;
16     if ((y == 0 && x == n-1) || a[ny][nx] != 0)
17       y = y + 1;
18     else {
19       y = ny; x = nx;
20     }
21   }
22   for (j=0; j<n; j++) cout << a[0][j] << " ";
23   cout << endl;
24   return 0;
25 }

■判断题

1. 输入 n 时，输出的数字个数为 2n。　（ ）
2. 输入 1 时，结果为 1。　（ ）

■选择题

1. 若输入 3，则输出是（ ）。 A. 17 24 1 8 15　B. 1 8 24 17 15　C. 15 24 17 8 1　D. 24 17 8 1 15
2. 若输入 5，则输出的个数是（ ）。 A. 6　B. 9　C. 8　D. 5
3. 若输入 4，则输出结果的和是（ ）。 A. 175　B. 200　C. 150　D. 120
4. 若输入 2，则输出是（ ）。 A. 8 6 1　B. 8 1 6　C. 6 1 8　D. 1 8 6

答案：26.X　27.√　28.A　29.B　30.A　31.B 解：奇数幻方 Siamese：输入 n0 变 n=2*n0-1，从顶行中列开始右上走，撞墙或被占则下移；最后只输出 a[0][*]。26 输出 2n0-1 个；27 输入 1 → n=1 输出 1；28 输入 3 → 5 阶首行 17 24 1 8 15；29 输入 5 → 9 阶 → 9 个数；30 输入 4 → 7 阶，幻和 7×(49+1)/2=175；31 输入 2 → 3 阶首行 8 1 6。 注意点：x=n-1 用的是旧 n，恰为新 n 的中列；程序只打首行，别当整个方阵数。

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

完善 (1) 循环赛日程表

设有 N 名选手进行循环比赛，其中 N=2ᵐ，要求每名选手与其他 N-1 名选手各赛一次，每名选手每天比赛一次，循环赛共进行 N-1 天，每天都没有选手轮空。输入一个正整数 M，输出表格形式的比赛安排表，一行各数据间用一个空格隔开。

样例输入：3 样例输出：

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

其中 0 行表示队伍编号，第 1~N-1 行表示各轮对手的编号。

1  #include <cstdio>
2  using namespace std;
3  const int MAXN = 1026;
4  int a[MAXN][MAXN], m;
5
6  int main() {
7    scanf("%d", &m);
8    int n = 1 << m, k = 1, half = 1;
9    ①;
10   while (k <= m) {
11     for (int i=0; i<half; i++) {
12       for (int j=0; j<half; j++) {
13         a[i][②] = ③;
14       }
15     }
16     for (int i=0; i<half; i++) {
17       for (int j=0; j<half; j++) {
18         a[i+half][j] = ④;
19         a[i+half][j+half] = a[i][j];
20       }
21     }
22     ⑤;
23     k++;
24   }
25   for (int i=0; i<n; i++) {
26     for (int j=0; j<n; j++) {
27       printf("%d", a[i][j]);
28     putchar('\n');
29   }
30   return 0;
31 }

1. ①处应填（ ）。 A. a[0][1] = 1　B. a[0][0] = 1　C. a[1][0] = 1　D. a[1][1] = 1
2. ②处应填（ ）。 A. 1　B. i+half　C. j　D. j+half
3. ③处应填（ ）。 A. a[i][j] - half　B. a[i][j+1] - half　C. a[i][j] + half　D. a[i1][j1] + half
4. ④处应填（ ）。 A. a[i][j+half]　B. a[i+half][j+half]　C. a[i+half][j]　D. a[i][j]
5. ⑤处应填（ ）。 A. half /= 2　B. half *= 2　C. half += 2　D. half -= 2

答案：32.B　33.D　34.C　35.A　36.B 解：分治复制：右上 = 左上 + half，左下 = 右上，右下 = 左上，half 翻倍。 注意点：样例首行是队号；half 每轮翻倍。

完善 (2) 银河英雄传说（带权并查集）

阪杨 cok 某因贝特率领的帝国军与杨威利的自由行星同盟军在某星系开战。开战前，每一艘战舰都编了号。这次决战中，杨威利每次发布合并指令，将某两部分舰队集中在某星系上，实施密集攻击。合并指令为 M i j，含义为第 i 号战舰所在的整个舰队，作为一个整体（头在前尾在后）接至第 j 号战舰所在的整个舰队的尾部。询问指令为 C i j，含义是询问第 i 号战舰与第 j 号战舰当前是否在同一列，如果在同一列，那么它们之间有多少艘战舰。

1  #include <bits/stdc++.h>
2  using namespace std;
3  int fa[30001], front[30001], num[30001], x, y, i, n, j, m, T, ans;
4  char ins;
5  int find(int n) {
6    if (fa[n] == n) return fa[n];
7    int fn = find(fa[n]);
8    ①;
9    return fa[n] = fn;
10 }
11
12 int main() {
13   cin >> T;
14   for (i=1; i<=30000; ++i) {
15     fa[i] = i;
16     ②;
17     num[i] = 1;
18   }
19   while (T--) {
20     cin >> ins >> x >> y;
21     int fx = find(x), fy = find(y);
22     if (ins == 'M') {
23       front[fx] += num[fy];
24       fa[fx] = fy;
25       ③;
26       ④;
27     }
28     if (ins == 'C') {
29       if (⑤)
30         cout << "-1" << endl;
31       else
32         cout << ⑥ << endl;
33     }
34   }
35   return 0;
36 }

1. ①处应填（ ）。 A. front[n] += front[fa[n]]　B. front[n] += front[n] C. front[n] += front[fa[n]]（印刷重影，以逻辑为准）　D. front[fa[n]] += front[fa[n]]
2. ②处应填（ ）。 A. front[i] = 1　B. front[i] = 0　C. front[i] = i　D. front[fa[i]] = 0
3. ③处应填（ ）。 A. num[fx] += num[fy]　B. num[fy] += num[fy]　C. num[fx] += num[fx]　D. num[fy] += num[fx]
4. ④处应填（ ）。 A. fx > fy　B. fx == fy　C. fx < fy　D. fx != fy
5. ⑤⑥处应填（ ）。 A. abs(front[x]-front[y])-1　B. abs(front[x]-front[y])+1 C. abs(front[num[x]]-front[num[y]])-1　D. abs(front[num[x]]-front[num[y]])+1

答案：37.A　38.B　39.D　40.D　41.A（⑤为 fx!=fy，⑥为 abs(front[x]-front[y])-1） 解：front 为到队首距离，num 为队大小。回溯时 front[n]+=front[fa[n]]；初值 0；M 是 fx 挂到 fy，先加 num[fy]，即 num[fy]+=num[fx]；C 查询要 find 后比 front 差，异根 -1，同根差值 -1。 注意点：M 是 fx 挂到 fy，别加反；C 查询要先 find 再比 front。