一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 下⾯关于链表和数组的描述，错误的是： {{ select(1) }}

• 当数据数量不确定时，为了应对各种可能的情况，需要申请⼀个较⼤的数组，可能浪费空间；此时⽤链表比较合适，大小可动态调整。
• 在链表中访问节点的效率较低，时间复杂度为 $O(n)$。
• 链表插⼊和删除元素效率较低，时间复杂度为 $O(n)$。
• 链表的节点在内存中是分散存储的，通过指针连在⼀起。

2. 在循环单链表中，节点的 next 指针指向下⼀个节点，最后⼀个节点的 next 指针指向（ ）。 {{ select(2) }}

• 当前节点
• nullptr
• 第⼀个节点
• 上⼀个节点

3. 为了⽅便链表的增删操作，⼀些算法⽣成⼀个虚拟头节点。下⾯代码实现了删除链表中值为 val 的节点，横线处应填的最佳代码是：

{{ select(3) }}

• dummyHead->next = head; cur = dummyHead;
• dummyHead->next = head->next; cur = dummyHead;
• dummyHead->next = head; cur = dummyHead->next;
• dummyHead->next = head->next; cur = dummyHead->next;

4. 对下⾯两个斐波那契数列函数，描述错误的是：

{{ select(4) }}

• 两个函数实现的功能相同。
• fibA 采⽤递推⽅式。
• fibB 采⽤递归⽅式。
• fibA 时间复杂度为 $O(n)$，fibB 的时间复杂度为$O(n^2)$ 。

5. 两块⻓⽅形⼟地的⻓宽分别为 24 和 36 ⽶，要将它们分成正⽅形⼩块，使得正⽅形的尺⼨尽可能⼤。下列 gcd(24, 36) 的调⽤顺序正确的是：

{{ select(5) }}

• gcd(24, 36) → gcd(24, 12) → gcd(12, 0)
• gcd(24, 36) → gcd(12, 24) → gcd(0, 12)
• gcd(24, 36) → gcd(24, 12)
• gcd(24, 36) → gcd(12, 24)

6. 下述函数将⾃然数 n 的质因数全部找出，横线处应填的最佳代码是：

   

{{ select(6) }}

• for (int i = 3; i <= n; i ++)
• for (int i = 3; i * i <= n; i ++)
• for (int i = 3; i <= n; i += 2)
• for (int i = 3; i * i <= n; i += 2)

7. 下述代码实现埃拉托⾊尼筛法，筛选出所有 ≤ n 的素数。以下说法正确的是：

{{ select(7) }}

• 代码的时间复杂度是 $O(n\sqrt{n})$。
• 在标记⾮素数时，代码从 $i^2$ 开始，可以减少重复标记。
• 代码会输出所有⼩于等于 n 的奇数。
• 调⽤ sieve_Eratosthenes(10) 返回的数组为 2, 3, 5, 7, 9。

8. 下述代码实现素数表的线性筛法。以下说法正确的是：

{{ select(8) }}

• 线性筛的时间复杂度是 $O(n)$。
• 每个合数会被其所有的质因⼦标记⼀次。
• 线性筛和埃拉托⾊尼筛的实现思路完全相同。
• 以上都不对

9. 以下关于快速排序的说法正确的是： {{ select(9) }}

• 快速排序通过递归对⼦问题求解。
• 快速排序的最坏时间复杂度是 $O(nlogn)$。
• 快速排序是⼀个稳定的排序算法。
• 在最优情况下，快速排序的时间复杂度是 $O(n)$。

10. 关于归并排序，下列描述正确的是： {{ select(10) }}

• 归并排序是⼀个不稳定的排序算法。
• 归并排序的时间复杂度在最优、最差和平均情况下都是 $O(nlogn)$。
• 归并排序需要额外的 $O(1)$ 空间。
• 对于输入数组 {12, 11, 13, 5, 6, 7}，输出为 7 6 5 13 12 11。

11. 给定⻓度为 n 的有序数组 nums，以下关于二分查找函数的描述不正确的是： {{ select(11) }}

• 采用二分查找，每次计算中点并排除一半区间。
• 递归求解，每次问题规模减半。
• 若数组不含 target，递归不会终⽌。
• 算法复杂度为 $O(logn)$。

12. 给定可能含重复元素的有序数组 nums，以下代码返回元素 target 的左边界（不存在返回 −1）。横线处应填： {{ select(12) }}

• right = middle - 1;
• right = middle;
• right = middle + 1;
• 以上都不对

13. 假设有多个孩子，数组 g 保存所有孩子的胃口值。有多块饼干，数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩子的数目，则横线上应填写的代码为（ ）。

{{ select(13) }}

• result++; index--;
• result--; index--;
• result--; index++;
• result++; index++;

14. 关于分治算法，下列说法不正确的是： {{ select(14) }}

• 分治算法将问题分成⼦问题，然后分别解决⼦问题，最后合并结果。
• 归并排序采⽤了分治思想。
• 快速排序采⽤了分治思想。
• 冒泡排序采⽤了分治思想。

15. 下列关于下述⾼精度减法函数的说法正确的是：

{{ select(15) }}

• 若数组 b 表示的整数 < 数组 a 表示的整数，代码能正确返回负差。
• 假设输入数字倒序存储，例如 500 存为 {0, 0, 5}。
• 代码的时间复杂度为 $O(a.size() + b.size())$。
• 当结果为 0 时，结果数组仍会存储多个 0。

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

16. 单链表只⽀持在表头进⾏插⼊和删除操作。 {{ select(16) }}

• 正确
• 错误

17. 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最⼩质因数筛去⼀次，因此效率更⾼。 {{ select(17) }}

• 正确
• 错误

18. 任何⼀个⼤于 1 的⾃然数都可以分解成若干个不同的质数的乘积，且分解⽅式是唯⼀的。 {{ select(18) }}

• 正确
• 错误

19. 贪⼼算法通过每⼀步选择当前最优解，从⽽⼀定能获得全局最优解。 {{ select(19) }}

• 正确
• 错误

20. 递归算法必须有⼀个明确的结束条件，否则会导致⽆限递归并可能引发栈溢出。 {{ select(20) }}

• 正确
• 错误

21. 快速排序和归并排序的平均时间复杂度均为 $O(nlogn)$，且都是稳定排序。 {{ select(21) }}

• 正确
• 错误

22. 快速排序的时间复杂度总⽐插⼊排序的时间复杂度低。 {{ select(22) }}

• 正确
• 错误

23. ⼆分查找仅适⽤于数组⽽不适合链表，因为⼆分查找需要跳跃式访问元素，链表中执⾏跳跃式访问的效率低。 {{ select(23) }}

• 正确
• 错误

24. 对有序数组 {5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100} 进⾏⼆分查找，成功查找元素 19 的比较次数是 2。 {{ select(24) }}

• 正确
• 错误

25. 递归函数每次调⽤⾃⾝时，系统都会为新开启的函数分配内存，以存储局部变量、调⽤地址等信息，导致递归通常⽐迭代更耗内存空间。 {{ select(25) }}

• 正确
• 错误