2025CSP-S解析

根据民间数据进行解析，如有更改请联系我进行更改。

选择

T1

题面

有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球拍成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

A. 25
B. 30
C. 6
D. 120

解析

可以将 $4$ 个红球插入到每个蓝球之间，将最后一个红球随意加，有 $9+1=10$ 种，再去掉放在红球之后的情况，得 $10-4=6$，故选 C。

T2

题面

在KMP算法中，对于模式串 $P=``abacaba"$，其 $next$ 数组（$next_i$ 定义为模式串 $P_{0\cdots i}$ 最长公共前后缀的长度，且数组下标从 $0$ 开始）的值是什么？

A. {0,0,1,0,1,2,3}
B. {0,1,2,3,4,5,6}
C. {0,0,1,1,2,2,3}
D. {0,0,0,0,1,2,3}

解析

肉眼观察即可，故选 A。

T3

题面

对一个大小为 $16$ （下标 $0\sim15$）的数组上构建满线段树。查询区间 $[3,11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）

A. $7$
B. $8$
C. $9$
D. $10$

解析

如图：

涂色的为访问的节点，故选 B。

T4

题面

将字符串 "cat","car",cart","case","dog","do" 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

A. $8$
B. $9$
C. $10$
D. $11$

解析

如图：

故选 D。

T5

题面

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

A. 只有 $1$ 种
B. 最多 $n$ 种
C. 等于 $n-m$ 种
D. 以上都不对

解析

考虑 $m=0$ 时有 $n!$ 种可能，故选 D。

T6

题面

在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(key)= key \mod 13$。依次插入关键字 $18,26,35,9,68,74$。插入 $74$ 后，它最终被放置在哪个素引位置？

A. $5$
B. $7$
C. $9$
D. $11$

解析

模拟，如下表：

加入的数字\表	0	1	2	3	4	5	6	7	8	9	10	11	12
18						18
26	26					18
35	26					18				35
9	26					18				35	9
68	26			68		18				35	9
74	26			68		18				35	9	74

故选 D。

T7

题面

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为$|7-3|=4$。该图的最小生成树总权重是多少？

A. $7$
B. $8$
C. $9$
D. $10$

解析

显然 $i$ 号节点连接 $i+1$ 号节点能取到最小值 $n-1$，故选 A。

咕咕咕中……

阅读

完形