CSP 2023 入门级第一轮 讲解

· · 题解

一、单选题：

  1. 常量的关键字是 const，选 B。
  3. data 是一个变量，排除 C 和 D，调用成员时变量名在前，选 A。
  4. 首先申请新空间，再赋值，然后将其下一个节点指向 head，最后将 head 指向它，选 A。
  5. 首先根节点的高度为 1，然后求 \displaystyle\sum_{i=0}^{m-1}3^i\le2023，即 \displaystyle\frac{3^m-1}{2}\le2023，m=8，选 C。
  6. 数学题，参加 1 次就有 7 种，2 次有 10 种，3 次只有 1 种，选 B。
  7. 设两数的长度分别为 n 和 m，高精度乘法复杂度为 \Theta(nm)，选 C。
  8. 建表达式树，答案是 ((6-(2+3))\times(3+8\div2))^2+3，选 A。
  10. 给定了频率，这样就可以建 Huffman 树，选 A。
  11. 已知先序中序求后序，后序遍历是 EDBGFCA，选 A。
  12. 拓扑排序，1 必须是第一个，4 必须是最后一个，选 B。
  13. bit 是存储的基本单位，选 B。
  14. 分类讨论，如果有 1 个女生，有 \displaystyle\binom{10}{2}\times\binom{12}{1}=\frac{10\times9}{2}\times12=540 种选择；如果有 2 个女生，就有 \displaystyle\binom{10}{1}\times\binom{12}{2}=10\times\frac{12\times11}{2}=660 种选择，如果全选女生就有 \displaystyle\binom{12}{3}=\frac{12\times11\times10}{6}=220 种选择，选 A。
  15. HTML 是编程语言，选 D。

二、阅读程序：
（1）：
判断题：

  2. 乘法交换律，正确。
  3. 第 10\sim11 行将浮点数输出设为了 4 位小数，正确。

选择题：

（2）：
判断题：

  1. f 函数返回的是最长公共子序列，当然小于等于 \min(n,m)，正确。
  2. 最长公共子序列非最长公共子串，错误。
  3. 自己当然是自己的子序列，正确。

选择题：

  1. 将 v[m][n] 换成 v[n][m]，当 n\ne m 时会数组越界，选 D。
  2. p-jcs 是 csp-jcsp-j 的子序列，选 B。
  3. spsccp 是 csppsccsppsc 的子序列，选 D。

（3）：
判断题：

  1. solve2 函数返回的就是 n 的因子的平方和，正确。
  2. 就是为了重复计算，正确。
  3. 若 n\in\text{prime}，则其因子只有 1 和 n，因子平方和为 n^2+1，正确。

选择题：

  1. 若 n=p^2,p\in\text{prime}，则其因子有 p^2，p 和 1，因子平方和为 (p^2)^2+P^2+1^2=n^2+n+1，选 B。

三、完善程序：
（1）：

  1. 等差序列第 mid 项是 nums[0]+mid，选 B。
  2. 二分板子，left=mid+1，选 A。
  3. 二分板子，right=mid，选 C。
  4. 第 left 项是 nums[0]+left，选 A。
  5. 最后返回的是 nums[0]+n-1，应为 nums[n-1]，选 D。

（2）：

  1. 当 i=0 时，编辑距离是 j，选 A。
  2. 同上，选 B。
  3. 这里要判断这一位两个字符串是否相等，选 A。
  4. 这里直接不用操作，dp[i-1][j-1]，选 B。
  5. 这里还可以替换，dp[i-1][j-1]，选 C。