试卷解析 · 理解每一步

提高组 CSP-S 2026 初赛模拟卷 3

CSPS-2026-R1-Mock-3

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

今有一空栈 S，对下列待进栈的数据元素序列 1,2,3,4,5, $\cdots$ 进行以“进栈、进栈、出栈、进栈、进栈、进栈、出栈”为一轮的操作，一直操作下去，那么在 2019 轮操作后，S 的栈顶元素为（）。

10090

10094

10100

10086

正确答案B

解析详情

答案 B栈操作模拟

思路与推导

一个循环节内总共进栈 5 次，出栈 2 次，则最后一轮入栈的 5 个数是 10091, …, 10095，最后一次出栈的是 10095，剩下栈顶是 10094。

第 2 题（单选题，2 分）

对有序数组 $\{5,13,19,21,37,56,64,75,88,92,100\}$ 进行二分查找，等概率的情况下，查找成功的平均查找长度（平均比较次数）是（）。

35/11

34/11

34/10

正确答案C

解析详情

答案 C二分查找平均查找长度

思路与推导

总共 11 个数，所以分母肯定是 11 的约数，排除选项 D。一种方法是暴力模拟出 11 种取值各自的查找次数，然后求平均数。好一点的方法是利用递推式，11 查 1 次后有 1/11 的概率直接命中，有 10/11 的概率要在 5 个数里再找，即 $E(11) = 1 + E(5) \times 10/11$ 。同理 $E(5) = 1 + E(2) \times 4/5$ ，而 $E(2) = 3/2$ ，则倒推出 $E(5) = 1 + 3/2 \times 4/5 = 1 + 6/5 = 11/5$ ， $E(11) = 1 + 11/5 \times 10/11 = 1 + 2 = 3$ 。

第 3 题（单选题，2 分）

以下选项中各有三个数，其中第一个为八进制数，第二个为十进制数，第三个为十六进制数。以下选项中三个数相同的是（）。

120 82 50

144 100 68

300 200 C8

1762 1010 3F2

正确答案D

解析详情

答案 D进制转换

思路与推导

都转成十进制暴力验证即可。

第 4 题（单选题，2 分）

将 $\{2,6,10,17\}$ 分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 $h(x)=$ （），将不会产生冲突。

x \bmod 11

x^{2} \bmod 11

2x \bmod 11

\lfloor \sqrt{x} \rfloor \bmod 11

正确答案D

解析详情

答案 D哈希函数

思路与推导

验证各 $h(x)$ 互不相同即可，例如选项 A 中，6 mod 11 = 17 mod 11。而选项 D 中算出来各 $h(x)$ 为 1, 2, 3, 4。

第 5 题（单选题，2 分）

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么有 12 个顶点的二分图至多有（）条边。

正确答案C

解析详情

答案 C二分图极值

思路与推导

设 n 个顶点的二分图两侧分别有 x 和 n-x 个顶点，则边数至多为 $x(n-x)$ 。由均值不等式，x 越接近 n/2，这个数越大。若 n=12，则 x=6 时边数最多，为 $6 \times 6 = 36$ 。

第 6 题（单选题，2 分）

有一个含有 k 个不同的数的数组 $S = \{x_1, x_2, \cdots, x_k\}$ 。若在 S 中有一个数 $x_i$ ( $1 < i < k$ ) 使得 $x_1 < x_2 < \cdots < x_i > x_{i+1} > \cdots > x_k$ ，则称 $x_i$ 为 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, c, b, d, e

a, d, b, c, e

b, e, a, d, c

b, e, a, c, d

正确答案C

解析详情

答案 C单峰数组二分查找

思路与推导

因为前两个 if 的可见部分是一样的，所以只能看两空的关联关系；条件 b 说明 mid 就是峰值，必然对应 e；同理，条件 a 说明峰值在右侧，对应 d；那么剩下的 c 只能在最后那个 else 处。符合的只有选项 C。

第 7 题（单选题，2 分）

如果不在快速排序中引入随机化，可能导致的后果是（）。

数组访问越界

陷入死循环

排序结果错误

排序时间退化为平方级

正确答案D

解析详情

答案 D快速排序随机化

思路与推导

随机化只是为避免轴点选择有系统偏差（例如总是选到最小值），导致复杂度退化，但不会引起算法出错或异常。

第 8 题（单选题，2 分）

二进制数 $-1101010$ 的补码是（）。

0010101

10010110

10010101

01101010

正确答案B

解析详情

答案 B补码表示

思路与推导

补码规则：绝对值各位取反再加一：01101010 → 10010101 → 10010110。

第 9 题（单选题，2 分）

设二进制数 x 的值是 11001101。若想通过 x&y 运算使 x 中的低 4 位不变，高 4 位清零，则 y 的二进制数是（）。

11110000

00001100

00001111

00000010

正确答案C

解析详情

答案 C位掩码

思路与推导

y 就是所谓掩码，需要清零的位取 0，需要保持的位取 1。与 x 本身的值无关。

第 10 题（单选题，2 分）

循环链表的主要优点是（）。

不需要头指针

已知某个节点的位置后，能很容易地找到它的直接前驱节点

在进行删除操作后，能保证链表不断开

从表中任一节点出发都能遍历整个链表

正确答案D

解析详情

答案 D循环链表

思路与推导

选项 A 直接是错的，链表都需要头指针，否则无法访问；选项 B 是双向链表的优点；选项 C 是所有链表的公共特征，非循环链表独有；选项 D 是循环链表最典型的优点（虽然双向链表通过变通的方式也能实现遍历，但不如循环链表方便）。

第 11 题（单选题，2 分）

若某算法的计算时间表示为递推关系式 $T(N) = N + T(N/2)$ ，则该算法的时间复杂度为（）。

O(N^{2})

O(N \log N)

O(N)

O(1)

正确答案C

解析详情

答案 C递推式复杂度

思路与推导

主定理直接结论，如不知道主定理也可以代值估算，例如 $T(64) = 64 + 32 + 16 + 8 + 4 + 2 + 1 + T(0)$ 。

第 12 题（单选题，2 分）

若某算法的计算时间表示为递推关系式 $T(n) = 3T(n/4) + n \log_{2} n$ ，则该算法的时间复杂度为（）。

O(n)

O(n \log_{2} n)

O(n \log_{2}^{2} n)

O(n \log_{3}^{2} n)

正确答案B

解析详情

答案 B主定理

思路与推导

主定理结论，因为 $n \log_2 n > O(n^{\log_4 3})$ ，所以最终复杂度与加的那项一样。

第 13 题（单选题，2 分）

由 5 个不同的节点构成的无根树有（）种。

3125

125

1024

正确答案B

解析详情

答案 B标号树计数

思路与推导

公式为 $n^{n-2}=5^3=125$ ，原理是 Prufer 序列。如果不知道结论，就手动分类讨论。首先
列出 5 个节点的无根树形态（如星型、链型等，不是很多），再分别统计编号方案，例如链型的有 5!/2 = 60 种。

第 14 题（单选题，2 分）

2019年10月14日是星期一，1978年10月14日是（）。

星期日

星期五

星期一

星期六

正确答案D

解析详情

答案 D日期与星期

思路与推导

首先 365% 7 = 1，对一般年份，每退一年星期数倒走一天，本题总共退 41 年，即星期数退 6 天，再加上其中有 10 个闰年，再额外退 10 天，最终是星期六。

第 15 题（单选题，2 分）

有 9 个顶点的简单无向连通图最多有（）条边。

正确答案D

解析详情

答案 D完全图边数

思路与推导

无向完全图，边数为 $C_{9}^{2}=36$ 。

二、阅读程序（1）

#include <iostream>
using namespace std;

int n, m, i, j, a, b, head, tail, ans;
int graph[100][100];
int degree[100];
int len[100];
int queue[100];

int main() {
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) graph[i][j] = 0;
    for (i = 0; i < n; i++) degree[i] = 0;
    for (i = 0; i < m; i++) {
        cin >> a >> b;
        graph[a][b] = 1;
        degree[b]++;
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if (!degree[i]) {
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n) {
        for (i = 0; i < n; i++)
            if (graph[queue[head]][i] == 1) {
                degree[i]--;
                if (degree[i] == 0) {
                    queue[tail] = i;
                    tail++;
                }
            }
        ++head;
    }
    ans = 0;
    for (i = 0; i < n; i++) {
        a = queue[i];
        len[a] = 1;
        for (j = 0; j < n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if (len[a] > ans) ans = len[a];
    }
    cout << ans << endl;
    return 0;
}

第 16 题（判断题，2 分）

输入时若将 degree[b]++ 改为 degree[a]++, 则运行结果不变。（）

正确答案错误

解析详情

答案错误拓扑排序与 DAG 最长路

思路与推导

如统计出度，求出的是拓扑排序的逆序，相当于将一切反向。虽然这个操作不影响最长路径的长度，但后续计算 len 时仍然是按原图的顺序写的，所以答案会出错。如将 if（graph[j][a] == 1）同时改为 if（graph[a][j] == 1），则结果也是对的。

第 17 题（判断题，2 分）

该程序的时间复杂度是 O(n)。

正确答案错误

解析详情

答案错误拓扑排序与 DAG 最长路

思路与推导

拓扑排序和无环图上递推的时间复杂度都是 $O(n + m)$ ，其中 n 是顶点数，m 是边的数量。一段一般性的图论代码的复杂度也不可能与 m 无关（特殊规则生成的图除外）。

第 18 题（判断题，2 分）

删除主函数开头对 graph 和 degree 执行清零操作的代码，程序输出不变。（）

正确答案正确

解析详情

答案正确拓扑排序与 DAG 最长路

思路与推导

语法上，全局变量自动清零，所以效果一样。但逻辑上定义每个变量必须考虑到其初始化。如果是包含多组输入数据的题目，则必须每次手动重新初始化。

第 19 题（判断题，2 分）

若输入以下数据，则输出为 3。（）

正确答案正确

解析详情

答案正确拓扑排序与 DAG 最长路

思路与推导

最长路径长度为 3（包含 3 个节点，例如 $0 \to 1 \to 3$ ）。

第 20 题（单选题，3 分）

graph 存储的是（）。

用邻接矩阵存储的图结构

每个节点的入度

拓扑排序结果

以各节点为终点的最长路径长度

正确答案A

解析详情

答案 A拓扑排序与 DAG 最长路

思路与推导

选项 A、B、C、D 对应的变量分别为：graph、degree、queue、len。

第 21 题（单选题，3 分）

这个程序使用了（）。

基数排序

归并排序

拓扑排序

堆排序

正确答案C

解析详情

答案 C拓扑排序与 DAG 最长路

思路与推导

拓扑排序，先找到度为0的节点，从这个节点开始去掉邻接节点的入边，再找到度为0的节点入队，反复执行这个过程。

二、阅读程序（2）

#include <iostream>
#include <cstring>
#define LL long long
using namespace std;

LL l, r, f[12][10][10][2][2][2], a[20];

LL Dfs(LL now, LL p, LL pp, LL _4, LL _8, LL top, LL hw) {
    if (_4 && _8) return 0;
    if (!now) return hw;
    if (!top && f[now][p][pp][_4][_8][hw] != -1)
        return f[now][p][pp][_4][_8][hw];
    LL Up = top ? a[now] : 9;
    LL ret(0);
    for (LL i = 0; i <= Up; ++i)
        ret += Dfs(now - 1, i, p, _4 | (i == 4), _8 | (i == 8),
                   top && (i == Up), hw | (i == pp && i == p));
    if (!top) f[now][p][pp][_4][_8][hw] = ret;
    return ret;
}

inline LL Solve(LL x) {
    LL tot(0);
    while (x) {
        a[++tot] = x % 10;
        x /= 10;
    }
    if (tot != 11) return 0;
    LL ret(0);
    for (LL i = 1; i <= a[tot]; ++i)
        ret += Dfs(tot - 1, i, 0, (i == 4), (i == 8), i == a[tot], 0);
    return ret;
}

int main() {
    cin >> l >> r;
    memset(f, -1, sizeof(f));
    cout << Solve(r) - Solve(l - 1) << endl;
    return 0;
}

第 22 题（判断题，2 分）

同时包含 4 和 8 的数都不可能被统计。（）

正确答案正确

解析详情

答案正确数位动态规划

思路与推导

if ( _4 && _8) return 0; 这句对同时出现 4 和 8 的数返回计数 0。

第 23 题（判断题，2 分）

相邻数位中，超过3个数位相同的数都不可能被统计。（）

正确答案错误

解析详情

答案错误数位动态规划

思路与推导

if (!now) return hw; 这句说明当 hw=1 时才会返回计数 1,也就是只计入 hw=1 的情况。

第 24 题（单选题，3 分）

下列选项中，( )是合法（可能会被统计）的数。

2323234823

1015400080

23333333333

10010012022

正确答案C

解析详情

答案 C数位动态规划

思路与推导

选项 A、B 同时包含 4 和 8，选项 D 没有连续的 3 位数值相同。

第 25 题（单选题，3 分）

当输入 12121284000 12121285550 时，程序输出结果为（）。

457

455

正确答案A

解析详情

答案 A数位动态规划

思路与推导

这个范围内其实只有 1500 多个数，未固定的只有末四位，千位只可能取 4 和 5。但前面又有过 8，所以千位只能取 5。又要求有 3 位数值相同，于是，只有两类情况：555* 和 5***。前者只有 5550 一个（再大就超过上限了）；后者有 5000，5111，5222，5333 四个（5444 因为不能含 4 而排除）。总计五个。

二、阅读程序（3）

#include <iostream>
using namespace std;

int main() {
    int n, i, j, x, y, nx, ny;
    int a[40][40];
    for (i = 0; i < 40; i++)
        for (j = 0; j < 40; j++) a[i][j] = 0;
    cin >> n;
    y = 0;
    x = n - 1;
    n = 2 * n - 1;
    for (i = 1; i <= n * n; i++) {
        a[y][x] = i;
        ny = (y - 1 + n) % n;
        nx = (x + 1) % n;
        if ((y == 0 && x == n - 1) || a[ny][nx] != 0)
            y = y + 1;
        else {
            y = ny;
            x = nx;
        }
    }
    for (j = 0; j < n; j++) cout << a[0][j] << " ";
    cout << endl;
    return 0;
}

第 26 题（判断题，2 分）

输入 n 时，输出的数字个数为 2n。（）

正确答案错误

解析详情

答案错误奇数阶幻方模拟

思路与推导

是 2n-1，代码中对 n 只有这一次更新。

第 27 题（判断题，2 分）

输入1时，结果为1。（）

正确答案正确

解析详情

答案正确奇数阶幻方模拟

思路与推导

模拟即可。

第 28 题（单选题，3 分）

若输入 3，则输出是（）。

17 24 1 8 15

1 8 24 17 15

15 24 17 8 1

24 17 8 1 15

正确答案A

解析详情

答案 A奇数阶幻方模拟

思路与推导

根据幻方填法模拟可得。更讨巧的办法是注意正中间那个一定是1，只有选项A符合。

第 29 题（单选题，3 分）

若输入 5，则输出的个数是（）。

正确答案B

解析详情

答案 B奇数阶幻方模拟

思路与推导

$5 \times 2 - 1 = 9$

第 30 题（单选题，3 分）

若输入 4，则输出结果的总和是（）。

175

200

150

120

正确答案A

解析详情

答案 A奇数阶幻方模拟

思路与推导

强行模拟也不是不可以，虽然比较费事。根据幻方特征，每行之和一样，所以总和为 $(1 + 2 + \cdots + 49)/7 = 175$ 。

第 31 题（单选题，3 分）

若输入2，则输出是（）。

8 6 1

8 1 6

6 1 8

1 8 6

正确答案B

解析详情

答案 B奇数阶幻方模拟

思路与推导

模拟即可。

三、完善程序（1）

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

样例输入：3样例输出：

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

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

#include <cstdio>
using namespace std;

const int MAXN = 1025;
int a[MAXN][MAXN], m;

int main() {
    scanf("%d", &m);
    int n = 1 << m, k = 1, half = 1;
    ①;
    while (k <= m) {
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                a[i][②] = ③;
            }
        }
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                a[i + half][j] = ④;
                a[i + half][j + half] = a[i][j];
            }
        }
        ⑤;
        k++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%d ", a[i][j]);
        putchar('
');
    }
    return 0;
}

第 32 题（单选题，3 分）

①处应填（）。

a[0][1] = 1

a[0][0] = 1

a[1][0] = 1

a[1][1] = 1

正确答案B

解析详情

答案 B循环比赛日程表

思路与推导

初始时表格大小为 $1 \times 1$ ，根据代码可知，从 0 开始标号，所以 a[0][0] = 1。

第 33 题（单选题，3 分）

②处应填（）。

i

i+half

j

j+half

正确答案D

解析详情

答案 D循环比赛日程表

思路与推导

因为第一维已经填了 i，说明是右上角分块， $a[i][j+\text{half}] = a[i][j] + \text{half}$ 。

第 34 题（单选题，3 分）

③处应填（）。

a[i][j] - half

a[i][j + 1] - half

a[i][j] + half

a[i][j + 1] + half

正确答案C

解析详情

答案 C循环比赛日程表

思路与推导

参考上题。

第 35 题（单选题，3 分）

④处应填（）。

a[i][j+half]

a[i+half][j+half]

a[i+half][j]

a[i][j]

正确答案A

解析详情

答案 A循环比赛日程表

思路与推导

左下角分块，填的值与右上角相同。这里填 a[i][j] + half 也是对的。

第 36 题（单选题，3 分）

⑤处应填（）。

half /= 2

half *= 2

half += 2

half -= 2

正确答案B

解析详情

答案 B循环比赛日程表

思路与推导

每次行和列都扩大一倍，所以是乘以2。

三、完善程序（2）

舰队司令莱因哈特率领十万余艘战舰出征，名将杨威利组织麾下三万艘战舰迎敌。在这次决战中，杨威利将巴米利恩星域战场划分成30 000列，每列依次编号为1..30 000。之后，他把自己的战舰也依次编号为1..30 000，让第i号战舰处于第i列，i=1..30 000。这是初始阵型。杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为Mij，含义为第i号战舰所在的整个战舰队列，作为一个整体（头在前，尾在后）接至第j号战舰所在的战舰队列的尾部。在杨威利发布指令调动舰队的同时，莱因哈特也会发出一些询问指令：Cij。该指令的意思是询问计算机，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少艘战舰。你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

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

int fa[30001], front[30001], num[30001], x, y, i, j, n, T, ans;
char ins;

int find(int n) {
    if (fa[n] == n) return fa[n];
    int fn = find(fa[n]);
    ①;
    return fa[n] = fn;
}

int main() {
    cin >> T;
    for (i = 1; i <= 30000; ++i) {
        fa[i] = i;
        ②;
        num[i] = 1;
    }
    while (T--) {
        cin >> ins >> x >> y;
        int fx = find(x), fy = find(y);
        if (ins == 'M') {
            front[fx] += num[fy];
            fa[fx] = fy;
            ③;
            num[fx] = 0;
        }
        if (ins == 'C') {
            if (④)
                cout << "-1" << endl;
            else
                cout << ⑤ << endl;
        }
    }
    return 0;
}

第 37 题（单选题，3 分）

① 对应填（）。

front[n] += front[fa[n]]

front[n] += front[n]

front[fa[n]] += front[n]

front[fa[n]] += front[fa[n]]

正确答案A

解析详情

答案 A带权并查集

思路与推导

从位置可以看出这里是对 front 进行路径压缩，将 fa[n] 的 front 加到 front[n] 上。那么 front 的含义也可推断出来，它代表节点前还有几艘同组战舰。
注意：虽然 front 这个变量名如此暗示，但实际上这里有微妙差异。在合并时，只修改了 front[fx] 一个，其子树内部的 front 没有改，也就是实际上只有根节点下第一层的 front 值才符合定义。但注意在最后使用 front 时，x, y 都已经 find() 过一次，而路径压缩会将其带到根节点下第一层的位置，所以结果才是对的。

第 38 题（单选题，3 分）

②处应填（）。

front[i] = 1

front[i] = 0

front[i] = i

front[fa[i]] = 0

正确答案B（另接受：D）

解析详情

答案 B带权并查集

思路与推导

结合 front 的含义，初始时，每个战舰前面的战舰数为 0。这道题其实有点小问题，因为选项 D 的实际效果是一样的（之前刚刚赋值 fa[i]=i），只能说从逻辑上来说，选项 A 更合理。

第 39 题（单选题，3 分）

③处应填（）。

num[fx] += num[fy]

num[fy] += num[fy]

num[fx] += num[fx]

num[fy] += num[fx]

正确答案D

解析详情

答案 D带权并查集

思路与推导

这里分组与合并同时进行，所以 num 表示分组大小，直接求和，合并方式是 fy 在前，fx 在后，所以是加到 num[fy]。

第 40 题（单选题，3 分）

④ 处应填（）。

fx > fy

fx == fy

fx < fy

fx != fy

正确答案D

解析详情

答案 D带权并查集

思路与推导

判断两个点不在一个分组，所以填 fx != fy，即所在分组的根节点不同。这是并查集的基本操作。

第 41 题（单选题，3 分）

⑤处应填（）。

abs(front[x]-front[y])-1

abs(front[x]-front[y])+1

abs(front[num[x]]-front[num[y]]])-1

abs(front[num[x]]-front[num[y]])+1

正确答案A

解析详情

答案 A带权并查集

思路与推导

x, y 前面的战舰个数相减再减一，得到它们之间的战舰个数。num 是组内战舰总数，front[num[x]] 没有意义。