2025 CCF 非专业级别软件能力认证第一轮 (CSP-S1) 提高组C++ 语言试题_c++

2025 CCF 非专业级别软件能力认证第一轮 (CSP-S1) 提高组C++ 语言试题 Puls

2025年9月20日CSP-S提高组第一轮真题试卷

练习模式考试模式

题目列表

选择题（每题2分，共30分）

1 . 有5 个红色球和 5 个蓝色球，它们除了颜色之外完全相同。将这 10个球拍成一排，要求任意两个蓝色球都不能相邻有多少种不同的排列方法? (2分)
2 . 在KMP 算法中，对于模式串P=“abacaba”，其next 数组(next[i]定义为模式串 P[0...i]最长公共前后缀的长度，且数组下标从 0开始)的值是什么? (2分)
3 . 对一个大小为 16(下标 0-15)的数组上构建满线段树。查询区间[3，11]时，最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)? (2分)
4 . 将字符串“cat”，“car”，“cart",“case”,“dog”,“do”插入一个空的 Trie 树(前缀树)中。构建完成 Trie 树(包括根节点)共有多少个结点? (2分)
5 . 对于一个包含 n个结点和 m条边的有向无环图(DAG)，其拓扑排序的结果有多少种可能? (2分)
6 . 在一个大小为 13 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 H(key)=key mod 13。依次插入关键字 18，26，35,9，68，74。插入 74 后，它最终被放置在哪个索引位置? (2分)
7 . 一个包含8个顶点的完全图(顶点的编号为1到 8)，任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点3和7之间的边权重为｜7-3｜= 4。该图的最小生成树的总权重是多少? (2分)
8 . 如果一棵二叉搜索树的后序遍历序列是2，5，4，8，12，10，6，那么该树的前序遍历序列是什么? (2分)
9 . 一个0-1背包问题，背包容量为20。现有5个物品，其重量和价值分别为7，5，4，3，6和 15，12，9，7，13。装入背包的物品能获得的最大总价值是多少? (2分)
10 . 在一棵以结点1为根的树中，结点 12 和结点 18 的最近公共祖先(LCA)是结点 4。那么下列哪个结点的 LCA 组合是不可能出现的？ (2分)
11 . 递归关系式$T(n)= 2T(n/2)+ O(n^2)$描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少? (2分)
12 . 在一个初始为空的最小堆(min-heap)中，依次插入元素 20，12，15，8，10，5。然后连续执行两次“除最小值” (delete-min)操作。请问此时堆顶元素是什么? (2分)
13 . 1 到 1000 之间，不能被 2、3、5 中任意一个数整除的整数有多少个? (2分)
14 . 斐波那契数列的定义为 F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算 F(n) 的时间复杂度是指数级的。而使用动态规划(或选代)方法的时间复杂度是线性的。造成这种巨大差异的根本原因是? (2分)
15 . 有5个独立的、不可抢占的任务 A1，A2，A3，A4，A5 需要在一台机器上执行(从时间0开始执行)，每个任务都有对应的处理时长和截止时刻，按顺序分别为 3,4,2,5,1和5,10,3,15,11。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务? (2分)

阅读程序

16 . 阅读程序1 (13分)
17 . 阅读程序2 (13.5分)
18 . 阅读程序3 (13.5分)

完善程序

19 . 完善程序(1)特殊最短路 (15分)
20 . 完善程序（2） (15分)

关于我们

关于我们联系方式免责声明侵权投诉服务协议

题库分类

scratch python c++ icode 科技素养

题单分类

scratch python c++ 科技素养

常见问题

如何开通会员问题反馈题单如何下载能否上传题单催更正确方式

提供少儿编程阶段，多个类型的题库学习，不限于等级考试，各项赛事

手机：13006071015