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

$1、$ 与数组相比，链表在（ ）操作上通常具有更高的效率。 {{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

$2、$ 下列 C++ 代码实现双向链表，函数 is_empty() 判断链表是否为空，如链表为空返回 true，否则返回 false。横线处不能填写（ ）。

01 // 节点结构体
02 struct Node {
03     int data;
04     Node* prev;
05     Node* next;
06 };
07 // 双向链表结构体
08 struct DoubleLink {
09     Node* head;
10     Node* tail;
11     int size;
12     DoubleLink() {
13         head = nullptr;
14         tail = nullptr;
15         size = 0;
16     }
17     ~DoubleLink() {
18         Node* curr = head;
19         while (curr) {
20             Node* next = curr->next;
21             delete curr;
22             curr = next;
23         }
24     }
25     // 判断链表是否为空
26     bool is_empty() const {
27         _______________________
28     }
29 };

{{ select(2) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

$3、$ 基于上题代码，在 append() 用于在双向链表尾部增加新节点。横线上应填写（ ）。

01 void append(int data) {
02     Node* newNode = new Node{data, nullptr, nullptr};
03     if (is_empty()) {
04         head = tail = newNode;
05     } else {
06         _________
07     }
08     ++size;
09 }

{{ select(3) }}

• tail->next = newNode;
• newNode->prev = tail; tail = newNode;
• tail = newNode; newNode->prev = tail; tail->next = newNode;
• tail->next = newNode; newNode->prev = tail; tail = newNode;

$4、$ 下列 C++ 代码用循环链表解决约瑟夫问题，横线上应填写（ ）。

01 struct Node {
02     int data;
03     Node* next;
04 };
05 Node* createCircularList(int n) {
06     Node* head = new Node{1, nullptr};
07     Node* prev = head;
08     for (int i = 2; i <= n; ++i) {
09         Node* node = new Node{i, nullptr};
10         prev->next = node; prev = node;
11     }
12     prev->next = head;
13     return head;
14 }
15 int fingLastSurvival(int n, int k) {
16     Node* head = createCircularList(n);
17     Node* p = head;
18     Node* prev = nullptr;
19     while (p->next != p) {
20         for (int count = 1; count < k; ++count) {
21             prev = p;
22             p = p->next;
23         }
24         prev->next = p->next;  // ----------------------
25         delete p;
26         p = prev->next;
27     }
28     cout << "最后留下的人编号是: " << p->data << endl;
29     delete p;
30     return 0;
31 }

{{ select(4) }}

• prev->next = p->next; delete p; p = prev->next;
• delete p; prev->next = p->next; p = prev->next;
• delete p; p = prev->next; prev->next = p->next;
• prev->next = p->next; p = prev->next; delete p;

$5、$ 下列 C++ 代码判断一个正整数是否是质数，说法正确的是（ ）。

01 bool is_prime(int n) {
02     if (n <= 1)
03         return false;
04     if (n == 2 || n == 3 || n == 5)
05         return true;
06     if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
07         return false;
08     int i = 7;
09     int step = 4;
10     int finish_number = sqrt(n) + 1;
11     while (i <= finish_number) {
12         if (n % i == 0)
13             return false;
14         i += step;
15         step = 6 - step;
16     }
17     return true;
}

{{ select(5) }}

• 代码存在错误，例如5是质数，但因为5 % 5余数是0返回了 false
• finish_number 的值应该是 n / 2
• 当前 while 循环正确的前提是：所有大于3的质数都符合 6k±1 形式
• while 循环修改如下，其执行效果和执行时间相同。

01 for (int i = 2; i < finish_number; i++) {
02     if (n % i == 0)
03         return false;
04 }
05 return true;

$6、$ 下列 C++ 代码用两种方式求解最大公约数，说法错误的是（ ）。

01 int gcd0(int big, int small) {
02     if (big < small) {
03         swap(big, small);
04     }
05     if (big % small == 0) {
06         return small;
07     }
08     return gcd0(small, big % small);
09 }
10 int gcd1(int big, int small) {
11     if (big < small) {
12         swap(big, small);
13     }
14     for (int i = small; i >= 1; --i) {
15         if (big % i == 0 && small % i == 0)
16             return i;
17     }
18     return 1;
19 }

{{ select(6) }}

• gcd0() 的时间复杂度为 $O(log n)$
• gcd1() 的时间复杂度为 $O(n)$
• 一般而言，gcd0() 的效率高于 gcd1()
• gcd1() 中循环应改为 for (int i = small; i > 1; --i)

$7、$ 下列判断整数 n 是否是质数的代码，说法错误的是（ ）。

01 bool is_prime(int n) {
02     if (n <= 1) return false;
03     int finish_number = static_cast<int>(sqrt(n)) + 1;
04     for (int i = 2; i < finish_number; ++i) {
05         if (n % i == 0)
06             return false;
07     }
08     return true;
09 }

{{ select(7) }}

• 埃氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

$8、$ 唯一分解定理描述了关于正整数的什么性质？（） {{ select(8) }}

• 任何正整数都可以表示为两个素数的和
• 任何大于1的合数都可以唯一分解为有限个质数的乘积。
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
• 所有素数都是奇数

$9、$ 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

01 int find_max_recursive(const vector<int>& nums, int left, int right) {
02     if (left == right)
03         return nums[left];
04     int mid = left + (right - left) / 2;
05     int left_max = find_max_recursive(nums, left, mid);
06     int right_max = find_max_recursive(nums, mid + 1, right);
07     return max(left_max, right_max);
08 }
09 int find_max(const vector<int>& nums) {
10     if (nums.empty()) {
11         throw invalid_argument("输入数组不能为空");
12     }
13     return find_max_recursive(nums, 0, nums.size() - 1);
14 }

{{ select(9) }}

• 该算法采用分治
• 该算法是递归实现
• 该算法采用贪心
• 该算法不是递推算法

$10、$ 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

01 int find_max(const vector<int>& nums) {
02     if (nums.empty()) {
03         throw invalid_argument("输入数组不能为空");
04     }
05     int max_value = nums[0];
06     for (int num : nums) {
07         if (num > max_value) {
08             max_value = num;
09         }
10     }
11     return max_value;
12 }

{{ select(10) }}

• 本题采用迭代算法
• 时间复杂度为 $O(n)$
• 和上一题的 find_max() 相比，因为没有递归，所以没有栈的创建和销毁开销
• 本题 find_max() 函数和上一题的 find_max() 时间复杂度相同

$11、$ 下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法，正确的是（ ）。

01 int binary_search_last_occurrence(const vector<int>& lst, int target) {
02     if (lst.empty()) return -1;
03     int low = 0, high = lst.size() - 1;
04     while (low < high) {
05         int mid = (low + high + 1) / 2;
06         if (lst[mid] <= target) {
07             low = mid;
08         } else {
09             high = mid - 1;
10         }
11     }
12     if (lst[low] == target)
13         return low;
14     else
15         return -1;
16 }

{{ select(11) }}

• 当 lst 中存在重复的 target 时，该函数总能返回最后一个 target 的位置，即便 lst 全由相同元素组成
• 当 target 小于 lst 中所有元素时，该函数会返回 0
• 循环条件改为 while (low <= high) 程序执行效果相同，且能提高准确性
• 将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同

$12、$ 有关下面C++代码的说法，错误的是（ ）。

01 double sqrt_binary(long long n, double epsilon = 1e-10) {
02     if (n < 0) {
03         throw invalid_argument("输入必须为非负整数");
04     }
05     if (n == 0 || n == 1) return n;
06     // 阶段 1
07     long long low = 1, high = n;
08     long long k = 0;
09     while (low <= high) {
10         long long mid = (low + high) / 2;
11         long long mid_sq = mid * mid;
12         if (mid_sq == n) {
13             return mid;
14         } else if (mid_sq < n) {
15             k = mid;
16             low = mid + 1;
17         } else {
18             high = mid - 1;
19         }
20     }
21     long long next_k = k + 1;
22     if (next_k * next_k == n) {
23         return next_k;
24     }
25     // 阶段 2
26     double low_d = (double)k;
27     double high_d = (double)(k + 1);
28     double mid;
29     while (high_d - low_d >= epsilon) {
30         mid = (low_d + high_d) / 2;
31         double mid_sq = mid * mid;
32

{{ select(12) }}

• “阶段1”的目标是寻找正整数 n 可能的正完全平方根
• “阶段2”的目标是如果正整数 n 没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
• 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

$13、$ 硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。 mount 为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（ ）

01 const int MAX_COINS = 10;
02 int result[MAX_COINS] = {0}; // 假设最多10种面额
03 int find_coins(const vector<int>& coins, int amount) {
04     sort(coins.begin(), coins.end(), greater<int>());
05     int n = coins.size();
06     for (int i = 0; i < n; ++i) {
07         int coin = coins[i];
08         int num = amount / coin;
09         result[i] = num;
10         amount -= num * coin;
11         if (amount == 0) break;
12     }
13     cout << "找零方案如下：" << endl;
14     for (int i = 0; i < n; ++i) {
15         cout << coins[i] << "角需要" << result[i] << "枚" << endl;
16     }
17     return 0;
18 }

{{ select(13) }}

• 上述代码采用贪心算法
• 针对本题具体要求，上述代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

$14、$ 关于下述C++代码的快速排序算法，说法错误的是（ ）。

01 int randomPartition(std::vector<int>& arr, int low, int high) {
02     int random = low + rand() % (high - low + 1);
03     std::swap(arr[random], arr[high]);
04     int pivot = arr[high];
05     int i = low - 1;
06     for (int j = low; j < high; j++) {
07         if (arr[j] <= pivot) {
08             i++;
09             std::swap(arr[i], arr[j]);
10         }
11     }
12     std::swap(arr[i + 1], arr[high]);
13     return i + 1;
14 }
15 void quickSort(std::vector<int>& arr, int low, int high) {
16     if (low < high) {
17         int pi = randomPartition(arr, low, high);
18         quickSort(arr, low, pi - 1);
19         quickSort(arr, pi + 1, high);
20     }
21 }

{{ select(14) }}

• 在 randomPartition 函数中，变量 i 的作用是记录大于基准值的元素的边界
• randomPartition 函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度$O(n^2)$
• 快速排序平均时间复杂度是 $O(n log n)$
• 快速排序是稳定排序

$15、$ 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（ ）。

01 const int MAXN = 1005; // 最大位数
02 struct BigInt {
03     int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
04     int len; // 数字长度
05     BigInt() {
06         memset(d, 0, sizeof(d));
07         len = 0;
08     }
09 };
10 // 比较两个高精度数的大小
11 int compare(BigInt a, BigInt b) {
12     if (a.len != b.len) return a.len > b.len ? 1 : -1;
13     for (int i = a.len - 1; i >= 0; i--) {
14         if (a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
15     }
16     return 0;
17 }
18 // 高精度减法
19 BigInt sub(BigInt a, BigInt b) {
20     BigInt c;
21     for (int i = 0; i < a.len; i++) {
22         c.d[i] += a.d[i] - b.d[i];
23         if (c.d[i] < 0) {
24             c.d[i] += 10;
25             c.d[i+1]--;
26         }
27     }
28     c.len = a.len;
29     while (c.len > 1 && c.d[c.len-1] == 0) c.len--;
30     return c;
31 }
32 // 高精度除法（a/b，返回商和余数）
33 pair<BigInt, BigInt> div(BigInt a, BigInt b) {
34     BigInt q, r; // q是商，r是余数
35     if (compare(a, b) < 0) { // 如果a<b，商为0，余数为a
36         q.len = 1;
37         q.d[0] = 0;
38         r = a;
39         return make_pair(q, r);
40     }
41     // 初始化余数r为a的前b.len位
42     r.len = b.len;
43     for (int i = a.len - 1; i >= a.len - b.len; i--) {
44         r.d[i - (a.len - b.len)] = a.d[i];
45     }
46     // 逐位计算商
47     for (int i = a.len - b.len; i >= 0; i--) {
48         // 把下一位加入余数
49         if (r.len > 1 || r.d[0] != 0) {
50             for (int j = r.len; j > 0; j--) {
51                 r.d[j] = r.d[j-1];
52             }
53             _______________________
54         } else {
55             r.d[0] = a.d[i];
56             r.len = 1;
57         }
58         // 计算当前位的商
59         while (compare(r, b) >= 0) {
60             r = sub(r, b);
61             q.d[i]++;
62         }
63     }
64     // 确定商的长度
65     q.len = a.len - b.len + 1;
66     while (q.len > 1 && q.d[q.len-1] == 0) q.len--;
67     // 处理余数前导零
68     while (r.len > 1 && r.d[r.len-1] == 0) r.len--;
69     return make_pair(q, r);
70 }

{{ select(15) }}

• r.d[0] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len = 1;
• r.d[0] = a.d[i]; r.len = 1;

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

$16、$ 下列 C++ 代码用欧几里得算法求最大公约数，gcd(a,b) 对于任意 a,b 都适用。（）

01 int gcd(int a, int b) {
02     while (b) {
03         int temp = b;
04         b = a % b;
05         a = temp;
06     }
07     return a;
08 }

{{ select(16) }}

• 正确
• 错误

$17、$ 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。（）

01 int lcm(int a, int b) {
02     return a * b / gcd(a, b);
03 }

{{ select(17) }}

• 正确
• 错误

$18、$ 下面的C++代码用于输出每个数对应的质因数列表，输出形如： {5: [5], 6: [2, 3], 7: [7], 8: [2, 2,2]} 。

01 int main() {
02     int n, m;
03     cin >> n >> m;
04     if (n > m) swap(n, m);
05     map<int, vector<int>> prime_factor;
06     for (int i = n; i <= m; ++i) {
07         int j = 2, k = i;
08         while (k != 1) {
09             if (k % j == 0) {
10                 prime_factor[i] = prime_factor[i] + j;
11                 k /= j;
12             } else {
13                 ++j;
14             }
15         }
16     }
17     for (auto& p : prime_factor) {
18         cout << p.first << ": ";
19         for (int v : p.second)
20             cout << v << " ";
21         cout << endl;
22     }
23     return 0;
24 }

{{ select(18) }}

• 正确
• 错误

$19、$ 下面的C++代码实现归并排序。代码在执行时，将输出一次 HERE 字符串，因为merge()函数仅被调用一次。

01 void merge(std::vector<int>& arr, int left, int mid, int right) {
02     std::vector<int> temp(right - left + 1);
03     int i = left;
04     int j = mid + 1;
05     int k = 0;
06     while (i <= mid && j <= right) {
07         if (arr[i] <= arr[j]) {
08             temp[k++] = arr[i++];
09         } else {
10             temp[k++] = arr[j++];
11         }
12     }
13     while (i <= mid) {
14         temp[k++] = arr[i++];
15     }
16     while (j <= right) {
17         temp[k++] = arr[j++];
18     }
19     for (int p = 0; p < k; ++p) {
20         arr[left + p] = temp[p];
21     }
22 }
23 void mergeSort(std::vector<int>& arr, int left, int right) {
24     if (left >= right) {
25         return;
26     }
27     int mid = left + (right - left) / 2;
28     mergeSort(arr, left, mid);
29     mergeSort(arr, mid + 1, right);
30     std::cout << "HERE";
31     merge(arr, left, mid, right);
32 }

{{ select(19) }}

• 正确
• 错误

$20、$ 归并排序的最好、最坏和平均时间复杂度均为 $O(n log n)$。（） {{ select(20) }}

• 正确
• 错误

$21、$ 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 g 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 m ，由于字母表中 g 位于 m 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为 g 的页码。这种查字典的一系列操作可看作二分查找。 {{ select(21) }}

• 正确
• 错误

$22、$ 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。

{{ select(22) }}

• 正确
• 错误

$23、$分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

{{ select(23) }}

• 正确
• 错误

$24、$ 函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。

01 int puzzle(int n) {
02     if (n == 1) return 1;
03     if (n % 2 == 0) return puzzle(n / 2);
04     return puzzle(3 * n + 1);
05 }

{{ select(24) }}

• 正确
• 错误

$25、$如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。

01 vector<int> linearSieve(int n) {
02     vector<bool> is_prime(n + 1, true);
03     vector<int> primes;
04     for (int i = 2; i <= n; ++i) {
05         if (is_prime[i]) {
06             primes.push_back(i);
07         }
08         for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
09             is_prime[i * primes[j

{{ select(25) }}

• 正确
• 错误