一、单选题（每题 $2$ 分，共 $30$ 分）

$1、$​​ 链表不具备的特点是( )。

{{ select(1) }}

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

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

{{ select(2) }}

• 
• 
• 
• 

$3、$ 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 head 和 tail ，链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是( )。

1 // 链表结点
2 template <typename T>
3 struct ListNode {
4     T data;
5     ListNode* prev;
6     ListNode* next;
7     // 构造函数
8     explicit ListNode(const T& val = T())
9         : data(val), prev(nullptr), next(nullptr) {}
10 };
11 
12 struct LinkedList {
13     ListNode<T>* head;
14     ListNode<T>* tail;
15 };
16 
17 void InitLinkedList(LinkedList* list) {
18     list->head = new ListNode<T>;
19     list->tail = new ListNode<T>;
20     ________________________________ // 在此处填入代码
21 };

{{ select(3) }}

• 
• 
• 
• 

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

1 int gcd(int a, int b) {
2     int big = a > b ? a : b;
3     int small = a < b ? a : b;
4     if (big % small == 0) {
5         return small;
6     }
7     return gcd(small, big % small);
8 }

{{ 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、$ 下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，横线上应填的最佳代码是( )

1 vector<int> sieve_linear(int n) {
2     vector<bool> is_prime(n +1, true);
3     vector<int> primes;
4     if (n < 2) return primes;
5     is_prime[0] = is_prime[1] = false;
6     for (int i = 2; i <= n/2; i++) {
7         if (is_prime[i])
8             primes.push_back(i);
9         for (int j = 0; ________________________________ ; j++) { // 在此处填入代码
10             is_prime[ i * primes[j] ] = false;
11             if (i % primes[j] == 0)
12                 break;
13         }
14     }
15     for (int i = n/2 +1; i <= n; i++) {
16         if (is_prime[i])
17             primes.push_back(i);
18     }
19     return primes;
20 }

{{ select(6) }}

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

$7、$ 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

{{ select(7) }}

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

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

1 int factorialA(int n) {
2     if (n <= 1) return 1;
3     return n * factorialA(n-1);
4 }
5 
6 int factorialB(int n) {
7     if (n <= 1) return 1;
8     int res = 1;
9     for(int i=2; i<=n; i++)
10         res *= n;
11 }

{{ select(8) }}

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

$9、$ 下算法中，（ ）是不稳定的排序。

{{ select(9) }}

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

$10、$ 考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是( )

1 int partition(vector<int>& arr, int low, int high) {
2     int pivot = arr[high]; // 基准值
3     int i = low - 1;
4     for (int j = low; j < high; j++) {
5         ________________________________ // 在此处填入代码
6     }
7     swap(arr[i + 1], arr[high]);
8     return i + 1;
9 }
10 
11 // 快速排序
12 void quickSort(vector<int>& arr, int low, int high) {
13     if (low < high) {
14         int pi = partition(arr, low, high);
15         quickSort(arr, low, pi - 1);
16         quickSort(arr, pi + 1, high);
17     }
18 }

{{ select(10) }}

• 
• 
• 
• 

$11、$ 若用二分法在[1, 100]内猜数，最多需要猜（ ）次。

{{ select(11) }}

• 100
• 10
• 7
• 5

$12、$ 下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码 是（ ）。

1 int binarySearch(int arr[], int left, int right, int target) {
2     while (left <= right) {
3         ________________________________ // 在此处填入代码
4         if (arr[mid] == target)
5             return mid;
6         else if (arr[mid] < target)
7             left = mid + 1;
8         else
9             right = mid - 1;
10     }
11     return -1;
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、$ 小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（ ）。

1 vector<int> multiply(vector<int>& a, vector<int>& b) {
2     int m = a.size(), n = b.size();
3     vector<int> c(m + n, 0);
4     // 逐位相乘，逆序存储
5     for (int i = 0; i < m; i++) {
6         for (int j = 0; j < n; j++) {
7             c[i + j] += a[i] * b[j];
8         }
9     }
10     // 处理进位
11     int carry = 0;
12     for (int k = 0; k < c.size(); ++k) {
13         ________________________________ // 在此处填入代码
14         c[k] = temp % 10;
15         carry = temp / 10;
16     }
17     while (c.size() > 1 && c.back() == 0)
18         c.pop_back();
19     return c;
20 }

{{ select(15) }}

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

二、判断题（每题 $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(nlog n)$。

{{ select(21) }}

• 正确
• 错误

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

{{ select(22) }}

• 正确
• 错误

$23、$ 二分查找适用于对无序数组和有序数组的查找。

{{ select(23) }}

• 正确
• 错误

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

{{ select(24) }}

• 正确
• 错误

$25、$ 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

{{ select(25) }}

• 正确
• 错误