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

第 1 题 关于单链表､双链表和循环链表,下列说法正确的是( )｡ {{ select(1) }}

• 在单链表中,若已知任意结点的指针,则可以在 $O(1)$ 时间内删除该结点｡
• 循环链表中一定不存在空指针｡
• 在循环双链表中,尾结点的next 指针一定为nullptr ｡
• 在带头结点的循环单链表中,判定链表是否为空只需判断头结点的 next 是否指向自身｡

---

第 2 题 双向循环链表中要在结点 p 之前插入新结点 s (均非空),以下指针操作正确的是( )｡

{{ select(2) }}

• 1 s -> next = p;
  2 p -> prev = s;
  3 p -> next = s;
  4 s -> prev = p;
  

• 1 s -> prev = p;
  2 s -> next = p -> next; 
  3 p -> next -> prev = s; 
  4 p -> next = s;
  

• 1 s -> prev = p->prev;
  2 s -> next = p; 
  3 p -> prev -> next = s;
  4 p -> prev = s;
  

• 1 s -> prev = nullptr;
  2 s -> next = p; 
  3 p -> prev = s;
  

---

第 3 题 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点｡横线处应填( )｡

1 struct Node{
2     int val;
3     Node* next;
4     Node(int v):val(v),next(nullptr){}
5 };
6 Node* eraseAll(Node* head, int x){
7     Node dummy(0);
8     dummy.next = head;
9     Node* cur = &dummy;
10     while(cur->next){
11         if(cur->next->val == x){
12             Node* del = cur->next;
13             _______________ //在此处填入代码
14             delete del;
15         } else 
16             cur = cur->next;
17     }
18     return dummy.next;
19 }

{{ select(3) }}

• cur = cur->next;
• cur->next = del->next;
• del->next = cur->next;
• cur->next = nullptr;

---

第 4 题 对如下代码实现的欧几里得算法(辗转相除法),执行 gcd(48, 18) 得到的调用序列为( )｡

1 int gcd(int a, int b) {
2     return b == 0 ? a : gcd(b, a % b);
3 }

{{ select(4) }}

• gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
• gcd(48,18) -> gcd(30,18) -> gcd(12,18)
• gcd(48,18) -> gcd(18,30) -> gcd(30,6)
• gcd(48,18) -> gcd(12,18) -> gcd(6,12)

---

第 5 题 下面代码实现了欧拉(线性)筛,横线处应填写( )｡

1 vector<int> euler_sieve(int n) {
2     vector<bool> is_composite(n + 1, false); 
3     vector<int> primes;
4     for (int i = 2; i <= n; i++) {
5         if (!is_composite[i]) primes.push_back(i);
6         for (int j = 0; _______________ //在此处填入代码
7             && (long long)i * primes[j] <= n; j++) {
8             is_composite[i * primes[j]] = true;
9             if (i % primes[j] == 0)
10                 break;
11         }
12     }
13     return primes;
14 }

{{ select(5) }}

• j <= n
• j < sqrt(n)
• j < primes.size()
• j < i

---

第 6 题 埃氏筛中将内层循环从 j = ii 开始而不是 j = 2i 的主要原因是( )｡

1 vector<int> eratosthenes_sieve(int n) {
2     vector<bool> is_composite(n + 1, false);
3     vector<int> primes;
4     for (int i = 2; i <= n; i++) {
5         if (is_composite[i]) continue;
6         primes.push_back(i);
7         for (long long j = (long long)i * i; j <= n; j += i)
8             is_composite[j] = true;
9     }
10     return primes;
11 }

{{ select(6) }}

• 因为 2*i 一定不是合数
• i*i 一定是质数
• 小于 i*i 的 i 的倍数已被更小质因子筛过
• 这样可以把时间复杂度降为 $O(n)$

---

第 7 题 下面程序的运行结果为( )｡

1 bool check(int n,int a[],int k,int dist) {
2     int cnt=1;
3     int last = a[0];
4     for (int i=1;i<n;i++) {
5         if (a[i] - last >= dist) {
6             cnt++;
7             last = a[i];
8         }
9     }
10     return cnt>=k;
11 }
12 int solve(int n,int a[],int k) {
13     std::sort(a,a + n);
14     int l=0;
15     int r= a[n -1]-a[0];
16     while (l <r) {
17         int mid = (l+ r+1)/ 2;
18         if (check(n, a, k,mid))
19             l=mid;
20         else
21             r=mid-1;
22     }
23     return l;
24 }
25 int main(){
26     int n=5;
27     int k=3;
28     int a[] = {1, 2, 8, 4, 9};
29     std::cout << solve(n, a, k) << std::endl;
30     return 0;
31 }

{{ select(7) }}

• 2
• 3
• 4
• 5

---

第 8 题 在升序数组中查找第一个大于等于x的位置,下面循环中横线应填()。

1 int lowerBound(const vector<int>& a,int x){
2     int l=0,r=a.size();
3     while(l<r){
4         int mid = l+(r-l)/2;
5         if(a[mid]>=x)
6             _______________ //在此处填入代码
7         else 
8             l =mid+1;
9     }
10     return l;
11 }

{{ select(8) }}

• r = mid;
• r = mid -1;
• l = mid;
• l =mid+1 ;

---

第 9 题 关于递归函数调用,下列说法错误的是( )｡ {{ select(9) }}

• 递归调用层次过深时,可能会耗尽栈空间导致栈溢出
• 尾递归函数可以通过编译器优化来避免栈溢出
• 所有递归函数都可以通过循环结构来改写,从而避免栈溢出
• 栈溢出发生时,程序会抛出异常并可以继续执行后续代码

---

第 10 题 给定 n 根木头,第 i 根长度为 a[i] ｡要切成不少于 m 段等长木段,求最大可能长度,则横线上应填写( )｡

1 const int MAXN = 100005;
2 long long a[MAXN];
3 int n, m;
4 bool check(long long x){
5     long long cnt = 0;
6     for(int i = 1; i <= n; i++){
7         if(x == 0) return true;
8         cnt += a[i] / x;
9         if(cnt >= m) return true;
10     }
11     return false;
12 }
13 int main(){
14     cin >> n >> m;
15     long long mx = 0;
16     for(int i = 1; i <= n; i++){
17         cin >> a[i];
18         mx = max(mx, a[i]);
19     }
20     long long l = 1, r = mx;
21     long long ans = 0;
22     while(l <= r){
23         long long mid = l + (r - l) / 2;
24         if(check(mid)){
25             ans = mid;
26             _______________ //在此处填入代码
27         } else {
28             _______________ //在此处填入代码
29         }
30     }
31     cout << ans << endl;
32     return 0;
33 }

{{ select(10) }}

1 l = mid + 1;
2 r = mid - 1;

• 1 l = mid - 1;
  2 r = mid + 1;
  

• 1 l = mid + 1;
  2 r = mid;
  

• 1 l = mid;
  2 r = mid + 1;
  

---

第 11 题 下面代码用分治求“最大连续子段和”,其时间复杂度为( )｡

1 int solve(vector<int>& a, int l, int r){
2     if(l == r) return a[l];
3     int mid = l + (r - l) / 2;
4     int left = solve(a, l, mid);
5     int right = solve(a, mid + 1, r);
6     int sum = 0, lmax = INT_MIN;
7     for(int i = mid; i >= l; i--){
8         sum += a[i];
9         lmax = max(lmax, sum);
10     }
11     sum = 0;
12     int rmax = INT_MIN;
13     for(int i = mid + 1; i <= r; i++){
14         sum += a[i];
15         rmax = max(rmax, sum);
16     }
17     return max({left, right, lmax + rmax});
18 }

{{ select(11) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(\log n)$

---

第 12 题 游戏大赛决赛,两组选手分别按得分从小到大排好队,现在要把他们合并成一个有序排行榜｡A组: $A={12,35,67,89}$ ,B组: $B={20,45,55,78}$ ,下面是归并合并函数的核心循环,横线处应填入( )｡

1 int i = 0, j = 0;
2 vector<int> result;
3 while (i < A.size() && j < B.size()) {
4     if (_______________ //在此处填入代码
5     ) {
6         result.push_back(A[i++]);
7     } else {
8         result.push_back(B[j++]);
9     }
10 }
11 while (i < A.size()) {
12     result.push_back(A[i++]);
13 }
14 while (j < B.size()) {
15     result.push_back(B[j++]);
16 }

{{ select(12) }}

• A[i] >= B[j]
• A[i] <= B[j]
• i >= j
• i <= j

---

第 13 题 有 n 位同学的成绩已经从小到大排好序,现在对它执行下面这段以第一个元素为 pivot 的快速排序,请问此次排序的时间复杂度是( )｡

1 void quicksort(vector<int>& a, int l, int r) {
2     if (l >= r) return;
3     int pivot = a[l];
4     int i = l, j = r;
5     while (i < j) {
6         while (i < j && a[j] >= pivot) j--;
7         while (i < j && a[i] <= pivot) i++;
8         if (i < j) swap(a[i], a[j]);
9     }
10     swap(a[l], a[i]);
11     quicksort(a, l, i - 1);
12     quicksort(a, i + 1, r);
13 }

{{ select(13) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(\log n)$

---

第 14 题 下面关于排序算法的描述中,不正确的是( )｡ {{ select(14) }}

• 冒泡排序和插入排序都是稳定的排序算法
• 快速排序和归并排序都是不稳定的排序算法
• 冒泡排序和插入排序最好时间复杂度均为 $O(n)$
• 归并排序在最好､最坏和平均三种情况的时间复杂度均为 $O(n \log n)$

---

第 15 题 下面代码实现两个整数除法,其中被除数为一个“大整数”,用字符串表示,除数是一个小整数,用int表示,则横线处应该填写( )｡

1 int main(){
2     string s;
3     int b;
4     cin >> s >> b;
5     vector<int> a;
6     for(char c : s){
7         a.push_back(c - '0');
8     }
9     vector<int> c;
10     long long rem = 0;
11     for(int i = 0; i < a.size(); i++){
12         rem = rem * 10 + a[i];
13         int q = rem / b;
14         c.push_back(q);
15         _______________ //在此处填入代码
16     }
17     int pos = 0;
18     while(pos < c.size() - 1 && c[pos] == 0) pos++;
19     for(int i = pos; i < c.size(); i++){
20         cout << c[i];
21     }
22     cout << endl;
23     cout << rem << endl;
24     return 0;
25 }

{{ select(15) }}

• rem /= b;
• rem %= b;
• rem = b;
• rem = q;

---