GESP C++ 五级模拟卷2（循环链表、归并排序、分治算法、高精度计算、递归与迭代）
选 单选题（共 15 题，每题 2 分）
在循环链表中删除结点 p（p 不是唯一结点），以下代码横线处应填入（ ）
prev->next = p->next;
delete p;
______;
以下高精度加法代码中，横线处应填入（ ）
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
______;
carry /= 10;
}
if (carry) c.push_back(carry);
return c;
}
分治算法的基本思想是（ ）
快速排序中随机选择基准值（pivot）的主要目的是（ ）
以下关于递归与迭代的说法，正确的是（ ）
在双向链表头部插入新结点 t（head 为头哨兵），以下代码横线处应填入（ ）
t->next = head->next;
t->prev = head;
head->next->prev = t;
______;
以下二分查找的变体用于查找第一个大于等于 target 的位置（lower_bound），横线处应填入（ ）
int lower_bound(vector<int>& arr, int target) {
int l = 0, r = arr.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (______) r = mid;
else l = mid + 1;
}
return l;
}
标准 3 柱汉诺塔问题中，移动 n 个盘子所需的最少移动次数是（ ）
硬币找零问题中，面额为 {1, 5, 10, 25} 分，要找零 40 分。使用贪心策略，得到的硬币数是（ ）
高精度乘法中，两个位数分别为 m 和 n 的数相乘，结果最多有多少位？（ ）
以下归并排序的 merge 函数中，横线处应填入（ ）
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (______) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
递归函数 fib(n) 使用朴素递归计算斐波那契数，其时间复杂度是（ ）
循环链表中，要判断指针 p 是否遍历完整个链表回到起点，条件是（ ）
以下关于 GCD（最大公约数）的叙述，正确的是（ ）
分治算法解决"最大子数组和"问题时，需要计算跨越中点的最大和，这部分的复杂度是（ ）
判 判断题（共 10 题，每题 2 分）
在循环链表中，每个结点都有一个前驱结点和一个后继结点。（ ）
高精度加法的时间复杂度与两个数的位数之和成正比，即 O(n)。（ ）
分治算法的效率一定比直接求解原问题的效率高。（ ）
归并排序需要额外的 O(n) 空间来存放临时数组。（ ）
快速排序在任何输入情况下都能保证 O(n log n) 的时间复杂度。（ ）
理论上所有递归算法都可以转换为等价的迭代算法。（ ）
贪心算法在做出选择后，如果发现选择不是最优的，会回溯重新选择。（ ）
标准 3 柱汉诺塔问题中，移动 n 个盘子所需的最少步数为 2ⁿ − 1。（ ）
链表结点在内存中必须连续存放。（ ）
高精度乘法和除法的实现都涉及逐位相乘和进位处理，两者时间复杂度相同。（ ）
编 编程操作题（共 2 题，共 50 分）
试题名称：高精度加法
时间限制：1.0 s | 内存限制：512.0 MB
给定两个非负整数（可能非常大，位数不超过 200 位），求它们的和。
输入格式
两行，每行一个非负整数，位数不超过 200 位。
输出格式
一行，一个整数，表示两个数的和。不要输出前导零（除非结果为 0）。
样例输入 #1
12345678901234567890
98765432109876543210
样例输出 #1
111111111011111111100
试题名称：归并排序
时间限制：1.0 s | 内存限制：512.0 MB
给定 N 个整数，请使用归并排序将它们按升序排列后输出。
输入格式
第一行，一个正整数 N（1 ≤ N ≤ 100000）。
第二行，N 个整数，绝对值不超过 10⁹，数之间用空格分隔。
输出格式
一行，N 个整数，按升序排列，数之间用一个空格分隔。
样例输入 #1
5
3 1 4 1 5
样例输出 #1
1 1 3 4 5