5299：[GESP202603五级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 关于单链表、双链表和循环链表，下列说法正确的是 ( )
- 在单链表中，若已知任意结点的指针，则可以在 $O(1)$ 时间内删除该结点。
- 循环链表中一定不存在空指针。
- 在循环双链表中，尾结点的 `next` 指针一定为 `nullptr`。
- 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 `next` 是否指向自身。
**第 2 题** 双向循环链表中要在结点 `p` 之前插入新结点 `s`(均非空)，以下指针操作正确的是 ( )
- ```cpp
01 s-> next = p;
02 p-> prev = s;
03 p-> next = s;
04 s-> prev = p;
```
- ```cpp
01 s -> prev = p;
02 s -> next = p -> next;
03 p -> next -> prev = s;
04 p -> next = s;
```
- ```cpp
01 s -> next = p;
02 s -> prev = p->prev;
03 p -> prev -> next = s;
04 p -> prev = s;
```
- ```cpp
01 s -> next = p;
02 s -> prev = nullptr;
03 p -> prev = s;
```
**第 3 题** 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填 ( )
```cpp
01 struct Node{
02 int val;
03 Node* next;
04 Node(int v):val(v),next(nullptr){}
05 };
06
07 Node* eraseAll(Node* head, int x){
08 Node dummy(0);
09 dummy.next = head;
10 Node* cur = &dummy;
11 while(cur->next){
12 if(cur->next->val == x){
13 Node* del = cur->next;
14 ______________________
15 delete del;
16 }else cur = cur->next;
17 }
18 return dummy.next;
19 }
```
- ```cpp
01 cur = cur->next;
```
- ```cpp
02 cur->next = del->next;
```
- ```cpp
01 del->next = cur->next;
```
- ```cpp
01 cur->next = nullptr;
```
**第 4 题** 对如下代码实现的欧几里得算法(辗转相除法)，执行 `gcd(48，18)` 得到的调用序列为 ( )
```cpp
01 int gcd(int a, int b) {
02 return b == 0 ? a : gcd(b, a % b);
03 }
```
- ```cpp
01 gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
```
- ```cpp
01 gcd(48,18) -> gcd(30,18) -> gcd(12,18)
```
- ```cpp
01 gcd(48,18) -> gcd(18,30) -> gcd(30,6)
```
- ```cpp
01 gcd(48,18) -> gcd(12,18) -> gcd(6,12)
```
**第 5 题** 下面代码实现了欧拉(线性)筛，横线处应填写 ( )
```cpp
01 vector euler_sieve(int n) {
02 vector is_composite(n + 1, false);
03 vector primes; 04
05 for (int i = 2; i <= n; i++) {
06 if (!is_composite[i])
07 primes.push_back(i);
08
09 for (int j = 0; __________________________ && (long long)i * primes[j] <= n; j++) {
10 is_composite[i * primes[j]] = true;
11
12 if (i % primes[j] == 0)
13 break;
14 }
15 }
16 return primes;
17 }
```
- `j <= n`
- `j < sqrt(n)`
- `j < primes.size()`
- `j < i`
**第 6 题** 埃氏筛中将内层循环从 `j=i*i`开始而不是 `j=2*i` 的主要原因是 ( )
```cpp
01 vector eratosthenes_sieve(int n) {
02 vector is_composite(n + 1, false);
03 vector primes;
04
05 for (int i = 2; i <= n; i++) {
06 if (is_composite[i]) continue;
07
08 primes.push_back(i);
09
10 for (long long j = (long long)i * i; j <= n; j += i)
11 is_composite[j] = true;
12 }
13 return primes;
14 }
```
- 因为 `2*i` 一定不是合数
- `i*i` 一定是质数
- 小于 `i*i` 的 `i` 的倍数已被更小质因子筛过
- 这样可以把时间复杂度降为 $O(n)$
**第 7 题** 下面程序的运行结果为 ( )
```cpp
01 bool check(int n, int a[], int k, int dist) {
02 int cnt = 1;
03 int last = a[0];
04
05 for (int i = 1; i < n; i++) {
06 if (a[i] - last >= dist) {
07 cnt++;
08 last = a[i];
09 }
10 }
11
12 return cnt >= k;
13 }
14
15 int solve(int n, int a[], int k) {
16 std::sort(a, a + n);
17
18 int l = 0;
19 int r = a[n - 1] - a[0];
20
21 while (l < r) {
22 int mid = (l + r + 1) / 2;
23
24 if (check(n, a, k, mid))
25 l = mid;
26 else
27 r = mid - 1;
28 }
29
30 return l;
31 }
32
33 int main() {
34 int a[] = {1, 2, 8, 4, 9};
35 int n = 5;
36 int k = 3;
37
38 std::cout << solve(n, a, k) << std::endl;
39
40 return 0;
41 }
```
- $2$
- $3$
- $4$
- $5$
**第 8 题** 在升序数组中查找第一个大于等于 `x` 的位置，下面循环中横线应填 ( )
```cpp
01 int lowerBound(const vector& a, int x){
02 int l=0, r=a.size();
03 while(l= x) _____________;
06 else l = mid + 1;
07 }
08 return l;
09 }
```
- ```cpp
01 r = mid;
```
- ```cpp
01 r = mid - 1;
```
- ```cpp
01 l = mid;
```
- ```cpp
01 l = mid + 1;
```
**第 9 题** 关于递归函数调用，下列说法错误的是 ( )
- 递归调用层次过深时，可能会耗尽栈空间导致栈溢出
- 尾递归函数可以通过编译器优化来避免栈溢出
- 所有递归函数都可以通过循环结构来改写，从而避免栈溢出
- 栈溢出发生时，程序会抛出异常并可以继续执行后续代码
**第 10 题** 给定 $n$ 根木头，第 `i` 根长度为 `a[i]`。要切成不少于 `m` 段等长木段，求最大可能长度，则横线上应填写 ( )
```cpp
01 const int MAXN = 100005;
02 long long a[MAXN];
03 int n, m;
04
05 bool check(long long x){
06 long long cnt = 0;
07 for(int i = 1; i <= n; i++){
08 if(x == 0) return true;
09 cnt += a[i] / x;
10 if(cnt >= m) return true;
11 }
12 return false;
13 }
14
15 int main(){
16 cin >> n >> m;
17 long long mx = 0;
18 for(int i = 1; i <= n; i++){
19 cin >> a[i];
20 mx = max(mx, a[i]);
21 }
22
23 long long l = 1, r = mx;
24 long long ans = 0;
25
26 while(l <= r){
27 long long mid = l + (r - l) / 2;
28
29 if(check(mid)){
30 ans = mid;
31 ______________________
32 }else{
33 ______________________
34 }
35 }
36
37 cout << ans << endl;
38 return 0;
39 }
```
- ```cpp
01 l = mid + 1;
02 r = mid - 1;
```
- ```cpp
01 l = mid - 1;
02 r = mid + 1;
```
- ```cpp
01 l = mid + 1;
02 r = mid;
```
- ```cpp
01 l = mid;
02 r = mid + 1;
```
**第 11 题** 下面代码用分治求“最大连续子段和”，其时间复杂度为 ( )
```cpp
01 int solve(vector& a, int l, int r){
02 if(l == r) return a[l];
03
04 int mid = l + (r - l) / 2;
05
06 int left = solve(a, l, mid);
07 int right = solve(a, mid + 1, r);
08
09 int sum = 0, lmax = INT_MIN;
10 for(int i = mid; i >= l; i--){
11 sum += a[i];
12 lmax = max(lmax, sum);
13 }
14
15 sum = 0;
16 int rmax = INT_MIN;
17 for(int i = mid + 1; i <= r; i++){
18 sum += a[i];
19 rmax = max(rmax, sum);
20 }
21
22 return max({left, right, lmax + rmax});
23 }
```
- $O(n^2)$
- $O(nlogn)$
- $O(logn)$
- $O(n)$
**第 12 题** 游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。$A$ 组: `A ={12,35,67,89}`，$B$ 组: `B ={20，45,55,78}`，下面是归并合并函数的核心循环，横线处应填入 ( )
```cpp
01 int i = 0, j = 0;
02 vector result;
03
04 while (i < A.size() && j < B.size()) {
05 if (___________________) {
06 result.push_back(A[i++]);
07 } else {
08 result.push_back(B[j++]);
09 }
10 }
11
12 while (i < A.size()) {
13 result.push_back(A[i++]);
14 }
15
16 while (j < B.size()) {
17 result.push_back(B[j++]);
18 }
```
- `A[i]>= B[j]`
- `A[i]<= B[j]`
- `i>=j`
- `i<=j`
**第 13 题** 有 $n$ 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 `pivot` 的快速排序，请问此次排序的时间复杂度是 ( )
```cpp
01 void quicksort(vector& a, int l, int r) {
02 if (l >= r) return;
03 int pivot = a[l];
04 int i = l, j = r;
05 while (i < j) {
06 while (i < j && a[j] >= pivot) j--;
07 while (i < j && a[i] <= pivot) i++;
08 if (i < j) swap(a[i], a[j]);
09 }
10 swap(a[l], a[i]);
11 quicksort(a, l, i - 1);
12 quicksort(a, i + 1, r);
13 }
```
- $O(n)$
- $O(nlogn)$
- $O(n^2)$
- $O(logn)$
**第 14 题** 下面关于排序算法的描述中，不正确的是 ( )
- 冒泡排序和插入排序都是稳定的排序算法
- 快速排序和归并排序都是不稳定的排序算法
- 冒泡排序和插入排序最好时间复杂度均为$O(n)$
- 归并排序在最好、最坏和平均三种情况的时间复杂度均为 $O(nlogn)$
**第 15 题** 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 `int` 表
示，则横线处应该填写 ( )
```cpp
01 int main(){
02 string s;
03 int b;
04 cin >> s >> b;
05
06 vector a;
07 for(char c : s){
08 a.push_back(c - '0');
09 }
10
11 vector c;
12 long long rem = 0;
13
14 for(int i = 0; i < a.size(); i++){
15 rem = rem * 10 + a[i];
16 int q = rem / b;
17 c.push_back(q);
18 ______________________
19 }
20
21 int pos = 0;
22 while(pos < c.size() - 1 && c[pos] == 0) pos++;
23
24 for(int i = pos; i < c.size(); i++){
25 cout << c[i];
26 }
27
28 cout << endl;
29 cout << rem << endl;
30 return 0;
31 }
```
- ```cpp
01 rem /= b;
```
- ```cpp
01 rem %= b;
```
- ```cpp
01 rem = b;
```
- ```cpp
01 rem = q;
```
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 有一个存储了 $n$ 个整数的线性表，分别用数组和单链表两种方式实现。在已知下标(或结点指针)的前提下，数组的随机访问是 $O(1)$，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 $O(1)$。
- 正确
- 错误
**第 2 题** 若数组 `a` 已按升序排列，则下面代码可以正确实现“在 `a` 中查找第一个大于等于 `x` 的元素的位置”。
```cpp
01 int lowerBound(vector& a,int x){
02 int l=0, r=a.size();
03 while(l < r) {
04 int mid = (l + r) / 2;
05 if( a[mid] >= x) r = mid;
06 else l = mid + 1;
07 }
08 return l;
09 }
```
- 正确
- 错误
**第 3 题** 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。
- 正确
- 错误
**第 4 题** 若某算法满足递推式: $T(n)=2T(n/2)+O(n)$，则其时间复杂度为$O(nlogn)$。
- 正确
- 错误
**第 5 题** 在一个数组中，如果两个元素`a[i]` 和 `a[j]` 满足 `ia[j]`，则 `a[i]` 和 `a[j]` 是一个逆序对。下面代码可以正确统计数组 `a` 区间 `[,r]` 内的逆序对总数。
```cpp
01 long long cnt=0;
02 void merge_count(vector& a, int l, int m, int r){
03 int i = l, j = m + 1;
04 while(i <= m && j <= r) {
05 if(a[i] <= a[j]) i++;
06 else {
07 cnt += (m - i+ 1);
08 j++;
09 }
10 }
11 }
```
- 正确
- 错误
**第 6 题** 根据唯一分解定理，如果大于$1$ 的整数不能被任何不超其平方根的质数整除，那么 $n$ 必定是质数。
- 正确
- 错误
**第 7 题** 假设数组 $a$ 的值域范围是$D$，以下程序的时间复杂度是$O(nlogn+nlogD)$。
```cpp
01 bool check(int n, int a[], int k, int dist) {
02 int cnt = 1;
03 int last = a[0];
04
05 for (int i = 1; i < n; i++) {
06 if (a[i] - last >= dist) {
07 cnt++;
08 last = a[i];
09 }
10 }
11
12 return cnt >= k;
13 }
14
15 int solve(int n, int a[], int k) {
16 std::sort(a, a + n);
17
18 int l = 0;
19 int r = a[n - 1] - a[0];
20
21 while (l < r) {
22 int mid = (l + r + 1) / 22
23
24 if (check(n, a, k, mid))
25 l = mid;
26 else
27 r = mid - 1;
28 }
29
30 return l;
31 }
32
33 int main() {
34 int a[] = {1, 2, 8, 4, 9};
35 int n = 5;
36 int k = 3;
37
38 std::cout << solve(n, a, k) << std::endl;
39
40 return 0;
41 }
```
- 正确
- 错误
**第 8 题** 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。
- 正确
- 错误
**第 9 题** 线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记，线性筛通过”每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度
- 正确
- 错误
**第 10 题** 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。
- 正确
- 错误