一、单项选择题（每题 2 分，共 15 题）

1. 以下哪种情况使用链表比数组更合适（ ）。 {{ select(1) }}

• 数据量固定且读多写少
• 需要频繁在中间或开头插入、删除元素
• 需要高效随机访问元素
• 存储空间必须连续

2. 函数 removeElements 删除单链表中所有结点值等于 val 的结点，并返回新的头结点（head 为头结点），横线处应填写（ ）。

   

{{ select(2) }}

• Node* del = cur;
  cur = del->next;
  delete del;
  

• Node* del = cur->next;
  cur->next = del;
  delete del;
  

• Node* del = cur->next;
  cur->next = del->next;
  delete del;
  

• Node* del = cur->next;
  delete del;
  cur->next = del->next;
  

3. 函数 hasCycle 采用 Floyd 快慢指针判断单链表是否有环：slow 每次走 1 步，fast 每次走 2 步；若有环，两者终会相遇；若无环，fast 会先到达 nullptr。横线上应填写（ ）。

   

   {{ select(3) }}

• slow = slow->next;
  fast = fast->next->next;
  

• slow = fast->next;
  fast = slow->next->next;
  

• slow = slow->next;
  fast = slow->next->next;
  

• slow = fast->next;
  fast = fast->next->next;
  

4. isPerfectNumber 判断正整数是否为完全数（等于其真因子之和）。横线处应填写（ ）。 真因子示例：$28$ 的真因子为 $1,2,4,7,14$。

   

   {{ select(4) }}

• i <= n
• i*i <= n
• i <= n/2
• i < n

5. 以下代码计算两个正整数的最大公约数（GCD），横线上一填写（ ）。

   

   {{ select(5) }}

• b
• a
• temp
• a * b

6. 函数 $sieve$ 实现埃拉托斯特尼筛法（筛法），横线处应填入（ ）。

   

   {{ select(6) }}

• i
• i+1
• i*2
• i*i

7. 函数 $linearSieve$ 实现线性筛法（欧拉筛），横线处应填入（ ）。

{{ select(7) }}

• i % p == 0
• p % i == 0
• i == p
• i * p == n

8. 关于埃氏筛与线性筛的比较，下列说法错误的是（ ）。 {{ select(8) }}

• 埃氏筛可能会对同一个合数进行多次标记
• 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• 线性筛保证每个合数只被其最小质因子筛到一次
• 对于常见范围 $(n \le 10^7)$，埃氏筛因实现简单、常数较小，速度往往优于线性筛

9. “唯一分解定理”描述的是（ ）。 {{ select(9) }}

• 每个整数都能表示为任意素数的乘积
• 每个大于 1 的整数能唯一分解为素数幂乘积（忽略顺序）
• 合数不能分解为素数乘积
• 素数只有两个因子：1 和自身

10. 第 10 题 给定一个 $n \times n$ 的矩阵 matrix，矩阵的每一行和每一列都按升序排列。函数 $countLE$ 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写（）。

{{ select(10) }}

• hi = mid - 1; 和 lo = mid + 1;
• hi = mid; 和 lo = mid;
• hi = mid; 和 lo = mid + 1;
• hi = mid + 1; 和 lo = mid;

11. 下述 C++ 代码实现​快速排序算法​。关于该实现的说法错误的是（ ）。

{{ select(11) }}

• 快速排序之所以叫“快速”，是因为它在平均情况下运行速度快，常数小，就地排序，实现中通常比归并排序更高效。
• 在平均情况下，划分的递归层数为 $log n$，每层中的总循环数为 $n$，总时间为 $O(n \log n)$。
• 在最差情况下，每轮划分操作将数组分成长度为 $0$ 和 $n-1$ 的两个子数组，此时递归达到最深，每层的循环数为 $n$，总时间为 $O(n^2)$。
• 划分函数 partition 中“从右在左查找”与“从左在右查找”的顺序可以交换。

12. 下述 C++ 代码实现​归并排序算法​，横线处应填写（ ）。

{{ select(12) }}

• i < mid
• j < right
• i <= mid
• j <= right

13. 假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 $movies$，其中 $movies[i] = [start_i, end_i]$ 表示第 $i$ 部电影的开始和结束时间。请你找出最多能够排多少部不重叠的电影，则横线处应填入（ ）。

{{ select(13) }}

• a[0] < b[0] 和 lastEnd
• a[1] < b[1] 和 lastEnd
• a[0] < b[0] 和 movies[i][0]
• a[1] < b[1] 和 movies[i][0]

14. 给定一个整数数组 $nums$，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。

{{ select(14) }}

• 上述代码采用分治算法实现
• 上述代码采用贪心算法
• 上述代码时间复杂度为 $O(nlog n)$
• 上述代码采用递归方式实现

15. 第 15 题 给定一个由非负整数构成的数组 $digits$，表示一个非负整数的各位数字，其中最高位在数组首位，且 $digits$ 不包含前导 0（除非是 0 本身）。下面代码对该整数执行 +1 操作，并返回结果数组，则横线处应填写（ ）。

{{ select(15) }}

• digits[i] = 0;
• digits[i] = 9;
• digits[i] = 1;
• digits[i] = 10;

二、判断题（每题 2 分，共 20 分）

16. 基于下面定义的函数，通过判断 $isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)$ 代码可验证如果一个数能被 9 整除，则它的各位数字之和也能被 9 整除。

{{ select(16) }}

• 正确
• 错误

17. 假设函数 $gcd()$ 能正确求两个正整数的最大公约数，则下面的 $findMusicalPattern(4, 6)$ 函数返回 2。

{{ select(17) }}

• 正确
• 错误

18. 第 3 题 下面选项实现的双波那契数列的时间复杂度为 $O(2^n)$。

{{ select(18) }}

• 正确
• 错误

19. 链表通过更改指针实现的结点插入与删除，但结点访问效率低，占用内存较多，且对缓存利用不友好。

    {{ select(19) }}

• 正确
• 错误

20. 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，仅适用于数列或基于数组实现的数据结构。

{{ select(20) }}

• 正确
• 错误

21. 识别图片中内容，转换成Markdown格式，注意数学公式，数学公式用$引起来。 全部结果用代码块引起来。 {{ select(21) }}

• 正确
• 错误

22. 快速排序和归并排序都是稳定的排序算法。 {{ select(22) }}

• 正确
• 错误

23. 下面代码采用分治算法求解标准 3 列汉诺塔问题，时间复杂度为 $O(n \log n)$。

{{ select(23) }}

• 正确
• 错误

24. 所有排序算法都可以转换为选择排序。

{{ select(24) }}

• 正确
• 错误

25. 贪心算法总能得到全局最优解。

{{ select(25) }}

• 正确
• 错误