CSP-S 初赛赛前模拟题-打印版｜结合近七年真题考点（附答案详解）

提高组（S 组）比入门级更进阶：Linux 命令、图论算法、数论进阶、字符串匹配、状态压缩 DP 都是 J 组没有的考点。这份模拟卷严格按照近七年（2019—2025）CSP-S 初赛真题的题型与难度编写——15 道单选、3 段阅读程序、2 段完善程序，满分 100 分。建议先卡 120 分钟做完，再翻到文末对答案。

获取 CSP-S 初赛赛前模拟题.pdf

请关注状元编程公众号，回复  2026091801

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

1. 在 Linux 系统中，用于显示当前工作目录绝对路径的命令是（ ）。

A. ls　　B. pwd　　C. cd　　D. mkdir

2. 二进制数 1101₂ 与 1010₂ 按位异或的结果是（ ）。

A. 0111₂　　B. 1111₂　　C. 0011₂　　D. 1000₂

3. 一棵完全二叉树共有 999 个结点，则它的叶子结点数为（ ）。

A. 499　　B. 500　　C. 501　　D. 512

4. 关于哈夫曼编码，下列说法正确的是（ ）。

A. 出现频率越高的字符，编码越长 B. 哈夫曼编码是一种前缀编码，任一字符的编码都不是另一字符编码的前缀 C. 哈夫曼编码是唯一的 D. 哈夫曼编码只能用于等长编码

5. 一个有 n 个顶点的强连通图，至少含有（ ）条边。

A. n-1　　B. n　　C. n+1　　D. 2n

6. 后缀表达式 3 4 + 5 * 的值是（ ）。

A. 23　　B. 35　　C. 17　　D. 27

7. 哈希表长度为 10，哈希函数 H(k)=k%10，用线性探测法解决冲突。依次插入关键字 12、22、32 后，关键字 32 存放在下标（ ）处。

A. 2　　B. 3　　C. 4　　D. 5

8. 6 个不同的元素排成一排，其中某两个特定元素不能相邻，共有（ ）种排列方式。

A. 720　　B. 480　　C. 240　　D. 120

9. 快速排序在最好情况下的时间复杂度是（ ）。

A. O(n)　　B. O(n log n)　　C. O(n²)　　D. O(log n)

10. 在含 1024 个元素的有序表中进行二分查找，最多需要比较（ ）次。

A. 9　　B. 10　　C. 11　　D. 1024

11. 在模素数 p 意义下，整数 a（a 与 p 互质）的乘法逆元是（ ）。

A. a^(p-1) mod p　　B. a^(p-2) mod p　　C. a^p mod p　　D. 1/a

12. 设递归式 f(n) = 2·f(n/2) + n，且 f(1) = 1，则 f(8) 的值是（ ）。

A. 24　　B. 32　　C. 40　　D. 48

13. KMP 字符串匹配算法通过（ ）避免重复比较。

A. 前缀函数（next 数组）　　B. 哈希函数　　C. 字典树　　D. 后缀数组

14. 递归式 T(n) = 2T(n/2) + O(n) 的时间复杂度是（ ）。

A. O(n)　　B. O(n log n)　　C. O(n²)　　D. O(log n)

15. 关于大小端（字节序），下列说法正确的是（ ）。

A. 大端模式下，低位字节存放在低地址 B. 小端模式下，低位字节存放在低地址 C. 大小端只影响浮点数的存储 D. 大小端由编译器决定，与硬件无关

二、阅读程序题（3 段程序，共约 40 分）

阅读程序（一）：筛法求素数

#include<iostream>usingnamespace std;constint N = 100;bool isPrime[N + 1];intmain(){for (int i = 2; i <= N; i++) isPrime[i] = true;for (int i = 2; i * i <= N; i++) {if (isPrime[i]) {for (int j = i * i; j <= N; j += i)                isPrime[j] = false;        }    }int cnt = 0;for (int i = 2; i <= N; i++)if (isPrime[i]) cnt++;    cout << cnt << endl;return0;}

判断题（正确写 √，错误写 ×）

1. 该程序的功能是统计 2~100 之间质数的个数。（　）
2. 程序最终的输出结果是 25。（　）
3. 若把 N 改为 10，输出结果为 4。（　）

选择题

1. 内层循环 j 从 i * i 开始，这样做（　）。 A. 会漏掉合数　　B. 是错误的　　C. 可以避免重复标记　　D. 会多统计质数

2. 该算法的时间复杂度约为（　）。 A. O(n)　　B. O(n log n)　　C. O(n log log n)　　D. O(n²)

阅读程序（二）：0-1 背包

#include<iostream>#include<vector>usingnamespace std;intmain(){int n = 4, W = 10;int w[5] = {0, 2, 3, 4, 5};int v[5] = {0, 3, 4, 5, 6};vector<int> dp(W + 1, 0);for (int i = 1; i <= n; i++)for (int j = W; j >= w[i]; j--)            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);    cout << dp[W] << endl;return0;}

判断题（正确写 √，错误写 ×）

1. 该程序解决的是 0-1 背包问题。（　）
2. 程序最终的输出结果是 13。（　）
3. 内层循环 j 从 W 递减到 w[i]，是为了保证每个物品最多只选一次。（　）

选择题

1. 若把内层循环改为 for (int j = w[i]; j <= W; j++)，则问题会变成（　）。 A. 0-1 背包　　B. 完全背包　　C. 多重背包　　D. 分组背包

2. 该程序的时间复杂度是（　）。 A. O(nW)　　B. O(n²)　　C. O(W²)　　D. O(nW²)

阅读程序（三）：快速幂

#include<iostream>usingnamespace std;intmain(){int a = 2, b = 10, mod = 1000;longlong ans = 1;while (b > 0) {if (b & 1) ans = ans * a % mod;        a = a * a % mod;        b >>= 1;    }    cout << ans << endl;return0;}

判断题（正确写 √，错误写 ×）

1. 该程序的功能是计算 a^b mod mod（模幂运算）。（　）
2. 程序最终的输出结果是 24。（　）
3. 该算法的时间复杂度是 O(log b)。（　）

选择题

1. 若把 b 改为 0，程序输出（　）。 A. 0　　B. 1　　C. a　　D. 运行错误

2. 该算法利用了（ ）的思想。 A. 二分/二进制拆分　　B. 贪心　　C. 回溯　　D. 分块

三、完善程序题（2 段程序，共 30 分）

完善程序（一）：二分答案

有 n 根木棍，第 i 根长度为 a[i]。现要把木棍切成 k 段等长的小木棍，求能切出的最大长度（不足一段的丢弃）。

#include<iostream>usingnamespace std;constint N = 100005;int n, k;int a[N];boolcheck(int len){int cnt = 0;for (int i = 1; i <= n; i++)        cnt += a[i] / len;return cnt >= k;}intmain(){    cin >> n >> k;int maxLen = 0;for (int i = 1; i <= n; i++) {        cin >> a[i];if (a[i] > maxLen) maxLen = a[i];    }int l = 0, r = maxLen, ans = 0;while (____①____) {int mid = (l + r + 1) / 2;if (check(mid)) { ____②____; }else            { ____③____; }    }    cout << ans << endl;return0;}

① ② ③ 处应填写的代码分别是（3 空，每空 4 分）。

完善程序（二）：并查集

维护 n 个元素的集合，支持"合并两个元素所在集合"和"查询两个元素是否在同一集合"两种操作。

#include<iostream>usingnamespace std;constint N = 100005;int fa[N];intfind(int x){if (fa[x] == x) return x;return ____①____;}voidmerge(int x, int y){int fx = find(x), fy = find(y);if (fx != fy) ____②____;}intmain(){int n, m;    cin >> n >> m;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {int op, x, y;        cin >> op >> x >> y;if (op == 1) merge(x, y);else cout << (find(x) == find(y) ? "YES" : "NO") << endl;    }return0;}

① ② 处应填写的代码分别是（2 空，每空 5 分）。

四、参考答案与详解

单项选择题答案

逐题解析

• 1. B：pwd = print working directory，显示当前目录绝对路径；ls 列目录、cd 切换目录、mkdir 建目录。
• 2. A：1101₂ ^ 1010₂ = 0111₂（逐位异或，相同为 0 不同为 1）。
• 3. B：完全二叉树叶子数 = n - ⌊n/2⌋ = 999 - 499 = 500。
• 4. B：哈夫曼编码是前缀编码（任一编码不是另一编码的前缀），频率越高编码越短，且编码不唯一。
• 5. B：强连通图任意两点可达，至少需要 n 条边（构成一个环）。
• 6. B：后缀表达式求值：(3+4)×5 = 35。
• 7. C：12%10=2 放 2；22%10=2 冲突→探测 3 放 3；32%10=2 冲突→3 冲突→4 放 4。
• 8. B：总数 6! 减去两元素相邻（捆成一个整体 5!×2!），即 720 - 240 = 480。
• 9. B：快排最好（每次均匀划分）O(n log n)，最坏（已有序）O(n²)。
• 10. B：二分查找最多比较 ⌈log₂1024⌉ = 10 次。
• 11. B：费马小定理 a^(p-1) ≡ 1 (mod p)，故逆元为 a^(p-2) mod p。
• 12. B：f(2)=4，f(4)=2×4+4=12，f(8)=2×12+8=32。
• 13. A：KMP 通过前缀函数（next 数组）记录已匹配信息，避免主串指针回溯。
• 14. B：主定理 a=2, b=2, f(n)=O(n)，n^(log_b a)=n，故 T(n)=O(n log n)。
• 15. B：小端（little-endian）模式下，低位字节存放在低地址。

阅读程序答案

阅读程序（一）：1.√　2.√　3.√　4.C　5.C

• 埃氏筛法，统计 2~100 质数共 25 个；N=10 时质数 {2,3,5,7} 共 4 个。
• 内层 j 从 i*i 开始，因为小于 i*i 的合数已被更小的质数筛过，避免重复标记（第 4 题 C）。
• 时间复杂度 O(n log log n)。

阅读程序（二）：1.√　2.√　3.√　4.B　5.A

• 0-1 背包，滚动数组优化。物品 (2,3)(3,4)(4,5)(5,6)，容量 10，最优组合 {1,2,4}：重量 2+3+5=10，价值 3+4+6=13，故 dp[10]=13。
• 内层逆序遍历保证每件物品只选一次；若改成正序，则变成完全背包（可重复选）。
• 时间复杂度 O(nW)。

阅读程序（三）：1.√　2.√　3.√　4.B　5.A

• 快速幂（二进制拆分）：2^10 mod 1000 = 1024 mod 1000 = 24。
• b=0 时循环不执行，ans 初值 1，输出 1。
• 时间复杂度 O(log b)。

完善程序答案

完善程序（一）：

• ① l < r
• ② ans = mid; l = mid;
• ③ r = mid - 1;

二分答案求最大值：mid = (l+r+1)/2 向上取整，可行时 l=mid（保留 mid），不可行时 r=mid-1。注意 +1 防止 l、r 相邻时死循环。

完善程序（二）：

• ① fa[x] = find(fa[x])
• ② fa[fx] = fy;

①是并查集核心的路径压缩；②把 fy 设为 fx 的父亲（合并两个集合）。

五、考点对照（这张卷覆盖的七年高频点）

💡 全卷覆盖了七年真题里的 14 大高频考点，其中 Linux、图论、数论进阶（逆元/快速幂/筛法）、KMP、0-1 背包、二分答案、并查集等 S 组进阶考点全部命中。做完对照这张表，能快速定位自己哪块薄弱。

本模拟卷基于 2019—2025 七年 CSP-S 初赛真题的题型与考点规律原创编写，仅供赛前自测，最终以 CCF 官方真题为准。祝各位同学提高组初赛旗开得胜！