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

第 1 题 以下哪种情况使用链表比数组更合适？

{{ select(1) }}

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

第 2 题 函数 removeElements 删除单链表中所有结点值等于 val 的结点，并返回新的头结点，其中链表头结点为 head，则横线处填写 ( )

01 // 结点结构体
02 struct Node {
03     int val;
04     Node* next;
05
06     Node() : val(θ), next(nullptr) {}
07     Node(int x) : val(x), next(nullptr) {}
08     Node(int x, Node *next) : val(x), next(next) {}
09 };
10
11 Node* removeElements(Node* head, int val) {
12     Node dummy(θ, head); // 哑结点，统一处理头结点
13     Node* cur = &dummy;
14     while (cur->next) {
15         if (cur->next->val == val) {
16             _______________________ // 在此填入代码
17
18         }
19         else {
20             cur = cur->next;
21         }
22     }
23     return dummy.next;
24 }

{{ select(2) }}

• 01 Node* del = cur;
  02 cur = del->next;
  03 delete del;
  

• 01 Node* del = cur–>next;
  02 cur–>next = del;
  03 delete del;
  

• 01 Node* del = cur–>next;
  02 cur–>next = del–>next;
  03 delete del;
  

• 01 Node* del = cur–>next;
  02 delete del;
  03 cur–>next = del–>next;
  

第 3 题 函数 hasCycle 采用 Floyd 快慢指针法判断一个单链表中是否存在环，链表的头节点为 head，即用两个指针在链表上前进：slow 每次走 $1$ 步， fast 每次走 $2$ 步，若存在环， fast 终会追上 slow (相遇)；若无环，fast 会先到达 nullptr，则横线上应填写 ( )

01 struct Node {
02     int val;
03     Node *next;
04     Node(int x) : val(x), next(nullptr) {}
05 };
06
07 bool hasCycle(Node *head) {
08     if (!head || !head–>next)
09         return false;
10     Node* slow = head;
11     Node* fast = head–>next;
12     while (fast && fast–>next) {
13         if (slow == fast) return true;
14         _______________________ // 在此填入代码
15     }
16     return false;
17 }

{{ select(3) }}

• 01 slow = slow–>next;
  02 fast = fast–>next–>next;
  

• 01 slow = fast–>next;
  02 fast = slow–>next–>next;
  

• 01 slow = slow–>next;
  02 fast = slow–>next–>next;
  

• 01 slow = fast–>next;
  02 fast = fast–>next–>next;
  

第 4 题 函数 isPerfectNumber 判断一个正整数是否为完全数 (该数是否即等于它的真因子之和)，则横线上应填写 ( )。一个正整数 $n$ 的真因子包括所有小于 $n$ 的正因子，如 $28$ 的真因子为1, 2, 4, 7, 14。

01 bool isPerfectNumber(int n) {
02     if(n <= 1) return false;
03     int sum = 1;
04     for(int i = 2; ______; i++) {
05         if(n % i == 0) {
06             sum += i;
07             if(i != n/i) sum += n/i;
08         }
09     }
10     return sum == n;
11 }

{{ select(4) }}

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

第 5 题 以下代码计算两个正整数的最大公约数(GCD)，横线上应填写 ( )

01 int gcd0(int a, int b) {
02     if (a < b) {
03         swap(a, b);
04     }
05     while(b != 0) {
06         int temp = a % b;
07         a = b;
08         b = temp;
09     }
10     return ______;
11 }

{{ select(5) }}

• b
• a
• temp
• a * b

第 6 题 函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入 ( )

01 vector<bool> sieve(int n) {
02     vector<bool> is_prime(n+1, true);
03     is_prime[0] = is_prime[1] = false;
04     for(int i = 2; i <= n; i++) {
05         if(is_prime[i]) {
06             for(int j = ______; j <= n; j += i) {
07                 is_prime[j] = false;
08             }
09         }
10     }
11     return is_prime;
12 }

{{ select(6) }}

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

第 7 题 函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入 ( )

01 vector<int> linearSieve(int n) {
02     vector<bool> is_prime(n+1, true);
03     vector<int> primes;
04     for(int i = 2; i <= n; i++) {
05         if(is_prime[i]) primes.push_back(i);
06         for(int p : primes) {
07             if(p * i > n) break;
08             is_prime[p * i] = false;
09             if(________) break;
10         }
11     }
12     return primes;
13 }

{{ select(7) }}

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

第 8 题 关于埃氏筛和线性筛的比较，下列说法错误的是( )

{{ select(8) }}

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

第 9 题 唯一分解定理描述的是 ( )

{{ select(9) }}

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

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

01 // 统计矩阵中 <= x 的元素个数：从左下角开始
02 int countLE(const vector<vector<int>>& matrix, int x) {
03     int n = (int)matrix.size();
04     int i = n – 1, j = 0, cnt = 0;
05     while (i >= 0 && j < n) {
06         if (matrix[i][j] <= x) {
07             cnt += i + 1;
08             ++j;
09         }
10         else {
11             ––i;
12         }
13     }
14     return cnt;
15 }
16 
17 int kthSmallest(vector<vector<int>>& matrix, int k) {
18     int n = (int)matrix.size();
19     int lo = matrix[0][0];
20     int hi = matrix[n – 1][n – 1];
21
22     while (lo < hi) {
23         int mid = lo + (hi - lo) / 2;
24         if (countLE(matrix, mid) >= k) {
25             ________________ // 在此处填入代码
26         } else {
27             ________________ // 在此处填入代码
28         }
29     }
30     return lo;
31 }

{{ select(10) }}

• 01 hi = mid - 1;
  02 lo = mid + 1;
  

• 01 hi = mid;
  02 lo = mid;
  

• 01 hi = mid;
  02 lo = mid + 1;
  

• 01 hi = mid + 1;
  02 lo = mid;
  

第 11 题 下述 C++ 代码实现了快速排序算法，下面说法错误的是 ( )

01 int partition(vector<int>& arr, int low, int high) {
02     int i = low, j = high;
03     int pivot = arr[low]; // 以首元素为基准
04     while (i < j) {
05         while (i < j && arr[j] >= pivot) j--; //从右往左查找
06         while (i < j && arr[i] <= pivot) i++; //从左往右查找
07         if (i < j) swap(arr[i], arr[j]);
08     }
09     swap(arr[i], arr[low]);
10     return i;
11 }
12
13 void quickSort(vector<int>& arr, int low, int high) {
14     if (low >= high) return;
15     int p = partition(arr, low, high);
16     quickSort(arr, low, p - 1);
17     quickSort(arr, p + 1, high);
18 }

{{ select(11) }}

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

第 12 题 下述 C++ 代码实现了归并排序算法，则横线上应填写 ( )

01 void merge(vector<int> &nums, int left, int mid, int right) {
02    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
03    vector<int> tmp(right - left + 1);
04     int i = left, j = mid + 1, k = 0;
05     while (i <= mid && j <= right) {
06         if (nums[i] <= nums[j])
07             tmp[k++] = nums[i++];
08         else
09             tmp[k++] = nums[j++];
10     }
11     while (i <= mid) {
12         tmp[k++] = nums[i++];
13     }
14     while (________) { // 在此处填入代码
15         tmp[k++] = nums[j++];
16     }
17     for (k = 0; k < tmp.size(); k++) {
18         nums[left + k] = tmp[k];
19     }
20 }
21
22 void mergeSort(vector<int> &nums, int left, int right) {
23     if (left >= right)
24         return;
25
26     int mid = (left + right) / 2;
27     mergeSort(nums, left, mid);
28     mergeSort(nums, mid + 1, right);
29     merge(nums, left, mid, right);
30 }

{{ select(12) }}

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

第 13 题 假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 $movies$，其中 movies[i] = [start_i, end_i] 表示第 $i$ 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为 ( )。

01 int maxMovies(vector<vector<int>>& movies) {
02     if (movies.empty()) return 0;
03
04     sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) {
05         return ______; // 在此处填入代码
06     });
07
08     int count = 1;
09     int lastEnd = movies[0][1];
10
11     for (int i = 1; i < movies.size(); i++) {
12         if (movies[i][0] >= lastEnd) {
13             count++;
14             ______ = movies[i][1]; // 在此处填入代码
15         }
16     }
17
18     return count;
19 }

{{ 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，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是 ( )

01 int crossSum(vector<int>& nums, int left, int mid, int right) {
02     int leftSum = INT_MIN, rightSum = INT_MIN;
03     int sum = 0;
04     for (int i = mid; i >= left; i--) {
05         sum += nums[i];
06         leftSum = max(leftSum, sum);
07     }
08     sum = 0;
09     for (int i = mid + 1; i <= right; i++) {
10         sum += nums[i];
11         rightSum = max(rightSum, sum);
12     }
13     return leftSum + rightSum;
14 }
15
16 int helper(vector<int>& nums, int left, int right) {
17     if (left == right)
18         return nums[left];
19     int mid = left + (right - left) / 2;
20     int leftMax = helper(nums, left, mid);
21     int rightMax = helper(nums, mid + 1, right);
22     int crossMax = crossSum(nums, left, mid, right);
23     return max({leftMax, rightMax, crossMax});
24 }
25
26 int maxSubArray(vector<int>& nums) {
27     return helper(nums, 0, nums.size() - 1);
28 }

{{ select(14) }}

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

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

01 vector<int> plusOne(vector<int>& digits) {
02     for (int i = (int)digits.size() - 1; i >= 0; --i) {
03         if (digits[i] < 9) {
04             digits[i] += 1;
05                 return digits;
06         }
07         ________________ // 在此处填入代码
08     }
09     digits.insert(digits.begin(), 1);
10 return digits;
11 }

{{ select(15) }}

• digits[i] = 0;
  

• digits[i] = 9;
  

• digits[i] = 1;
  

• digits[i] = 10;
  

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

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

01 bool isDivisibleBy9(int n) {
02     return n % 9 == 0;
03 }
04
05 bool isDigitSumDivisibleBy9(int n) {
06     int sum = 0;
07     string numStr = to_string(n);
08     for (char c : numStr) {
09         sum += (c - '0');
10     }
11     return sum % 9 == 0;
12 }

{{ select(16) }}

• 正确
• 错误

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

01 void findMusicalPattern(int rhythm1, int rhythm2) {
02     int commonDivisor = gcd(rhythm1, rhythm2);
03     int patternLength = (rhythm1 * rhythm2) / commonDivisor;
04     return patternLength；
05 }

{{ select(17) }}

• 正确
• 错误

第 3 题 下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。

01 long long fib_memo(int n, long long memo[]) {
02     if (n <= 1) return n;
03     if (memo[n] != -1) return memo[n];
04     memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
05     return memo[n];
06 }
07 
08 int main() {
09     int n = 40;
10     long long memo[100];
11     fill_n(memo, 100, -1);
12     long long result2 = fib_memo(n, memo);
13     return 0;
14 }

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

第 6 题 线性筛关键是 "每个合数只会被最小质因子筛到一次"，因此为 $O(n)$。

{{ select(21) }}

• 正确
• 错误

第 7 题 快速排序和归并排序都是稳定的排序算法。

{{ select(22) }}

• 正确
• 错误

第 8 题 下面代码采用分治算法求解标准 $3$ 柱汉诺塔问题，时间复杂度为 $O(nlogn)$。

01 void move(vector<int> &src, vector<int> &tar) {
02     int pan = src.back();
03     src.pop_back();
04     tar.push_back(pan);
05 }
06 
07 void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
08     if (n == 1) {
09         move(src, tar);
10         return;
11     }
12
13     dfs(n - 1, src, tar, buf);
14     move(src, tar);
15     dfs(n - 1, buf, src, tar);
16 }
17
18 void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
19     int n = A.size();
20     dfs(n, A, B, C);
21 }

{{ select(23) }}

• 正确
• 错误

第 9 题 所有递归算法都可以转换为迭代算法。

{{ select(24) }}

• 正确
• 错误

第 10 题 贪心算法总能得到全局最优解。

{{ select(25) }}

• 正确
• 错误