CSP-S 2023 提高级 第一轮试题（初赛）答案及解析

CSP-S 2023 提高级 第一轮试题（初赛）答案及解析

一、单项选择题

1. 在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？
   A. newdir
   B. mkdir
   C. create
   D. mkfold

答：B
mkdir是Linux中新建目录文件的指令，其它选项都不是Linux指令

2. 0,1,2,3,4 中选取 4 个数字，能组成（）个不同四位数（注：最小的四位数是 1000 最大的四位数是 9999）。
   A. 96
   B. 18
   C. 120
   D. 84

答：A
最高位数只能从1,2,3,4中四个数中选，有$C(4,1)$种情况，而后3位数可以从剩下的4个数字中选择，选出来后再排列到3个位置上，是从4个数中选出3个数的排列，有$P(4,3)$种情况，共有$C(4,1)\ast P(4,3)=4\ast 4\ast 3\ast 2=96$种情况，选A。

3. 假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta (n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。
   A. $O(m\sqrt{\log n}\cdot \log \log n)$
   B. $O(n^2+m)$
   C. $O(\frac{n^2}{\log m}+m\log n)$
   D. $O(m+n\log n)$

答： A
由于$m=\Theta (n)$，因此可以将各项的大O表示法中的m替换为n来看待。
A：$O(n\sqrt{\log n}\cdot \log \log n)<O(n\sqrt{\log n}\cdot \sqrt{\log n})=O(nlogn)$，
B：$O(n^2+n)=O(n^2)$
C：$O(\frac{n^2}{\log n}+n\log n)>O(\frac{n^2}{n}+n\log n)=O(n\log n)$
D：$O(n+n\log n)=O(n\log n)$
可见A选项的时间复杂度最小

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

答： C
由于选项中最大为11，假设最多有编号为11的圆环。考虑可以作为加和的完全平方数可能有4， 9， 16。考虑其可能是哪两个不同的正整数的加和：
$4=1+3$
$9=1+8=2+7+3+6=4+5$
$16=5+11=6+10=7+9$
看到这些等式，应该容易想到，每根柱子第1层分别放1，2，3，4。根据加和为9的等式可知，若想继续放圆环，需要在4上面放5，3上面放6，2上面放7，1上面放8。接下来7上面放9， 6上面放10， 5上面放11。
摆放后其形式为：

	9	10	11
8	7	6	5
1	2	3	4

如果一开始将3放在1上面，4，5，6，7都有位置可以放，当想放8时，由于8只能放在1上面，而1上面已经有数字了，因此无法再放了。该方法只能放到7，不如上面的方法放的圆环多。

5. 以下对数据结构的表述不恰当的一项是：
   A. 队列是一种先进先出（FIFO）的线性结构
   B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
   C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
   D. 二叉树是一种每个结点最多有两个子结点的树结构

答： B
A、C、D的描述都是正确的。
B选项：构造哈夫曼树主要是为了实现哈夫曼编码，而不是图的深度优先搜索。

6. 以下连通无向图中，（）一定可以用不超过两种颜色进行染色。
   A. 完全三叉树
   B. 平面图
   C. 边双连通图
   D. 欧拉图

答： A
“染色”，在本题中指的是将图中所有顶点进行染色，保证每条边连接的两个顶点的颜色不同。
如果一个图只有1个顶点，那么可以使用1种颜色进行染色。
该题的要求是，最多使用2种颜色对图染色，就可以使得图中任意一条边连接的两个顶点颜色不同。
如果学过二分图，应该了解：二分图可以使用不超过两种颜色进行染色，而树一定是二分图，完全三叉树是一种树，因此A选项是对的。
（从树的某顶点出发进行广搜，广搜到的奇数层顶点染一种颜色，偶数层顶点染上另一种颜色，即可完成满足条件的染色）。
如果一个图除顶点处外无边相交，那么该图是平面图。
无向连通图如果删掉某条边后，该图就不是连通图，那么被删掉的边叫做原图的“桥”。
没有桥的无向连通图叫“边双连通图”
无向图中，经过所有边且每条边只经过一次的回路叫欧拉回路。有欧拉回路的图是欧拉图。
反例：三个顶点构成的完全图是平面图，是边双连通图，也是欧拉图，但该图需要至少使用3中颜色才能完成染色，因此B、C、D不正确。

7. 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $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 在满足上述条件的序列里是最大的。 （注：序列 A 是序列 B 的子序列，当且仅当在保持序列 B 元素顺序的情况下，从序列 B 中删除若干个元素，可以使得剩余的元素构成序列 A）则序列问序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）
   A. 4
   B. 5
   C. 6
   D. 7

答： C
根据定义可知，ABCAAAABA和ABABCBABA的最长公共子序列为：ABCABA

8. 一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 x 点，得到 2x 元；第二次掷出 y 点，当 y=x 时玩家会失去之前得到的 2x 元，而当 y≠x 时玩家能保住第一次获得的 2x 元。上述 $x,y\in 1,2,3,4,5,6$。 例如：玩家第 一次掷出 3 点得到 6 元后，但第二次再次掷出 3 点，会失去之前得到的 6 元，玩家最终收益为 0 元；如果玩家第一次掷出 3 点、第二次掷出 4 点，则最终收益是 6 元。假设骰子掷出任意一点的概率均为 $\frac{1}{6}$ ，玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？
   A. 7 元
   B. $\frac{35}{6}$ 元
   C. $\frac{16}{3}$ 元
   D. $\frac{19}{3}$ 元

答： B
该题求的是收益的期望，期望为每种情况发生的概率乘以该情况下随机变量数值的加和。

• 投出1的概率是$\frac{1}{6}$，如果第一次投出1，第二次投骰子有$\frac{1}{6}$的概率投出1，得0元。有$\frac{5}{6}$的概率投出的不是1，得2元。因此得2元的期望为$\frac{1}{6}\ast \frac{5}{6}\ast 2$
• 投出2的概率是$\frac{1}{6}$，如果第一次投出2，第二次投骰子有$\frac{1}{6}$的概率投出2，得0元。有$\frac{5}{6}$的概率投出的不是2，得4元。因此得4元的期望为$\frac{1}{6}\ast \frac{5}{6}\ast 4$
  …
  同理，求出得6、8、10、12元的期望，进行加和即为投两次骰子获得收益的期望。
  $\frac{1}{6}\ast \frac{5}{6}\ast 2+\frac{1}{6}\ast \frac{5}{6}\ast 4+\frac{1}{6}\ast \frac{5}{6}\ast 6+\frac{1}{6}\ast \frac{5}{6}\ast 8+\frac{1}{6}\ast \frac{5}{6}\ast 10+\frac{1}{6}\ast \frac{5}{6}\ast 12=\frac{5}{36}\ast (2+4+6+8+10+12)=\frac{5\ast 42}{36}=\frac{35}{6}$

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

int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c; 

请问，res 的值是什么？（）
提示：在C++中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。
A. true
B. false
C. 1
D. 0

答： A
根据运算符的优先级，在表达式中加括号，得到
(a & b) || ((c ^ b) && (a | c))
$a=5=(101{)}_2$
$b=3=(11{)}_2$
$c=4=(100{)}_2$
a & b= 101 & 11 = 101
c ^ b = 100 ^ 11 = 111
a | c = 101 | 100 = 101
注意，对于逻辑运算（与&&，或||，非！)，0被认为是假false，非0认为是真true。
(c ^ b) && (a | c) = 111 && 101 = true && true = true
(a & b) || ((c ^ b) && (a | c)) = 101 && true = true && true = true;
注意：res是bool类型变量，占1字节，bool类型变量只有两种值：true与false。而0、1是int类型常量，占4字节，因此在概念上1并不等同于true，0并不等同于false，只不过在写代码时，0、1的作用与true、false一般相同，因而一般不加区分。
比如bool a = 1，是将int类型常量1强转为bool类型量true，而后负值给bool类型变量a。
该题问的是res的值，因此只能填bool类型的常量值，因此结果为true，选A。

10. 假设快速排序算法的输入是一个长度为n的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?
    A. 快速排序对于此类输入的表现最好，因为数组已经排序。
    B. 快速排序对于此类输入的时间复杂度是 $\Theta (n\log n)$
    C. 快速排序对于此类输入的时间复杂度是 $\Theta (n^2)$
    D. 快速排序无法对此类数组进行排序，因为数组已经排序。

答：C
考察快速排序的退化。每趟快速排序选择一个基准元素，将序列分为前后两部分，假设进行升序排序，那么一趟快速排序后，前一部分的元素都要满足小于等于基准元素，后一部分的元素都要满足大于等于基准元素。前后两部分的长度未必相同。每趟快速排序要遍历序列中的所有元素，是$O(n)$复杂度。而后分别对前后两部分进行快速排序。
如果长为n的序列有序，而且每次选第一个元素为基准元素，那么会导致分成的两部分的长度为1和n-1。下一次对长为n-1的序列进行一趟快速排序，分成的两部分分别为1和n-2，……，依此类推。一共会进行大约n趟的快速排序，每趟遍历到的元素数量分别为n, n-1, …, 2, 1，循环次数大约为n+n-1+…+1 = n(n-1)/2，其时间复杂度为$O(\frac{n(n-1)}{2})=O(\frac{n^2}{2}-\frac{n}{2})=O(n^2)$，因此选C。

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

答： A
g++编译指令的格式为：g++ cpp源文件名 -o 输出文件名
-o是可选参数，其后是编译后得到的文件的名字。如果写的是-o main.cpp，那么生成的文件名字就是main.cpp，而不是main。况且该目录下已经有main.cpp了，无法再生成同名的文件。
而cpp源文件名在前或在后不影响指令的执行。
因此写为：g++ -o 输出文件名 cpp源文件名，也可以正常完成编译。

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

答：C
树的重心具有性质：当有两个重心时，树的结点数为偶数，并且这两个重心通过一条边直接相连。
该命题的逆否命题为：如果数的结点数不为偶数，树没有两个重心。
树只可能有一个或两个重心，数的结点数不是奇数就是偶数，因此该命题为：
如果数的结点数为奇数，树只有一个重心。

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

答：C
一个有向图可以进行拓扑排序的前提是该图是有向无环图。显然，当前顶点1、3、4构成是一个环，只要删掉该环上的任意一条边，就可以使整个图变为有向无环图。可以删除边<1,3>，❤️,4>或<4,1>。

14. 若 $n={\sum }_{i=0}^{k}16^i\cdot x_i$，定义 $f(n)={\sum }_{i=0}^k{x}_i$，其中 x i ∈ { 0 , 1 , ⋯ , 15 } x_i\in\{0,1,\cdots,15\} xi​∈{0,1,⋯,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$的不动点。问在 $100_{16}$到 $1A{0}_{16}$中，关于$f$的不动点为9的自然数个数为（）。
    A. 10
    B. 11
    C. 12
    D. 13

答：B
该题概念类似OpenJudge NOI 1.13 50:数根
$n={\sum }_{i=0}^{k}16^i\cdot x_i$表示对数值n在16进制下进行按位权展开。
$f(n)={\sum }_{i=0}^k{x}_i$就是求n在16进制下各数位上的数之和。
$n_i=f(n_{i-1})$表示后一个数字就是前一个数字在16进制下各数位上的数之和。
$n_m=n_{m-1}$表示$n_m$各数位上的和就是自己，满足$f(n_m)=n_m$
显然，只有当$n_m$是1位十六进制数时，才能满足$f(n_m)=n_m$，该数就是$n_0$的不动点
简单来说，一个数的不动点就是该数在十六进制下将所有位数字加和，得到的数字只要不是1位数，再将每位数字加和，直到最后剩下1位十六进制数，该数就是不动点。
接下来考虑不动点为9的数字，以下写出的数字都是十六进制数字
首先1位十六进制数中，只有9的不动点是9。
接下来找经过一次$f$函数处理后，可以得到9的数字，有18, 27, 36, 45, 54, 63, 72, 81, 90。
如果某数字各位加和为上述各数字(如18），不动点也是9。
加和为18的两位数有：9F, AE, BD, CC, DB, EA, F9。
由于每位最大为F，F+F=1E，不可能有加和第1位（从低位到高位数，最低位为第0位）为2的两位数。
根据以上查找过程，我们可以找从100到1A0的不动点为9的数字。
各位加和为9的数字有：108, 117, 126, 135, 144, 153, 162, 171, 180
各位加和为18的数字有：18F, 19E
在第2位为1的情况下，最大数字1FF， 1+F+F=1F，第1位不可能大于1。
因此以上就是100到1A0中所有不动点为9的数字，共11个。

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

double quick_power(double x, unsigned n) {if (n == 0) return 1;if (n == 1) return x;return quick_power(x, n / 2)* quick_power(x, n / 2)* ((n & 1) ? x : 1);
}

A. $O(n)$
B. $O(1)$
C. $O(logn)$
D. $O(n\log n)$

答：A
结果是O(n)，
方法1：可以用数学归纳法证明调用quick_power(x, n)的时间复杂度为$O(n)$
当n=1时，需要执行1条语句，时间频度$T(1)=1$，时间复杂度为$O(n)$
假设当n<k(k>=2)时，时间复杂度为$O(n)$，当n=k时：
要想执行quick_power(x, n)，需要先执行2次quick_power(x, n/2)，每次执行的时间复杂度为$O(n/2)$，其时间频度为$T(n/2)=c\cdot n/2+d$，其中c和d是常数。而后执行了做乘法等几次基本运算，记作e次运算，总时间频度$T(n)=2T(n/2)+e=2c\cdot n/2+2d+e=c\cdot n+2d+e$
时间复杂度$O(T(n))=O(c\cdot n+2d+e)=O(n)$
方法2：使用主定理
主定理基本形式为$T(n)=aT(n/b)+f(n)$，其中a为子问题个数，$\frac{1}{b}$为子问题规模和原问题的比值。
如果$O(n^{{\log }_{b}a})>O(f(n))$，则该算法的时间复杂度为$O(n^{{\log }_{b}a})$
该递归函数的时间频度递推式可以写为：$T(n)=2T(n/2)+1$
$a=2,b=2,f(n)=1$
$O(n^{{\log }_{b}a})=O(n^{{\log }_{2}2})=O(n^1)=O(n)$，$O(f(n))=O(1)$
$O(n)>O(1)$，因此$O(T(n))=O(n)$

二、阅读程序

阅读程序(1)
阅读程序(2)
阅读程序(3)

三、完善程序

完善程序(1)
完善程序(2)