5290：[GESP202509五级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：8
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 以下哪种情况使用链表比数组更合适？
- 数据量固定且读多写少
- 需要频繁在中间或开头插入、删除元素
- 需要高效随机访问元素
- 存储空间必须连续
**第 2 题** 函数 `removeElements` 删除单链表中所有结点值等于 `val` 的结点，并返回新的头结点，其中链表头结点为 `head`，则横线处填写 ( )
```cpp
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 }
```
- ```cpp
01 Node* del = cur;
02 cur = del->next;
03 delete del;
```
- ```cpp
01 Node* del = cur–>next;
02 cur–>next = del;
03 delete del;
```
- ```cpp
01 Node* del = cur–>next;
02 cur–>next = del–>next;
03 delete del;
```
- ```cpp
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`，则横线上应填写 ( )
```cpp
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 }
```
- ```cpp
01 slow = slow–>next;
02 fast = fast–>next–>next;
```
- ```cpp
01 slow = fast–>next;
02 fast = slow–>next–>next;
```
- ```cpp
01 slow = slow–>next;
02 fast = slow–>next–>next;
```
- ```cpp
01 slow = fast–>next;
02 fast = fast–>next–>next;
```
**第 4 题** 函数 `isPerfectNumber` 判断一个正整数是否为完全数 (该数是否即等于它的真因子之和)，则横线上应填写 ( )。一个正整数 $n$ 的真因子包括所有小于 $n$ 的正因子，如 $28$ 的真因子为`1, 2, 4, 7, 14`。
```cpp
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 }
```
- `i <= n`
- `i*i <= n`
- `i <= n/2`
- `i < n`
**第 5 题** 以下代码计算两个正整数的最大公约数`(GCD)`，横线上应填写 ( )
```cpp
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 }
```
- `b`
- `a`
- `temp`
- `a * b`
**第 6 题** 函数 `sieve` 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入 ( )
```cpp
01 vector sieve(int n) {
02 vector 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 }
```
- `i`
- `i+1`
- `i*2`
- `i*i`
**第 7 题** 函数 `linearSieve` 实现线性筛法(欧拉筛)，横线处应填入 ( )
```cpp
01 vector linearSieve(int n) {
02 vector is_prime(n+1, true);
03 vector 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 }
```
- `i % p == 0`
- `p % i == 0`
- `i == p`
- `i * p == n`
**第 8 题** 关于埃氏筛和线性筛的比较，下列说法错误的是( )
- 埃氏筛可能会对同一个合数进行多次标记
- 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
- 线性筛保证每个合数只被其最小质因子筛到一次
- 对于常见范围($n \leq 10^7$)，埃氏筛因实现简单，常数较小，其速度往往优于线性筛
**第 9 题** 唯一分解定理描述的是 ( )
- 每个整数都能表示为任意素数的乘积
- 每个大于 $1$ 的整数能唯一分解为素数幂乘积(忽略顺序)
- 合数不能分解为素数乘积
- 素数只有两个因子: $1$ 和自身
**第 10 题** 给定一个 $n \times n$ 的矩阵 $matrix$，矩阵的每一行和每一列都按升序排列。函数 `countLE` 返回矩阵中第
$k$ 小的元素，则两处横线上应分别填写 ( )
```cpp
01 // 统计矩阵中 <= x 的元素个数：从左下角开始
02 int countLE(const vector>& 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>& 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 }
```
- ```cpp
01 hi = mid - 1;
02 lo = mid + 1;
```
- ```cpp
01 hi = mid;
02 lo = mid;
```
- ```cpp
01 hi = mid;
02 lo = mid + 1;
```
- ```cpp
01 hi = mid + 1;
02 lo = mid;
```
**第 11 题** 下述 `C++` 代码实现了快速排序算法，下面说法错误的是 ( )
```cpp
01 int partition(vector& 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& 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 }
```
- 快速排序之所以叫 "快速"，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
- 在平均情况下，划分的递归层数为 $logn$，每层中的总循环数为 $m$，总时间为 $O(nlogn)$。
- 在最差情况下，每轮划分操作都将长度为 $m$ 的数组划分为长度为 $0$ 和 $n-1$ 的两个子数组，此时递归层数达到 $n$，每层中的循环数为 $n$，总时间为 $O(n^2)$。
- 划分函数 `partition` 中 "从右往左查找" 与 "从左往右查找" 的顺序可以交换。
**第 12 题** 下述 `C++` 代码实现了归并排序算法，则横线上应填写 ( )
```cpp
01 void merge(vector &nums, int left, int mid, int right) {
02 // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
03 vector 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 &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 }
```
- `i < mid`
- `j < right`
- `i <= mid`
- `j <= right`
**第 13 题** 假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 $movies$，其中 `movies[i] =
[start_i, end_i]` 表示第 $i$ 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为 ( )。
```cpp
01 int maxMovies(vector>& movies) {
02 if (movies.empty()) return 0;
03
04 sort(movies.begin(), movies.end(), [](const vector& a, const vector& 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 }
```
- `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`，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是 ( )
```cpp
01 int crossSum(vector& 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& 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& nums) {
27 return helper(nums, 0, nums.size() - 1);
28 }
```
- 上述代码采用分治算法实现
- 上述代码采用贪心算法
- 上述代码时间复杂度为 $O(nlogn)$
- 上述代码采用递归方式实现
**第 15 题** 给定一个由非负整数组成的数组$digits$，表示一个非负整数的各位数字，其中最高位在数组首位，且 $digits$ 不含前导 $0$ (除非是 $0$ 本身)。下面代码对该整数执行 $+1$ 操作，并返回结果数组，则横线上应填写 ( )
```cpp
01 vector plusOne(vector& 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 }
```
- ```cpp
digits[i] = 0;
```
- ```cpp
digits[i] = 9;
```
- ```cpp
digits[i] = 1;
```
- ```cpp
digits[i] = 10;
```
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 基于下面定义的函数，通过判断 `isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)` 代码可验算如果一个数能被 $9$ 整除，则它的各位数字之和能被 $9$ 整除。
```cpp
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 }
```
- 正确
- 错误
**第 2 题** 假设函数 `gcd()` 能正确求两个正整数的最大公约数，则下面的 `findMusicalPattern(4，6)` 函数返回 $2$。
```cpp
01 void findMusicalPattern(int rhythm1, int rhythm2) {
02 int commonDivisor = gcd(rhythm1, rhythm2);
03 int patternLength = (rhythm1 * rhythm2) / commonDivisor;
04 return patternLength；
05 }
```
- 正确
- 错误
**第 3 题** 下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。
```cpp
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 }
```
- 正确
- 错误
**第 4 题** 链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。
- 正确
- 错误
**第 5 题** 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。
- 正确
- 错误
**第 6 题** 线性筛关键是 "每个合数只会被最小质因子筛到一次"，因此为 $O(n)$。
- 正确
- 错误
**第 7 题** 快速排序和归并排序都是稳定的排序算法。
- 正确
- 错误
**第 8 题** 下面代码采用分治算法求解标准 $3$ 柱汉诺塔问题，时间复杂度为 $O(nlogn)$。
```cpp
01 void move(vector &src, vector &tar) {
02 int pan = src.back();
03 src.pop_back();
04 tar.push_back(pan);
05 }
06
07 void dfs(int n, vector &src, vector &buf, vector &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 &A, vector &B, vector &C) {
19 int n = A.size();
20 dfs(n, A, B, C);
21 }
```
- 正确
- 错误
**第 9 题** 所有递归算法都可以转换为迭代算法。
- 正确
- 错误
**第 10 题** 贪心算法总能得到全局最优解。
- 正确
- 错误