粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com
真题解析 · 免费诊断 · 知识点精讲 · GESP 刷题 · CSP-J 刷题 · CSP-S 刷题 · NOIP 刷题 · AI 伴学 · 帮助中心
真题来源：中国计算机学会（CCF）CCF-GESP / CSP / NOIP 认证试题；本页解析由 OI伴学提供。
| 题号 | 题型 | 答案 | 考点 | 解题思路 |
|---|---|---|---|---|
| 第 1 题 | 选择题 | B | 输入输出 | 这题考对数运算与浮点精度。拿到log10(100)直接想10的幂次，log2(100)用换底或估算，相减后看最接近哪个选项，别被'最接近'三个字绕进去。 |
| 第 2 题 | 选择题 | D | 动态规划、前缀和与差分 | 这题是经典的区间 DP 模型，核心在于识别出合并代价与区间和的关系，以及分裂点 k 的正确范围。拿到题先别急着套公式，盯着代码里 f[i][j] 的更新过程，你会发现那个 s[j]… |
| 第 3 题 | 选择题 | B | 动态规划 | 这题考的是动态规划里最长上升子序列（LIS）的经典写法，命题人把输出拆成了两行：先一行把每个 f[i] 都打出来，再单独一行输出最终答案 ans。拿到题先别急着算 LIS 长度，要… |
| 第 4 题 | 选择题 | C | 函数 | C++类：构造函数（对象创建时调用）、析构函数（对象销毁时调用）、虚函数（实现多态）。构造函数不能为虚。 |
| 第 5 题 | 选择题 | D | IDE与开发环境 | 这题核心就一个词：非连通。想顶点最少，就得让一个连通块拼命吃边（完全图最省顶点），另一个连通块只剩1个孤立点。先算完全图能吃多少边，再加1。 |
| 第 6 题 | 选择题 | D | 哈希表 | 别被表长31带偏，这道题核心就盯住哈希函数里的模13和线性探测。拿到输入序列，按代码逻辑一步步模拟：算出初始下标k，若flag[k]已置1就k=(k+1)%13循环探测，直到找到空… |
| 第 7 题 | 选择题 | B | — | 这题核心就是还原二叉树。先序首字母定根，中序左右分界，递归画出来，再数高度、度、叶节点，最后对选项逐个验证。 |
| 第 8 题 | 选择题 | C | 动态规划、复杂度分析、状态压缩DP | 这题考动态规划的空间复杂度分析。拿到代码先看状态转移方程，判断当前状态依赖哪些上一轮的数据，就能直接看出能不能压缩维度，别被二维数组的表象迷惑了。 |
| 第 9 题 | 选择题 | B | 搜索、队列(queue) | 这题考的是图遍历的核心数据结构。拿到题先别想代码，直接回扣定义：广度优先（BFS）是按层、由近及远访问的，这就要求待访问节点必须保持“先进先出”的顺序，否则层次就乱了。 |
| 第 10 题 | 选择题 | C | 哈希表、函数 | 这道题考哈希表链地址法的平均查找长度。拿到题先算每个关键字的哈希地址，还原出各槽位链表长度，再按头插顺序累加比较次数，最后除以总数。 |
| 第 11 题 | 选择题 | D | 动态规划 | 这题本质是图遍历，拿到题先别想DP，直接建反向图（或正向图找能到的点），从目标课程出发跑BFS或DFS就能把全部先修课搜出来，动态规划在这里纯属画蛇添足。 |
| 第 12 题 | 选择题 | C | — | 看到完全二叉树和节点总数，别想复杂遍历，直接抓住核心性质：最后一层节点数与倒数第二层的关系，用⌈n/2⌉公式秒杀。 |
| 第 13 题 | 选择题 | B | 复杂度分析 | 拿到题先盯住‘有向图’和‘邻接表’两个关键词。邻接表里每个顶点的链表只存从它出发的弧，求某个顶点的度（出度）就是顺着这个链表走一遍数节点数，时间复杂度只跟链表里弧的总数有关。 |
| 第 14 题 | 选择题 | D | 拓扑排序 | 别急着套公式，先想：有向图判环到底在干什么？是找‘访问中’的节点还是看能不能排拓扑序？两者本质都是遍历全图，复杂度同阶，谁快纯属玄学。 |
| 第 15 题 | 选择题 | B | 搜索、队列(queue)、图的遍历 | 这题考的是 BFS 的核心机制：队列出队顺序决定访问顺序。拿到题别急着背层序，先画出 v1 的邻居按什么顺序入队，再顺着队列推一遍。同层节点顺序必须跟邻接表一致，这是判断合法性的唯… |
| 第 16 题 | 判断题 | A | — | 图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。 |
| 第 17 题 | 判断题 | A | 算法 | 图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。 |
| 第 18 题 | 判断题 | B | — | 这题考完全二叉树深度公式的精确表达。拿到题先想：深度必须是整数，而log2(N)在N不是2的幂时是分数，所以公式里缺了个向下取整符号，这就是坑。 |
| 第 19 题 | 判断题 | A | 动态规划 | 这题考动态规划适用范围。拿到题先别急着写代码，想清楚：最大子段和能用贪心吗？能分治吗？能不能用动态规划？DP的核心是‘最优子结构’——当前最优解包含子问题的最优解，最大子段和显然满… |
| 第 20 题 | 判断题 | A | 对数函数、幂函数与指数函数 | 这题别急着套公式，先看清符号：题干里的log默认指自然对数ln，而右边是常用对数lg。抓住这一点，两边一化简，大小关系就呼之欲出了。 |
| 第 21 题 | 判断题 | B | 复杂度分析 | 这道题考的是图论基础里邻接矩阵和邻接表两种存储方式在求节点度时的时间复杂度对比。拿到题先明确有向图中‘度’的定义，再看两种结构怎么存边，最后对比遍历代价。 |
| 第 22 题 | 判断题 | B | 字符串哈希 | 别被‘素数’两个字骗了，冲突的本质是不同键值对模p同余，与p是否素数无关，直接举反例即可。 |
| 第 23 题 | 判断题 | B | 动态规划 | 这题考动态规划的本质理解，核心是：状态转移方程只是定义了‘怎么算’，但没解决‘算多少次’的问题。拿到题先想：递归不加记忆化会怎样？指数级爆炸就是答案。 |
| 第 24 题 | 判断题 | A | — | 这道题考的是BFS遍历的本质。拿到题先想：连通图定义是任意两点可达，BFS从一点出发能访问所有点吗？能，且BFS天然能处理无权图的全量可达性，所以用BFS遍历若访问节点数等于总节点… |
| 第 25 题 | 判断题 | B | 函数 | 这题考构造函数生成规则。拿到题先想：用户定义构造函数后，编译器还不会自动生成缺省构造函数吗？不会。所以'先执行缺省构造函数'这半句直接从根上错了。 |
建议按「限时做 → 对答案 → 读常见错误」三步走。先按考试的真实节奏做完，再回来看每一题的解析；尤其是"常见错误"那一段——它对应的是命题人反复设置的陷阱，读完能直接迁移到同类题上。
想做限时模考，可在 OI伴学 平台切换考试模式；错题会自动归集，并按考点推荐同类练习。
粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com