CSP-S 2023 第一轮试卷

在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？

$0,1,2,3,4$ 中选取 $4$ 个数字，能组成（）个不同四位数（注：最小的四位数是 $1000$ 最大的四位数是 $9999$）。

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

假设有 $n$ 根柱子，需要按照以下规则依次放置编号为 $1,2,3,\cdots$ 的圆环：每根柱子的底 部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 $4$ 根柱子时，最多可以放置（）个圆环

以下对数据结构的表述不恰当的一项是：

以下连通无向图中，（）一定可以用不超过两种颜色进行染色

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $X={x_1,x_2,x_3,\cdots,x_m}$ 和 $Y={y_1,y_2,y_3,\cdots,y_n}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z={z_1,z_2,z_3,\cdots,z_k}$, 使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件…

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 $x$ 点，得到 $2x$ 元；第二次掷出 $y$ 点，当 $y=x$ 时玩家会失去之前得到的 $2x$ 元而当 $y \neq x$ 时玩家能保住第一次获得的 $2x$ 元。上述 $x,y\in{1,2,3,4,5,6}$。 例如：玩家第 一次掷出 $3$ 点得到 $6$ 元后，但第二次再次掷出 $3$ 点，会失去之前得到的 $6$ 元，玩家最终收益为…

假设我们有以下的 C++ 代码：

假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？（）

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

如图是一张包含 $6$ 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 $6$ 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

若 $n=\sum_{i=0}^k {16^i\cdot x_i}$，定义 $f(n)=\sum_{i=0}^k {x_i}$，其中 $x_i\in\{0,1,\cdots,15\}$。对于给定自然数 $n_0$，存在序列 $n_0,n_1,n_2,\cdots,n_m$，其中对于 $1 \le i \le m$ 都有 $n_i=f(n_{i-1})$，且 $n_m=n_{m-1}$，称 $n_m$ 为 $n_0$ 关于 $f$ 的不动点。…

现在用如下代码来计算 $x^n$，其时间复杂度为（）。