粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com
真题解析 · 免费诊断 · 知识点精讲 · GESP 刷题 · CSP-J 刷题 · CSP-S 刷题 · NOIP 刷题 · AI 伴学 · 帮助中心
真题来源：中国计算机学会（CCF）CCF-GESP / CSP / NOIP 认证试题；本页解析由 OI伴学提供。
| 题号 | 题型 | 答案 | 考点 | 解题思路 |
|---|---|---|---|---|
| 第 1 题 | 选择题 | D | 位运算、原码、反码与补码、基础语法 | 看到 x &= x 1 → 先想消去最低位 1 |
| 第 2 题 | 选择题 | D | 哈夫曼树、贪心算法、堆(Heap) | 哈夫曼树用"每次取最小的两个权值合并"的贪心过程构造，带权路径长度 WPL 恰好等于"所有合并代价之和"。把 1…8 依次按规则合并，把每次合并得到的数加起来即可。 |
| 第 3 题 | 选择题 | C | 整数与整除、计数原理、数学 | 把 1～999 写成三位数（001, 002, …, 999），每一位上"1"都恰好出现 100 次，三位合计 300 次；再加上 1000 里的那一个"1"，共 301。 |
| 第 4 题 | 选择题 | D | 计数原理、排列组合基础、组合数学 | "恰好 2 封装对"= 先从 5 封里选出对的 2 封（C(5,2) = 10 种），剩下 3 封必须"全部装错"（错排数 D₃ = 3!·(1−1/1!+1/2!−1/3!) =… |
| 第 5 题 | 选择题 | A | 同余与模运算、快速幂、数论算法 | 3 与 100 互质，幂次模 100 一定循环。先找循环节：3²⁰ ≡ 1 (mod 100)，所以只看指数对 20 取模。2026 mod 20 = 6，算 3⁶ = 729，取… |
| 第 6 题 | 选择题 | C | 区间DP、动态规划、简单动态规划 | 相邻两堆合并是区间 DP 的经典模型：dp[i][j] = 把 a[i..j] 合并成一堆的最小代价，转移为 dp[i][j] = min(dp[i][k] + dp[k+1][j… |
| 第 7 题 | 选择题 | A | 树状数组(BIT)、复杂度分析、线性结构 | 树状数组的两次操作都是"沿 lowbit 跳"：查询前缀和 sum(i) 是不断 i = lowbit(i)，修改 add(i) 是不断 i += lowbit(i)。把 11 和… |
| 第 8 题 | 选择题 | B | 拓扑排序、图的基本概念、计数原理 | 顶点 4 与谁都不相邻，位置完全自由；剩下 3 个顶点只需满足"1 在 2、3 之前"。用排列计数：总排列 4! = 24，而 {1,2,3} 中 1 排最前的概率是 1/3，故为… |
| 第 9 题 | 选择题 | A | 分治算法、复杂度分析、时间复杂度分析 | 这是主定理的"非整数分割"情形：T(n) = T(n/3) + T(2n/3) + Θ(n)，两棵子树规模之和恰为 n，属于平衡划分，结果与归并排序同阶——Θ(n log n)。 |
| 第 10 题 | 选择题 | D | 树的直径、树的重心、树形结构 | 直径 = 树上最远两点间的边数，Dijkstra 式"两遍搜索"或手数最长路径即可；重心 = 删掉它之后最大连通块最小的那个点。先画出这棵树，再找最长链和平衡点。 |
| 第 11 题 | 选择题 | C | 强连通分量(SCC)、图论算法、图的基本概念 | 缩点后是 DAG，要把整张图变成强连通，最少添加的边数 = max(入度为 0 的数目, 出度为 0 的数目)，本题即 max(3, 4) = 4（前提是 SCC 个数 ≥ 2）。 |
| 第 12 题 | 选择题 | C | 卡特兰数、排列组合基础、二叉树基础 | "不带标号、区分左右子树"的二叉树就是卡特兰数：n 个结点的形态数为 Cₙ = 1/(n+1)·C(2n, n)。n = 6 时 C₆ = 132。 |
| 第 13 题 | 选择题 | B | KMP算法、字符串算法、二分答案 | 逐一比较 S 的前缀与后缀，找出所有既是真前缀又是真后缀（且非空）的子串：长度 2 的 "ab" 与长度 4 的 "abab"，长度和为 6。也可以用 KMP 的 next 数组沿… |
| 第 14 题 | 选择题 | C | 归并排序、排序基础、复杂度分析 | 归并统计逆序对时， a[i] <= a[j] 表示"左边元素不大于右边，不算逆序"；改成严格小于后， 相等的元素对也被计入 ，于是答案变成满足 i < j 且 a[i] ≥ a[j… |
| 第 15 题 | 选择题 | B | 快速幂、同余与模运算、数论算法 | 这是快速幂（模幂）的模板：求 2^100 mod 1000。要么按二进制逐位平方 乘手算，要么直接注意到 2^100 的末三位是 376。 |
| 第 16 题 | 阅读程序 | ABC | 位运算、一维数组、进制与编码 | 看到 CRC 模 2 除法 → 先想：除数多项式、补零移位、高位消去。 |
| 第 17 题 | 阅读程序 | ABD | ST表(Sparse Table)、最大公约数与最小公倍数、离散化 | 这是"ST 表（稀疏表）+ gcd"：dp[i][j] 保存从 a[i] 开始连续 2^j 个数的最大公约数，预处理用倍增合并两半（第二半从 i + 2^(j−1) 起），查询时把… |
| 第 18 题 | 阅读程序 | ABC | 树形DP、树的直径、树形结构 | 这是"树形 DP 求直径"：f[i] 表示以 i 为根往下走的最长路（边数），因为 fa[i] < i，逆序处理就能保证先算完所有孩子。第一句 if 用"父结点已有的最长路 + 本… |
| 第 19 题 | 完善程序 | CDBA | BFS(广度优先搜索)、二分图、图的基本概念 | BFS 求无权图最短路，同时用 c[] 做二分图染色。① 把 '+'/' ' 变成权值 ±1；② 队列用 hh/tt 双指针，循环条件是 hh < tt；③ 距离由父结点加一；④ … |
| 第 20 题 | 完善程序 | CBDA | 状态压缩DP、枚举法、位运算 | 看到绝对值最大化 → 先想符号枚举 + 格雷码增量 |
建议按「限时做 → 对答案 → 读常见错误」三步走。先按考试的真实节奏做完，再回来看每一题的解析；尤其是"常见错误"那一段——它对应的是命题人反复设置的陷阱，读完能直接迁移到同类题上。
想做限时模考，可在 OI伴学 平台切换考试模式；错题会自动归集，并按考点推荐同类练习。
粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com