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

1. 链表不具备的特点是（ ）。

   {{ select(1) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

2. 双向链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p，则下述语句中错误的是（ ） {{ select(2) }}

• p->next->prev = p->next;
  p->prev->next = p->prev;
  delete p;
  

• p->prev->next = p->next;
  p->next->prev = p->prev;
  delete p;
  

• p->next->prev = p->prev;
  p->next->prev->next = p->next;
  delete p;
  

• p->prev->next = p->next;
  p->prev->next->prev = p->prev;
  delete p;
  

3. 以下代码实现了一个空的双向循环链表，横线上应填的最佳代码是（ ）

{{ select(3) }}

• list->head->prev = list->head; list->tail->prev = list->head;
• list->head->next = list->tail; list->tail->prev = list->head;
• list->head->next = list->tail; list->tail->next = list->head;
• list->head->next = list->tail; list->tail->next = nullptr;

4. 用以下辗转相除法（欧几里得算法）求 gcd(84, 60) 的步骤中，第二步计算的数是（ ）

{{ select(4) }}

• 84 和 60
• 60 和 24
• 24 和 12
• 12 和 0

5. 根据唯一分解定理，下面整数的唯一分解是正确的（ ） {{ select(5) }}

• 18 = 3 × 6
• 28 = 4 × 7
• 36 = 2 × 3 × 6
• 30 = 2 × 3 × 5

6. 下述代码实现素数表的线性筛法，横线上应填的最佳代码是（ ）

{{ select(6) }}

• j < primes.size()
• i * primes[j] <= n
• j < primes.size() && i * primes[j] <= n
• j <= n

7. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 {{ select(7) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

8. 对下面两个函数，说法错误的是（ ）

{{ select(8) }}

• 两个函数实现的功能相同
• 两个函数的时间复杂度均为 O(n)
• factorialA 采用递归方式
• factorialB 采用递归方式

9. 下列算法中，（ ）是不稳定的排序。 {{ select(9) }}

• 选择排序
• 插入排序
• 归并排序
• 冒泡排序

10. 以下 C++ 快速排序代码中，横线上应填的最佳代码是（ ）

{{ select(10) }}

• if (arr[j] > pivot) {
      i++;
      swap(arr[i], arr[j]);
  }
  

• if (arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
  }
  

• if (arr[j] < pivot) {
      swap(arr[i], arr[j]);
      i++;
  }
  

• if (arr[j] == pivot) {
      i++;
      swap(arr[i], arr[j]);
  }
  

11. 若用二分法在 [1, 100] 内猜数，最多需要猜（ ）次。 {{ select(11) }}

• 100
• 10
• 7
• 5

12. 以下二分查找代码中，横线上能填写的最佳代码是（ ）

{{ select(12) }}

• int mid = left + (right - left) / 2;
• int mid = left;
• int mid = (left + right) / 2;
• int mid = right;

13. 贪心算法的核心特征是（ ） {{ select(13) }}

• 总是选择当前最优解
• 回溯尝试所有可能
• 分阶段解决子问题
• 总能找到最优解

14. 函数 int findMax(int arr[], int low, int high) 计算数组中最大元素，其中数组 arr 从索引 low 到 high，（ ）正确实现了分治逻辑。 {{ select(14) }}

• 
• 
• 
• 

15. 以下高精度乘法函数中，横线上应填写的代码为（ ）

{{ select(15) }}

• int temp = c[k];
• int temp = c[k] + carry;
• int temp = c[k] - carry;
• int temp = c[k] * carry;

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

16. 单链表中删除某个结点 p（非尾结点），但不知道头结点，可行的操作是将 p 的值设为 p->next 的值，然后删除 p->next。 {{ select(16) }}

• 正确
• 错误

17. 链表存储线性表时要求内存中可用存储单元地址是连续的。 {{ select(17) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

20. 递归函数必须具有一个终止条件，以防止无限递归。 {{ select(20) }}

• 正确
• 错误

21. 快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n log n)$。 {{ select(21) }}

• 正确
• 错误

22. 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n log n)$。 {{ select(22) }}

• 正确
• 错误

23. 二分查找适用于对无序数组和有序数组的查找。 {{ select(23) }}

• 正确
• 错误

24. 小杨有 100 元去超市买东西，每个商品有各自的价格，每种商品只能买 1 个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。 {{ select(24) }}

• 正确
• 错误

25. 归并排序体现了分治算法，每次将大的待排序数组划分成大小大致相等的两个小数组，然后分别对两个小数组排序，最后对排好序的两个小数组合并成有序数组。 {{ select(25) }}

• 正确
• 错误