CSP 2021 提高级第一轮

推荐一个超好的题解 链接

单选

第一题

在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ A ）。

ls：list列表，用于列出目录下文件和子目录。
cp：copy复制。
cd：change directory，切换目录。
all：linux中无此命令。

第五题

以比较为基本运算，对于 2n2n 个数，同时找到最大值和最小值，最坏情况下需要的最小的比 较次数为（ 3n-2 ）。

2n个元素仿照堆的比较方式，两两比较n次（第1个和第2个比，第3个和第4个比…）分两组，胜者组找最大值n-1次，败者组找最小值n-1次，n+(n-1)+(n-1)=3n-2。

第十三题

有 8 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ 54 ）种方案。

动态规划，状态转移方程如下：
n个苹果的总方案数=第n个苹果不选的方案数（记作a） + 第n个苹果选的方案数（记作b）
而a应该与苹果数量为n-1的总方案数相同， b应该与苹果数量为n-1时第n-1个苹果不选的方案数相同

程序阅读

第十七题

将第 26、27 行中的 / sqrt(t) / 2替换为/ 2 / sqrt(t)，不会影响程序运行的结果。（ 错误 ）

交换之后会变成整除，参考3/2/1.0与3/1.0/2的区别 。

第十八题

将第 28 行中的 x * x 改成 sq(x)、y * y 改成 sq(y)，不会影响程序运行的结果。（ 错误 ）

x为double类型，里面存放的值可能为XX.5，而sq(const int x)会先将实参取整，与 x * x 结果不同，故错误。

完善程序题

第三十四题

①处应填（ D ）
A. F[4] = 0
B. F[1] = 4
C. F[1] = 2
D. F[4] = 1

算法的起点是4，所有数字都要用4拼出来，而F[4]=1。