CSP-S2023初赛

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

A.$O(m\sqrt{logn}·loglogn)$

B.$O(n^2+m)$

C.$\frac{n^2}{logn+mlogn}$

D.$O(m+nlogn)$

解析：

一道图论题，m和n同一级别，可以把所有的m换成n来比较，$loglogn<\sqrt{logn}$，因此$A＜D＜C＜B$。所以选A。

错误原因：

蒙的，蒙错了。

---

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列X=x$1$，x$2$，x$3$，……，xm 和Y=y$1$，y$2$，y$3$，……，yn，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 Z=z$1$，z$2$，z$3$……，zk，使得序列Z即使序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。则序列ABCAAAABA和ABABCBABA的最长公共子序列长度为（）。

A.$4$

B.$5$

C.$6$

D.$7$

解析：

可以发现，先匹配头尾的AB和ABA（因为它们都有），长度为$5$，剩下CAAA和ABCB只有一个可取。所以选C。

错误原因：

手滑点错了，所以以后在递交之前一定要在检查一遍。

---

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

A.快速排序对于此类输入的表现最好，因为数组已经排序。

B.快速排序对于此类输入的时间复杂度是$O(nlogn)$。

C.快速排序对于此类输入的时间复杂度是$O(n^2)$。

D.快速排序无法对此数组进行排序，因为数组已经排序。

解析：

快速排序越有序越慢，因为没法均分为两组，而是分成了$1$和n-$1$。所以选C。

错误原因：

不记得快速排序越有序越慢的原理了，以后要把十大排序的时间复杂度记好。

---

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

A.$4$个节点的数

B.$6$个节点的数

C.$7$个节点的数

D.$8$个节点的数

解析：

重心可能有两个，偶数个结点的树我们可以构造成一条链，当中的两个结点都是重心。故排除A、B、D。所以选C。

错误原因：

没有理解什么是树的重心。

---

若$n=\sum^k_{i=0}16^i·x_i$，定义$f(n)=\sum^k_{i=0}·x_i$，其中$x_i$∈{0,1,⋯,15}。对于给定自然数 $n_0$，存在序列 $n_0，n_1，n_2，……，n_m$，其中对于 $1≤i≤m$ 都有 $n_i=f(n_i-1)$ 且$n_m=n_{m-1}$，称$n_m$为$n_0$关于$f$的不动点，问在 $100_{16}$ 到 $1A0_{16}$ 关于 $f$ 的不动点为 $9$ 的自然数个数为（）。

A.$10$

B.$11$

C.$12$

D.$13$

解析：

$n$可以写成$16$进制，$x_k，……，x_1，x_0$，$f(n)$实际上各个位的和，也就是在固定范围内找各位数字和为$9$的数或者几次变换后数字和为$9$的数。$108$，$117$，$126$，$135$，$144$，$153$，$162$，$171$，$180$，（$9$个），$100(16)-1A0(16)$范围内数字和最大为$25$，仅当数字和是$24$，即$18(16)$时，序列的下一个数能变为$9$，而数字和$24$的数只有$18F$和$19E$两个，所以加起来一共$11$个。所以选B。

错误原因：

（你觉得我可能会吗）计算中出现了问题。

谢谢