试卷解析 · 理解每一步

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

CSPS-2026-R1-Mock-8

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

一、单项选择题

第 1 题（单选题，2 分）

十进制的 160.5 相当于十六进制的（）。

A0.8

F.5

80.25

无限小数

正确答案A

解析详情

答案 A计算机基础与数据结构算法

思路与推导

十进制 0.5 是十六进制的 0.8，也就是 1 的一半。

第 2 题（单选题，2 分）

在具有 2n 个节点的完全二叉树中，叶节点的个数为（）。

n-1

n+1

不能确定

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

具有偶数个节点的完全二叉树中，1度节点有且仅有1个。 $n_{2}=n_{0}+1$ ， $n_{1}+n_{0}=2n-1$ 。

第 3 题（单选题，2 分）

6个棋子围成一圈，每个棋子可染黑色或白色，通过旋转可重合的算一种方案，则一共有（）种着色方案。

正确答案D

解析详情

答案 D计算机基础与数据结构算法

思路与推导

严格说来要用波利亚定理，但由于规模只有6，不如分类枚举。
全黑/全白：2种；
1 黑 5 白或反之：2 种：
2 黑白或反之：6 种（110000,101000,100100）;
3黑3白：4种（111000,110100,110010,101010）。
因为只有旋转没有翻转，所以 110100 和 110010 算 2 种。

第 4 题（单选题，2 分）

假设 x 和 y 是两个独立的随机实数变量，且它们都是从 [0,1] 的均匀分布里随机生成的，则 $\min(x,y)$ 的期望值是（）。

\frac{1}{4}

\frac{1}{3}

\frac{1}{2}

不是有理数

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

猜测的话，首先因为取 min，所以肯定是小于 1/2 的，至于是 1/3 还是 1/4，如果不会精确计算的话，可以离散化然后枚举估算。例如从 0.1, 0.2, $\cdots$ , 0.9, 1.0 这十个数里选 2 个，再求 min 的平均值。严格计算可以利用几何意义，精确计算为函数 $z = \min(x, y)$ , $x, y \in [0,1]$ 。这个图像是 2 个三棱锥，期望值就是其体积， $2 \times 1/6 = 1/3$ 。

第 5 题（单选题，2 分）

设某算法的计算时间表示为递推关系式 $T(n)=T(n-1)+3n$ (n 为正整数)，且 $T(0)=1$ ，则该算法的时间复杂度为（）。

O(n)

O(n^{2})

O(n\log n)

O(n^{3})

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

$T(n)=3[n+(n-1)+\cdots+1]+T(0)=O(n^{2})$ 。

第 6 题（单选题，2 分）

在单链表指针 p 指向的节点后，插入指针 s 指向的节点，正确的操作是（）。

p->next = s; s->next = p->next;

s->next = p->next; p->next = s;

p->next = s; p->next = s->next;

p->next = s->next; p->next = s;

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

插入的时候首先要让新加入的 s 节点的 next 指向原先 p 的 next，然后再修改 p 的 next 指向 s。如果先改 p->next 则链表就断开了，原先 p->next 的信息就丢失了。

第 7 题（单选题，2 分）

前缀表达式 + 3 * 2 + 5 12 的值是（）。

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

$3+2*(5+12)=37$ 。

第 8 题（单选题，2 分）

若在某进制下 $7 \times 7 = 41$ 成立，那么在该进制下 $12 \times 12 = (\quad)$ 。

144

100

正确答案A

解析详情

答案 A计算机基础与数据结构算法

思路与推导

设进制数为 d，显然 d 肯定大于 7，所以一位数 7 就是十进制下的 7，则十进制下 $7 \times 7 = 49 = 4d + 1$ ，得 d = 12。十二进制下， $(12)_{12} = 14$ ，所以乘积为（十进制的）196，对应十二进制的 144。

第 9 题（单选题，2 分）

寄存器是（）的重要组成部分。

硬盘

高速缓存

内存

中央处理器（CPU）

正确答案D

解析详情

答案 D计算机基础与数据结构算法

思路与推导

常识。CPU 有控制器、运算器、寄存器。

第 10 题（单选题，2 分）

无向图 $G = (V, E)$ ，其中 $V = \{A_{0}, A_{1}, A_{2}, A_{3}\}$ ， $E = \{(A_{0}, A_{1}), (A_{0}, A_{2}), (A_{0}, A_{3}), (A_{1}, A_{3})\}$ 。以 $A_{0}$ 为起点进行深度优先搜索，遍历顺序不可能是（）。

A_{0}, A_{1}, A_{2}, A_{3}

A_{0}, A_{1}, A_{3}, A_{2}

A_{0}, A_{2}, A_{1}, A_{3}

A_{0}, A_{3}, A_{1}, A_{2}

正确答案A

解析详情

答案 A计算机基础与数据结构算法

思路与推导

从 $A_{0}$ 走到 $A_{1}$ 的话，因为 $A_{1}$ 与 $A_{3}$ 相邻而与 $A_{2}$ 不相邻，所以下一个不可能访问 $A_{2}$ 。

第 11 题（单选题，2 分）

双向链表的节点包含两个指针域 llink 和 rlink，分别指向其前驱节点和后继节点。设 p 指向链表中的一个节点，q 指向一待插入节点。现要求在 p 前插入 q，则正确的插入操作为（）。

p->llink = q;
q->rlink = p;
p->llink->rlink = q;
q->llink = p->llink;

q->llink = p->llink;
p->llink->rlink = q;
q->rlink = p;
p->llink = q->rlink;

q->rlink = p;
p->rlink = q;
p->llink->rlink = q;
q->rlink = p;

p->llink->rlink = q;
q->rlink = p;
q->llink = p->llink;
p->llink = q;

正确答案D

解析详情

答案 D计算机基础与数据结构算法

思路与推导

因为步骤有点多，而这里需要改 4 个指针，可行方案并非唯一，所以最实际的方法是画个图逐选项模拟一下。纸面分析的话，选项 A 中第一步先改 p->llink，导致其原先的前驱信息丢失（断链）；选项 B 前 3 步都没问题，但最后一步修改 p->llink 应指向 q 而不是 q->rlink，后者前面已经指向 p 本身了，所以不对；选项 C，因为要求是插入在 p 前，所以 p->rlink 不应修改；选项 D 可通过模拟发现是对的。

第 12 题（单选题，2 分）

有向图 $G = (V, E)$ ，其中 $V = \{A_0, A_1, A_2, A_3, A_4\}$ ，从顶点 $A_0$ 出发进行广度优先搜索（BFS），一种可行顺序是 $A_0, A_4, A_2, A_3, A_1$ 。我们以 $(x, y)$ 表示 x 指向 y 的有向边，则边集 E 可能是（）。

\{(A_0, A_1), (A_0, A_2), (A_0, A_3), (A_0, A_4), (A_2, A_1), (A_2, A_3)\}

\{(A_0, A_1), (A_0, A_3), (A_1, A_2), (A_2, A_3), (A_3, A_4)\}

\{(A_0, A_1), (A_0, A_2), (A_0, A_4), (A_2, A_1), (A_2, A_3), (A_3, A_4)\}

\{(A_0, A_1), (A_0, A_2), (A_0, A_3), (A_2, A_1), (A_2, A_3), (A_3, A_4)\}

正确答案A

解析详情

答案 A计算机基础与数据结构算法

思路与推导

本题最好是将选项画出图来再验证。具体地， $A_{0}$ 首先要与 $A_{4}$ 相邻，可排除选项 B 和 D；而选项 C 中， $A_{4}$ 是唯一一个到 $A_{0}$ 的距离为 2 的，应该排在最后，也排除。

第 13 题（单选题，2 分）

一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根节点的左子树的节点个数可能是（）。

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

本题逐项代入验证更方便。例如选项 A，BCDEFG 和 CBFEGD 会使右子树的前后序遍历匹配冲突，这样根节点就会不一致（选项 B 和 D），所以排除；选项 C 和 D 也同理可排除；而选项 B 验证这样的二叉树存在，左子树为 BC/CB，右子树为 DEFG/FEGD。

第 14 题（单选题，2 分）

由 3 个 a、5 个 b 和 2 个 c 构成的所有字符串中，包含子串 abc 的共有（）个。

840

820

800

780

正确答案D

解析详情

答案 D计算机基础与数据结构算法

思路与推导

先求子串中至少含一个 abc 的情况数：扣去 1 个 abc 后剩下 2 个 a、4 个 b、1 个 c，还有 1 个 abc 整体，这 8 个对象进行可重排列，共 $8!/(2!\times4!)=840$ 种；再扣除含有 2 个 abc 的情况（被重复计算了一次），同理有 2 个 abc 整体，1 个 a，3 个 b，共 6 个对象重排列，有 $6!/(3!\times2!)=60$ 种。最后答案为 840 - 60 = 780 种。

第 15 题（单选题，2 分）

拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列，使得对于图中任意一对顶点 u 和 v，若从 u 到 v 有边，则 u 在线性序列中出现在 v 之前。这样的线性序列称为拓扑序列。对有向无环图 $G = (V, E)$ ， $V = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ， $E = \{(1, 2), (1, 5), (2, 3), (3, 4), (3, 7), (4, 6), (7, 6), (8, 9)\}$ ，可能的拓扑序列的个数为（）。

336

432

343

正确答案B

解析详情

答案 B计算机基础与数据结构算法

思路与推导

拓扑序计数本身是没有什么高效方法的，所以只能根据具体情况分类讨论 + 枚举。首先可画出原图。注意 12376 是一条链，只能顺序排列。4 需要排在 3 之后，6 之前，所以只有 2 个位置可放，即 123476 和 123746。接下来 5 要插入在 1 以后，共有 6 种方案，目前为 $2 \times 6 = 12$ 种。接下来 8 和 9 在已有的 7 个数的空隙（含首尾共 8 个位置）中找 2 个，可以重复，有 $C_{9}^{2} = 36$ 种（8 必须在 9 后，所以 8 和 9 的相对顺序只有 1 种），最终为 $12 \times 36 = 432$ 。

二、阅读程序（1）

#include <iostream>
using namespace std;
int n;

int main() {
    cin >> n; // 保证输入为正整数
    int ans = n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            ans = ans / i * (i - 1);
        }
    }
    cout << ans << endl;
    return 0;
}

第 16 题（判断题，1 分）

该算法的时间复杂度为 O(n)。

正确答案正确

解析详情

答案正确欧拉函数

思路与推导

while 部分每执行一次 n 至少变小一半，所以 n/=i 至多执行 log n 次，而其他部分的复杂度显然不高于 O(n)。

第 17 题（判断题，1 分）

输出的数一定不会比 n 大。

正确答案正确

解析详情

答案正确欧拉函数

思路与推导

ans 开始为 n，全局只可能除，所以不可能变大。

第 18 题（判断题，2 分）

如果 n > 2，则输出一定是偶数。

正确答案正确

解析详情

答案正确欧拉函数

思路与推导

如果 n 是奇数且大于 1，则只会除以奇数而乘偶数（至少一次），所以结果为偶数；如果 n 是偶数，除了有一次除以 2，其他也都是除以奇数而乘偶数。所以唯一输出为奇数的情况只有 n = 1,2。

第 19 题（判断题，2 分）

如果 n 是素数，则输出就是 n。

正确答案错误

解析详情

答案错误欧拉函数

思路与推导

是 n-1。可代入 n = 2 验证。

第 20 题（单选题，3 分）

输入 1001 时，输出为（）。

1024

1000

720

512

正确答案C

解析详情

答案 C欧拉函数

思路与推导

1001 = 7*11*13, ans = 1001*6/7*10/11*12/13 = 720.

第 21 题（单选题，3 分）

依次输入 1~20，则输出的最大值为（）。

正确答案D

解析详情

答案 D欧拉函数

思路与推导

n = 19 时 ans = 18.

二、阅读程序（2）

#include <iostream>
#include <string>
using namespace std;

int n, x[100];
string s[100];

int main() {
    while (cin >> s[++n]);
    n--;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < s[i].size(); j++)
            x[i] = x[i] * x[i] + s[i][j];
    int ans = n;
    for (int i = n; i >= 1; i--) {
        bool b = 0;
        for (int j = 1; j < i && !b; j++)
            if (x[i] == x[j]) b = true;
        ans -= b;
    }
    cout << ans << endl;
    return 0;
}

第 22 题（判断题，2 分）

输入的时候如果有多行，则只会读入第一行。（）

正确答案错误

解析详情

答案错误字符串哈希与去重

思路与推导

语法常识。此种写法会一直输入到输入文件结尾（或者说输入流终止）。

第 23 题（判断题，2 分）

第二组 for 循环（int ans = n；之后开始的）的时间复杂度可以优化到 $O(n \log n)$ 。()

正确答案正确

解析详情

答案正确字符串哈希与去重

思路与推导

排序去重即可。

第 24 题（判断题，2 分）

如果只输入小写字母，且所有 $s[i].size() <= 10$ ，则 $x[i]$ 最终的值都是正数。（）

正确答案错误

解析详情

答案错误字符串哈希与去重

思路与推导

x 自乘 10 次基本上肯定会溢出，所以大概率有负数。但作为只要比较是否相同的哈希值，溢出成负数也不影响正确性。

第 25 题（判断题，2 分）

输入 in dzds left brain there is nothing left while in his right there is nothing right，并将第12行改为x[i] = x[i] * x[i] * x[i] + s[i][j]；输出不会有变化。

正确答案正确

解析详情

答案正确字符串哈希与去重

思路与推导

只是换了一种哈希函数，不影响相同的 s[i] 对应的 x[i] 也相同。虽然哈希可能有理论上的冲突概率，但在这个具体输入中，只有十几个单词，出现冲突的概率微乎其微。

第 26 题（单选题，3 分）

输入 in theory theory and practice are the same in practice they are not, 输出为（）。

正确答案C

解析详情

答案 C字符串哈希与去重

思路与推导

一共出现9个不同单词。

第 27 题（单选题，3 分）

以下描述中错误的是（）。

输出的时候，ans 的值一定不大于 n 的值

无须定义字符串数组也能实现同样的功能

输入长度为 10 的 10 个由小写字母组成的单词，则输出概率最大的值是 10

设只输入小写字母且 s[i].size() ≤ 10，如果 s[j] ≠ s[k]，则一定有 x[j] ≠ x[k] (1 ≤ j < k ≤ n)

正确答案D

解析详情

答案 D字符串哈希与去重

思路与推导

选项 A: ans 初始值是 n 并且只减不增，逻辑上去重以后数量只可能变小；选项 B: 可以每输入一个就现算哈希值，不需要存储所有输入；选项 C: 10 个长度为 10 的随机串，出现重复的概率很小；选项 D: 存在哈希冲突的理论可能性。

二、阅读程序（3）

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

int a[1010][12], n, m, pw[12] = {1};

int main() {
    cin >> n >> m; // 保证 0 < n, m <= 1000
    for (int h = 1, p = 2; p <= n; p *= 2, h++) pw[h] = 2 * pw[h - 1];
    for (int i = 1; i <= n; i++) cin >> a[i][0];
    for (int h = 1; pw[h] <= n; h++)
        for (int i = 1; i <= n - pw[h] + 1; i++)
            a[i][h] = max(a[i][h - 1], a[i + pw[h - 1]][h - 1]);
    for (int i = 1, x, y, h; i <= m; i++) {
        cin >> x >> y; // 保证 1 <= x <= y <= n
        for (h = 0; pw[h] * 2 <= y - x + 1;) h++;
        cout << max(a[x][h], a[y - pw[h] + 1][h]) << " "; // 利用幂等性
    }
    return 0;
}

第 28 题（判断题，2 分）

输入 n=100 时，数组 pw 中非零元素共有 7 个。（）

正确答案正确

解析详情

答案正确稀疏表区间最大值

思路与推导

pw 中的值保留不超过 n 的 2 的幂次，也就是 1,2,4,8,16,32,64。

第 29 题（判断题，2 分）

对一组 x=y 的输入，对应的输出就是 x。（）

正确答案错误

解析详情

答案错误稀疏表区间最大值

思路与推导

输出是 a[x][0] 的值。

第 30 题（判断题，2 分）

固定 i，则 a[i][h] 的值随 h 单调不降，不考虑没被赋值过的位置。（）

正确答案正确

解析详情

答案正确稀疏表区间最大值

思路与推导

h 越大，被求最大值的范围只增不减，所以最大值不会减小。从下面这句可直接看出： $a[i][h] = \max(a[i][h-1], a[i+pw[h-1]][h-1])$ ；。

第 31 题（判断题，2 分）

将倒数第 5 行中 for 循环的循环条件改为 $pw[h+1] \leq y-x+1$ ，结果不会有变化。（）

正确答案错误

解析详情

答案错误稀疏表区间最大值

思路与推导

循环要到左边的值严格超过 y-x+1 才会结束，但预计算的时候所有 pw 值都不会超过 n，即 pw[h+1] 可能引用到没有被预计算到的位置而其值为 0，则循环就不能正常结束了。为避免这个隐患，预计算的时候应多算一两项。

第 32 题（单选题，3 分）

此程序的时间复杂度为（）。

O(n(n+m))

O((n+m)\log n)

O(n^{2}+m)

O(n\log n+m)

正确答案B

解析详情

答案 B稀疏表区间最大值

思路与推导

h 的两个循环都是 log_n 级别的。

第 33 题（单选题，3 分）

输入如下，输出为（）。

555

543

552

542

正确答案C

解析详情

答案 C稀疏表区间最大值

思路与推导

根据输出区间 max 的逻辑即可得知。

三、完善程序（1）

二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值，小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。

输入格式：输入的第一行包含一个整数 n，表示这棵树有 n 个节点，编号分别为 1..n，其中编号为 1 的为根节点。之后的第 i 行有三个数 value，left_child，right_child，分别表示节点 i 关键字的值、左子节点的编号、右子节点的编号；若不存在左子节点或右子节点，则用 0 代替。

输出要求：输出1表示这棵树是二叉查找树，输出0则表示不是。

#include <iostream>
using namespace std;

const int INF = 1000000;
struct node { int l, r, v; } a[100];
int n;

int check(int x, int lower_bound, int upper_bound) {
    if (x == 0) return 1;
    return ① && ② && check(③) && check(④);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].v >> a[i].l >> a[i].r;
    cout << check(⑤, -INF, INF) << endl;
    return 0;
}

第 34 题（单选题，3 分）

①处应填（）。

x > lower_bound

x < lower_bound

a[x].v > lower_bound

a[x].v < lower_bound

正确答案C

解析详情

答案 C二叉查找树验证

思路与推导

这里是判断根节点 x 本身的取值是否在允许的范围之内，也就是大于下限小于上限，lower_bound 显然是下限，所以是大于。比较的是取值 v 而不是编号 x。

第 35 题（单选题，3 分）

②处应填（）。

x > upper_bound

x.v < upper_bound

a[x].v > upper_bound

a[x].v < upper_bound

正确答案D

解析详情

答案 D二叉查找树验证

思路与推导

与上题类似。

第 36 题（单选题，3 分）

③处应填（）。

a[x].r, a[x].v, lower_bound

a[x].r, lower_bound, a[x].v

a[x].l, a[x].v, lower_bound

a[x].l, lower_bound, a[x].v

正确答案D

解析详情

答案 D二叉查找树验证

思路与推导

这里是递归判断左子树（因为选项中是 lower_bound），所以是 a[x].1。对左子树，其取值范围在 x 本身的基础上，额外增加一个小于 x 本身的值，所以新的范围是 lower_bound，a[x].v。

第 37 题（单选题，3 分）

④处应填（）。

a[x].r, a[x].v, upper_bound

a[x].r, upper_bound, a[x].v

a[x].l, a[x].v, upper_bound

a[x].l, upper_bound, a[x].v

正确答案A

解析详情

答案 A二叉查找树验证

思路与推导

与上题类似。

第 38 题（单选题，3 分）

⑤处应填（）。

0

1

-1

INF

正确答案B

解析详情

答案 B二叉查找树验证

思路与推导

主函数调用判断整棵树，所以传入根节点编号 1。递归模拟，判定以 x 为根节点的子树的值域是否在 lower_bound 和 upper_bound 之间。

三、完善程序（2）

有一个 $n \times n$ ( $1 \leq n \leq 5000$ ) 的矩阵 a，对任意 $1 \leq i \leq n$ ， $1 \leq j \leq n$ ，输入数据满足 $a_{i,j} \leq a_{i+1,j}$ ， $a_{j,i} \leq a_{j,i+1}$ ，即矩阵中相邻的两个元素，右边的一定比左边的大，下面的一定比上面的大。给定一个数 k，找出 k 所在的行和列。输入保证矩阵中的数各不相同，且 k 这个值存在。

#include <iostream>
using namespace std;

int n, k, answerx, answery;
int a[5001][5001];

void FindKPosition() {
    int ①;
    while (j > 0) {
        if (a[n][j] < k) break;
        j--;
    }
    ②;
    while (a[i][j] != k) {
        while (③ && i > 1) i--;
        while (④ && j <= n) j++;
    }
    ⑤;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    cin >> k;
    FindKPosition();
    cout << answerx << " " << answery << endl;
    return 0;
}

第 39 题（单选题，3 分）

①处应填（）。

i = 1, j = 1

i = 1, j = n

i = n, j = 1

i = n, j = n

正确答案D

解析详情

答案 D单调矩阵查找

思路与推导

结合后面的那个 while（里面 j 在减小），所以这里 j 初始值为 n。下一题涉及的逻辑是找最后一行中，最后第一列不小于 k 的，作为起点。其实这整个逻辑大可省略，直接从 i=n，j=1 开始就行了。如前分析，输入保证在每个 L 型区域上，数值整体是单调的，所以初始位置在最大的那个 L 上就行了，没必要特判一次。但这里代码已经这么写了，只能照此选择。

第 40 题（单选题，3 分）

②处应填（）。

i++

i--

j++

j--

正确答案C

解析详情

答案 C单调矩阵查找

思路与推导

如上题所示，while 结束后 a[n,j] 是最后一行最后一个小于 k 的，下一个则是第一个大于等于 k 的。

第 41 题（单选题，3 分）

③处应填（）。

a[i - 1][j] > k

a[i][j] > k

a[i - 1][j] < k

a[i][j] < k

正确答案B

解析详情

答案 B单调矩阵查找

思路与推导

i 可以放心减小的条件是 j 的右侧肯定没有 k，根据题述单调性，只有 a[i][j] 已经大于 k 才能保证这一点。

第 42 题（单选题，3 分）

④处应填（）。

a[i][j + 1] > k

a[i][j] > k

a[i][j + 1] < k

a[i][j] < k

正确答案D

解析详情

答案 D单调矩阵查找

思路与推导

类似上题。

第 43 题（单选题，3 分）

⑤处应填（）。

answerx = i, answery = j

answerx = i, answery = j + 1

answerx = i - 1, answery = j

answerx = i - 1, answery = j + 1

正确答案A

解析详情

答案 A单调矩阵查找

思路与推导

while (a[i][j] != k) 循环结束的时候，就是 a[i][j] = k，于是 i 和 j 就是题目求的答案。