2025年_CSP-S1初赛试卷
__SECTIONS__:[{"name": "单选题", "count": 15}, {"name": "阅读程序", "count": 15}, {"name": "完善程序", "count": 10}] 从PDF导入：2025年_CSP-S _初赛试卷
试卷题目预览
有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这10个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？（ ）
在KMP算法中，对于模式串P="abacaba"，其next数组（next[i]定义为模式串P[0...i]最长公共前后缀的长度，且数组下标从0开始）的值是什么
对一个大小为16（下标0~15）的数组上构建满线段树。查询区间[3,11]时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？（
将字符串"cat","car","cart","case","dog","do"插入一个空的Trie树（前缀树）中。构建完成的Trie树（包括根结点）共有多少个
对于一个包含n个顶点和m条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？（ ）
在一个大小为13的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为H(key)=key mod 13。依次插入关键字18,26,35,9,68,74。插入
一个包含8个顶点的完全图（顶点的编号为1到8），任意两点之间的边权重等于两顶点编号的差的绝对值。该图的最小生成树的总权重是多少？（ ）
如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6，那么该树的前序遍历序列是什么？（ ）
一个0-1背包问题，背包容量为20。现有5个物品，其重量和价值分别为7,5,4,3,6和15,12,9,7,13。装入背包的物品能获得的最大总价值是多少？（
在一棵以结点1为根的树中，结点12和结点18的最近公共祖先(LCA)是结点4。那么下列哪个结点的LCA组合是不可能出现的？（ ）
递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？（ ）
在一个初始为空的最小堆（min-heap）中，依次插入元素20,12,15,8,10,5。然后连续执行两次"删除最小值"（delete-min）操作。请问此时堆
1到1000之间，不能被2、3、5中任意一个数整除的整数有多少个？（ ）
斐波那契数列的定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算F(n)的时间复杂度是指数级的。而使用动态规划（或迭代
有5个独立的、不可抢占的任务A1,A2,A3,A4,A5需要在一台机器上执行（从时间0开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为3,4,2,
当输入的n=3时，程序输出的答案为3。（ ）
在dfs函数运行过程中，k的取值会满足1≤k≤n+1。（ ）
删除第19行的flag[i]=false;，对答案不会产生影响。（ ）
单选题
当输入的n=4时，程序输出的答案为（ ）
如果因为某些问题，导致程序运行第25行的dfs函数之前，数组p的初值并不全为0，则对程序的影响是（ ）
假如删去第14行的if(flag[i]) continue;，输入3，得到的输出答案是（ ）
（2）有两个完全相同的鸡蛋，存在一个[1,n]范围内的最小高度k，使得这两个鸡蛋在从小于该高度k的位置放开后落到地面上不会破碎，但一旦高度大于等于h则鸡蛋会破碎。程序通过guess1和guess2两种方法找到最小高度k。
#include
#include
#include
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
++cnt_check;
if (cnt_broken == 2) return false;
if (h >= k) {
++cnt_broken;
return true;
} else {
return false;
}
}
inline void guess1(int n) {
for (int i = 1; i <= n; ++i) {
if (check(i)) return;
}
}
inline void guess2(int n) {
int w = 0;
for (w = 1; w * (w + 1) / 2 < n; ++w);
for (int ti = w, nh = w;; --ti, nh += ti) {
if (check(nh)) {
for (int j = nh - ti + 1; j < nh; ++j) {
if (check(j)) return;
}
return;
}
}
}
int main() {
scanf("%d%d", &n, &k);
int t;
scanf("%d", &t);
if (t == 1) guess1(n);
else guess2(n);
return 0;
}
判断题
当输入为6 5 1时，猜测次数为5；当输入为6 5 2时，猜测次数为3。（ ）
不管输入的n和k具体为多少，t=2时的猜测数总是小于等于t=1时的猜测数。（ ）
不管t=1或t=2，程序都一定会猜到正确结果。（ ）
单选题
函数guess2在运行过程中，最多使用的猜测次数的量级为（ ）
当输入的n=100时，代码中t=1和t=2分别需要的猜测次数最多分别为（ ）
（3）对于区间[l,r]内的每个位置i，求出kᵢ×xᵢ^pᵢ的总和，判断有多少种方案能使总和为0。
#include
#include
#include
#include
int n, m;
std::vector
inline int mpow(int x, int k) {
int ans = 1;
for (; k; k = k >> 1, x = x * x)
if (k & 1) ans = ans * x;
return ans;
}
std::vector
int cnt1, cnt2;
void dfs(std::vector
if (l > r) {
++cnt;
ans.push_back(v);
return;
}
for (int i = 1; i <= m; ++i)
dfs(ans, cnt, l+1, r, v + k[l] * mpow(i, p[l]));
}
int main() {
scanf("%d%d", &n, &m);
k.resize(n + 1); p.resize(n + 1);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &k[i], &p[i]);
dfs(ans1, cnt1, 1, n >> 1, 0);
dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
std::sort(ans1.begin(), ans1.end());
// 去重并统计
std::sort(ans2.begin(), ans2.end());
long long ans = 0;
// 双指针统计答案
printf("%lld\n", ans);
return 0;
}
判断题
删除ans2的排序后，代码输出的结果不会受到影响。（ ）
函数mpow(x,k)的功能是求出x^k。（ ）
单选题
当输入为"3 15 1 2 -1 2 1 2"时，输出结果为（ ）
记程序结束前p数组元素的最大值为P，则该代码的时间复杂度是（ ）
①处应填（ ）
②处应填（ ）
③处应填（ ）
④处应填（ ）
输出结果时，为什么需要取min(d[t][0], d[t][1])？（ ）
（2）（方程求解）给定参数k和p数组，求解方程Σkᵢ×xᵢ^pᵢ=0的解的数量，其中xᵢ∈[1,m]。使用折半搜索和双指针算法优化。
试补全程序。
#include
#include
#include
using namespace std;
int n, m;
vector
int mpow(int x, int k) {
int ans = 1;
for (; k; k >>= 1, x = x * x)
if (k & 1) ans = ans * x;
return ans;
}
vector
int cnt1, cnt2;
void dfs(vector
if (l > r) {
++cnt;
ans.push_back(v);
return;
}
for (int i = 1; i <= m; ++i) {
dfs(ans, cnt, l + 1, r, ⑤ );
}
}
int main() {
scanf("%d%d", &n, &m);
k.resize(n + 1);
p.resize(n + 1);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &k[i], &p[i]);
dfs(ans1, cnt1, 1, n >> 1, 0);
dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
sort(ans1.begin(), ans1.end());
// 去重统计
sort(ans2.begin(), ans2.end());
long long ans = 0;
int las = 0;
for (int i = cnt2 - 1; i >= 0; --i) {
for (; las < cnt1 && ⑥ ; ++las);
if (las < cnt1 && ans1[las] + ans2[i] == 0)
ans += cntans1[las];
}
printf("%lld\n", ans);
return 0;
}