5620：[GESP202609五级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 小杨用单链表保存任务序列，并同时维护头指针 `head` 和尾指针 `tail`。在链表非空且已知 `tail` 的情况下，在表尾插入新结点的时间复杂度是（ ）
```cpp
01 struct Node {
02 int value;
03 Node *next;
04 };
05
06 Node *head;
07 Node *tail;
```
- $O(1)$
- $O(\log n)$
- $O(n)$
- $O(n\log n)$
**第 2 题** 在不带哨兵结点的双向链表中，结点 `p` 既不是头结点也不是尾结点。删除 `p` 的正确代码是（ ）
```cpp
01 struct Node {
02 int value;
03 Node *prev;
04 Node *next;
05 };
```
- ```cpp
01 p->prev = p->next;
02 p->next = p->prev;
03 delete p;
```
- ```cpp
01 p->prev->next = p;
02 p->next->prev = p;
03 delete p;
```
- ```cpp
01 p->prev->next = p->next;
02 p->next->prev = p->prev;
03 delete p;
```
- ```cpp
01 p->next = p->prev;
02 p->prev->next = nullptr;
03 delete p;
```
**第 3 题** 下面函数使用快慢指针查找单链表的中间结点。横线处应填写（ ）
```cpp
01 struct Node {
02 int value;
03 Node *next;
04 };
05
06 Node *middle(Node *head) {
07 Node *slow = head;
08 Node *fast = head;
09 while (fast != nullptr && fast->next != nullptr) {
10 slow = slow->next;
11 ______________________
12 }
13 return slow;
14 }
```
- `fast = fast->next;`
- `fast = fast->next->next;`
- `fast = slow->next;`
- `fast = head->next;`
**第 4 题** 函数 `gcd(int a, int b)` 定义如下，则 `gcd(105, 45)` 的结果是（ ）
```cpp
01 int gcd(int a, int b) {
02 return b == 0 ? a : gcd(b, a % b);
03 }
```
- $3$
- $5$
- $15$
- $45$
**第 5 题** 下面函数用于判断正整数 $n$ 是否为质数。横线处的最佳写法是（ ）
```cpp
01 bool isPrime(int n) {
02 if (n < 2)
03 return false;
04 for (int i = 2; __________________; i++) {
05 if (n % i == 0)
06 return false;
07 }
08 return true;
09 }
```
- `i < n`
- `i <= n / 2`
- `i * i < n`
- `(long long) i * i <= n`
**第 6 题** 下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（ ）
```cpp
01 vector linearSieve(int n) {
02 vector composite(n + 1, false);
03 vector primes;
04
05 for (int i = 2; i <= n; i++) {
06 if (!composite[i])
07 primes.push_back(i);
08 for (int p : primes) {
09 if ((long long)i * p > n)
10 break;
11 composite[i * p] = true;
12 if (__________________)
13 break;
14 }
15 }
16 return primes;
17 }
```
- `p % i == 0`
- `i % p == 0`
- `i == p`
- `i * p == n`
**第 7 题** 根据唯一分解定理，整数 $756$ 的正确质因数分解是（ ）
- $2^2 \times 3^3 \times 7$
- $2^3 \times 3^2 \times 7$
- $2^2 \times 3^2 \times 21$
- $2 \times 3^3 \times 14$
**第 8 题** 函数 `f(int n)` 定义如下，则 `f(4)` 的结果是（ ）
```cpp
01 int f(int n) {
02 if (n == 1)
03 return 1;
04 return n + f(n - 1);
05 }
```
- $4$
- $7$
- $9$
- $10$
**第 9 题** 在升序数组中查找第一个严格大于 `x` 的元素位置，下面代码中的横线应填写（ ）
```cpp
01 int upperBound(const vector &a, int x) {
02 int l = 0, r = (int)a.size();
03 while (l < r) {
04 int mid = l + (r - l) / 2;
05 if (__________________) {
06 l = mid + 1;
07 } else {
08 r = mid;
09 }
10 }
11 return l;
12 }
```
- `a[mid] < x`
- `a[mid] >= x`
- `a[mid] <= x`
- `a[mid] > x`
**第 10 题** 小杨需要把若干箱货物按原顺序分配到 `days` 天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数 `check(cap)` 判断载重量为 `cap` 时能否在规定天数内运完。横线处应填写（ ）
```cpp
01 long long l = maxWeight;
02 long long r = totalWeight;
03
04 while (l < r) {
05 long long mid = l + (r - l) / 2;
06 if (check(mid)) {
07 ____________________
08 } else {
09 ____________________
10 }
11 }
12 cout << l;
```
- `l = mid + 1; 和 r = mid;`
- `r = mid; 和 l = mid + 1;`
- `r = mid - 1; 和 l = mid;`
- `l = mid; 和 r = mid - 1;`
**第 11 题** 下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（ ）
```cpp
01 while (i <= mid && j <= right) {
02 if (__________________) {
03 temp.push_back(a[i++]);
04 } else {
05 temp.push_back(a[j++]);
06 }
07 }
```
- `a[i] < a[j]`
- `a[i] > a[j]`
- `a[i] >= a[j]`
- `a[i] <= a[j]`
**第 12 题** 下面快速排序的划分函数以 `a[right]` 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（ ）
```cpp
01 int partition(int a[], int left, int right) {
02 int pivot = a[right];
03 int i = left - 1;
04 for (int j = left; j < right; j++) {
05 if (__________________) {
06 i++;
07 swap(a[i], a[j]);
08 }
09 }
10 swap(a[i + 1], a[right]);
11 return i + 1;
12 }
```
- `a[j] <= pivot`
- `a[j] > pivot`
- `a[i] <= pivot`
- `a[right] < a[j]`
**第 13 题** 小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间 `start` 和结束时间 `end`。采用贪心算法时，正确的选择策略是（ ）
```cpp
01 struct Activity {
02 int start;
03 int end;
04 };
```
- 每次选择开始时间最早的活动
- 每次选择持续时间最短的活动
- 每次选择参与人数最少的活动
- 按结束时间从早到晚排序，依次选择与已选活动不冲突的活动
**第 14 题** 下面函数使用迭代方法求最大连续子段和。对于数组 `{-2, 3, -1, 5, -6, 2}`，函数返回值是（ ）
```cpp
01 int maxSubArray(const vector &a) {
02 int best = a[0];
03 int current = a[0];
04 for (int i = 1; i < (int)a.size(); i++) {
05 current = max(a[i], current + a[i]);
06 best = max(best, current);
07 }
08 return best;
09 }
```
- $5$
- $6$
- $7$
- $8$
**第 15 题** 数组 $a$ 和 $b$ 按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（ ）。
```cpp
01 vector add(const vector &a, const vector &b) {
02 vector c;
03 int carry = 0;
04 int n = max(a.size(), b.size());
05
06 for (int i = 0; i < n; i++) {
07 int sum = carry;
08 if (i < a.size())
09 sum += a[i];
10 if (i < b.size())
11 sum += b[i];
12 c.push_back(sum % 10);
13 ____________________
14 }
15 if (carry)
16 c.push_back(carry);
17 return c;
18 }
```
- `carry = sum % 10;`
- `carry = sum;`
- `carry = sum / 10;`
- `carry = c[i] / 10;`
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 下面代码在已知结点 $p$ 的情况下，能够以 $O(1)$ 的时间在单链表的 $p$ 结点之后插入新结点 $s$。
```cpp
01 s->next = p->next;
02 p->next = s;
```
- 正确
- 错误
**第 2 题** 下面代码可以安全地删除单链表的头结点，并使 `head` 指向删除后的新头结点。
```cpp
01 Node *p = head;
02 delete p;
03 head = p->next;
```
- 正确
- 错误
**第 3 题** 下面欧几里得算法既适用于 `a > b`，也适用于 `a < b`，只要 `a`、`b` 是正整数。
```cpp
01 int gcd(int a, int b) {
02 while (b != 0) {
03 int r = a % b;
04 a = b;
05 b = r;
06 }
07 return a;
08 }
```
- 正确
- 错误
**第 4 题** 下面埃氏筛从 `i * i` 开始标记，是因为 `i * i` 之前的 `i` 的合数倍数已经被更小的质因子标记过。
```cpp
01 for (int i = 2; (long long)i * i <= n; i++) {
02 if (isPrime[i]) {
03 for (int j = i * i; j <= n; j += i) {
04 isPrime[j] = false;
05 }
06 }
07 }
```
- 正确
- 错误
**第 5 题** 下面程序的时间复杂度为 $O(n)$。
```cpp
01 for (int i = 1; i <= n; i *= 2) {
02 cout << i << endl;
03 }
```
- 正确
- 错误
**第 6 题** 若数组 $a$ 已按升序排列，下面函数能够返回最后一个小于等于 $x$ 的元素下标；如果不存在，则返回 $-1$。
```cpp
01 int findLastLE(const vector &a, int x) {
02 int l = 0, r = (int)a.size() - 1;
03 int ans = -1;
04 while (l <= r) {
05 int mid = l + (r - l) / 2;
06 if (a[mid] <= x) {
07 ans = mid;
08 l = mid + 1;
09 } else {
10 r = mid - 1;
11 }
12 }
13 return ans;
14 }
```
- 正确
- 错误
**第 7 题** 快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 $O(n\log n)$。
- 正确
- 错误
**第 8 题** 归并排序的递推式为 $T(n) = 2T(n/2) + O(n)$，对应的时间复杂度为 $O(n\log n)$。
- 正确
- 错误
**第 9 题** 下面的贪心代码一定能对任意硬币面值集合 `coins` 求出 `money` 所需的最少硬币数。
```cpp
01 int count = 0;
02 for (int coin : coins) { // coins 按面值从大到小排列
03 count += money / coin;
04 money %= coin;
05 }
```
- 正确
- 错误
**第 10 题** 假设两个非负高精度整数分别存储在数组 `a` 和 `b` 中，且 $a \ge b$。数组采用低位在前的方式存储，即 `a[0]` 表示个位。下面代码中的 `c` 可以正确保存 $a - b$ 的各位数字。
```cpp
01 int borrow = 0;
02 for (int i = 0; i < len; ++i) {
03 int t = a[i] - b[i] + borrow;
04 if (t < 0) {
05 t += 10;
06 borrow = 1;
07 } else {
08 borrow = 0;
09 }
10 c[i] = t;
11 }
```
- 正确
- 错误