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

第 1 题 小杨用单链表保存任务序列，并同时维护头指针 head 和尾指针 tail。在链表非空且已知 tail 的情况下，在表尾插入新结点的时间复杂度是（）。

1   struct Node {
2   	int value;
3   	Node *next;
4   };
5   Node *head;
6   Node *tail;

{{ select(1) }}

• $O(1)$
• $O(logn)$
• $O(n)$
• $O(nlogn)$

第 2 题 在不带哨兵结点的双向链表中，结点 p 既不是头结点也不是尾结点。删除 p 的正确代码是（）。

1   struct Node {
2       int value;
3       Node *prev;
4       Node *next;
5   };

{{ select(2) }}

• 1   p->prev = p->next;
  2   p->next = p->prev;
  3   delete p;
  

• 1   p->prev->next = p;
  2   p->next->prev = p;
  3   delete p;
  

• 1   p->prev->next = p->next;
  2   p->next->prev = p->prev;
  3   delete p;
  

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

第 3 题 下面函数使用快慢指针查找单链表的中间结点。横线处应填写（）。

1   struct Node {
2   	int value;
3   	Node *next;
4   };
5
6   Node *middle(Node *head) {
7   	Node *slow = head;
8   	Node *fast = head;
9   	while (fast != nullptr && fast->next != nullptr) {
10  		slow = slow->next;
11          _______  
12  }
13  	return slow;
14  }

{{ select(3) }}

• fast = fast->next;
• fast = fast->next->next;
• fast = slow->next;
• fast = head->next;

第 4 题 函数gcd(int a, int b) 定义如下，则gcd(105, 45) 的结果是（）。

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

{{ select(4) }}

• 3
• 5
• 15
• 45

第 5 题 下面函数用于判断正整数 n 是否为质数。横线处的最佳写法是（）。

1   bool isPrime(int n) {
2   	if (n < 2)
3   		return false;
4   	for (int i = 2; _____; i++) {
5   		if (n % i == 0)
6   			return false;
7   	}
8   	return true;
9   }

{{ select(5) }}

• i < n
• i <= n / 2
• i * i < n
• (long long) i * i <= n

第 6 题 下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（）。

1   vector<int> linearSieve(int n) {
2   	vector<bool> composite(n + 1, false);
3   	vector<int> primes;
4
5   	for (int i = 2; i <= n; i++) {
6   		if (!composite[i])
7   			primes.push_back(i);
8   		for (int p : primes) {
9   			if ((long long)i * p > n)
10   				break;
11  			composite[i * p] = true;
12  			if (_______)
13  				break;
14  		}
15  	}
16  	return primes;
17  }

{{ select(6) }}

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

第 7 题 根据唯一分解定理，整数 $756$ 的正确质因数分解是（）。

{{ select(7) }}

• $2^2 \times 3^3 \times 7$
• $2^3 \times 3^3 \times 7$
• $2^2 \times 3^2 \times 21$
• $2 \times 3^3 \times 14$

第 8 题 函数f(int n) 定义如下，则f(4) 的结果是（）。

1   int f(int n) {
2   	if (n == 1)
3   		return 1;
4   	return n + f(n - 1);
5   }

{{ select(8) }}

• 4
• 7
• 9
• 10

第 9 题 在升序数组中查找第一个严格大于 x 的元素位置，下面代码中的横线应填写（）。

1   int upperBound(const vector<int> &a, int x) {
2   	int l = 0, r = (int)a.size();
3   	while (l < r) {
4   		int mid = l + (r - l) / 2;
5   		if (                 ) {
6   			l = mid + 1;
7   		} else {
8   			r = mid;
9   		}
10  	}
11  	return l;
12  }

{{ select(9) }}

• a[mid] < x
• a[mid] >= x
• a[mid] <= x
• a[mid] > x

第 10 题 小杨需要把若干箱货物按原顺序分配到 days 天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数 check(cap) 判断载重量为 cap 时能否在规定天数内运完。横线处应填写（）。

1   long long l = maxWeight;
2   long long r = totalWeight;
3
4   while (l < r) {
5	long long mid = l + (r - l) / 2;
6	    if (check(mid)) {
7           _______
8	    } else {
9           _______
10	    }
11  }
12  cout << l;

{{ select(10) }}

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

第 11 题 下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（）。

1   while (i <= mid && j <= right) {
2   	if (______) {
3   		temp.push_back(a[i++]);
4   	} else {
5   		temp.push_back(a[j++]);
6   	}
7   }

{{ select(11) }}

• a [i] < a [j]
• a [i] > a [j]
• a [i] >= a [j]
• a [i] <= a [j]

第 12 题 下面快速排序的划分函数以a[right] 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（）。

1   int partition(int a[], int left , int right) {
2   	int pivot = a[right];
3   	int i = left - 1;
4   	for (int j = left; j < right; j++) {
5   		if (______) {
6   			i++;
7   			swap(a[i], a [j]);
8   		}
9   	}
10  	swap(a[i + 1], a[right]);
11  	return i + 1;
12  }

{{ select(12) }}

• a[j] <= pivot
• a[j] > pivot
• a[i] <= pivot
• a[right] < a [j]

第 13 题 小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间 start 和结束时间 end 。采用贪心算法时，正确的选择策略是（）。

1   struct Activity {
2       int start;
3       int end;
4   };

{{ select(13) }}

• 每次选择开始时间最早的活动
• 每次选择持续时间最短的活动
• 每次选择参与人数最少的活动
• 按结束时间从早到晚排序，依次选择与已选活动不冲突的活动

第 14 题 下面函数使用迭代方法求最大连续子段和。对于数组 {-2, 3, -1, 5, -6, 2 }，函数返回值是（）。

1   int maxSubArray(const vector<int> &a) {
2   	int best = a[0];
3   	int current = a[0];
4   	for (int i = 1; i < (int)a.size(); i++) {
5   		current = max(a[i], current + a [i]);
6   		best = max(best, current);
7   	}
8   	return best;
9   }

{{ select(14) }}

• 5
• 6
• 7
• 8

第 15 题 数组 a 和 b 按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（）。

1   vector<int> add(const vector<int> &a, const vector<int> &b) {
2   	vector<int> c;
3   	int carry = 0;
4   	int n = max (a.size(), b.size());
5   	
6     for (int i = 0; i < n; i++) {
7   		int sum = carry;
8   		if (i < a.size())
9   			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  }

{{ select(15) }}

• carry = sum % 10;
• carry = sum;
• carry = sum / 10;
• carry = c[i] / 10;

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

第 16 题 下面代码在已知结点 p 的情况下，能够以 $O(1)$ 的时间在单链表的 p 结点之后插入新结点 s 。

1   s->next = p->next;
2   p->next = s;

{{ select(16) }}

• 对
• 错

第 17 题 下面代码可以安全地删除单链表的头结点，并使 head 指向删除后的新头结点。

1   Node *p = head;
2   delete p;
3   head = p->next;

{{ select(17) }}

• 对
• 错

第 18 题 下面欧几里得算法既适用于 a > b，也适用于 a < b，只要 a、b 是正整数。

1   int gcd(int a , int b) {
2   	while (b != 0) {
3   		int r = a % b ;
4   		a = b ;
5   		b = r;
6   	}
7   	return a ;
8   }

{{ select(18) }}

• 对
• 错

第 19 题 下面埃氏筛从 i * i 开始标记，是因为 i * i 之前的 i 的合数倍数已经被更小的质因子标记过。

1   for (int i = 2; (long long)i * i <= n; i++) {
2   	if (isPrime [i]) {
3   		for (int j = i * i; j <= n; j += i) {
4   			isPrime [j] = false;
5   		}
6   	}
7   }

{{ select(19) }}

• 对
• 错

第 20 题 下面程序的时间复杂度为 $O(n)$。

1   for (int i = 1; i <= n; i *= 2) {
2   	cout << i << endl;
3   }

{{ select(20) }}

• 对
• 错

第 21 题 若数组 a 已按升序排列，下面函数能够返回最后一个小于等于 x 的元素下标；如果不存在，则返回 -1 。

1   int findLastLE(const vector<int> &a, int x) {
2   	int l = 0, r = (int)a.size() - 1;
3   	int ans = -1;
4   	while (l <= r) {
5   		int mid = l + (r - l) / 2;
6   		if (a[mid] <= x) {
7   			ans = mid;
8   			l = mid + 1;
9   		} else {
10  			r = mid - 1;
11  		}
12  	}
13  	return ans;
14  }

{{ select(21) }}

• 对
• 错

第 22 题 快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为$O(nlogn)$。

{{ select(22) }}

• 对
• 错

第 23 题 归并排序的递推式为 $T(n)=2T(n/2)+O(n)$，对应的时间复杂度为 $O(nlogn)$。

{{ select(23) }}

• 对
• 错

第 24 题 下面的贪心代码一定能对任意硬币面值集合 coins 求出 money 所需的最少硬币数。

1   int count = 0;
2   for (int coin : coins){ // coins 按面值从大到小排列
3   	count += money / coin;
4   	money %= coin;
5   }

{{ select(24) }}

• 对
• 错

第 25 题 假设两个非负高精度整数分别存储在数组 $a$ 和 $b$ 中，且 $a≥b$。数组采用低位在前的方式存储，即 $a[0]$ 表示个位。下面代码中的 $c$ 可以正确保存 $a - b$ 的各位数字。

1   int borrow = 0;
2   for (int i = 0; i < len; ++i) {
3   	int t = a[i] - b[i] + borrow;
4   	if (t < 0) {
5   		t += 10;
6   		borrow = 1;
7   	} else {
8   		borrow = 0;
9   	}
10  	c[i] = t;
11  }

{{ select(25) }}

• 对
• 错