GESP C++ 五级 模拟卷2
GESP C++ 五级模拟卷2（循环链表、归并排序、分治算法、高精度计算、递归与迭代）
// questions
题目预览
在循环链表中删除结点 p（p 不是唯一结点），以下代码横线处应填入（ ）
prev->next = p->next;
delete p;
______;
p = prev;
p = p->next;
prev = prev->next;
p = prev->next;
以下高精度加法代码中，横线处应填入（ ）
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;
}
c.push_back(carry % 10);
c.push_back(carry / 10);
c.push_back(carry); carry %= 10;
carry = carry % 10; c.push_back(carry);
分治算法的基本思想是（ ）
每一步选择当前最优解，逐步逼近全局最优解
将原问题分解为规模更小的子问题，分别求解后合并
通过穷举所有可能的解来寻找最优解
从初始状态出发，每次随机选择一个方向前进
快速排序中随机选择基准值（pivot）的主要目的是（ ）
保证排序是稳定的
减少额外空间的使用
避免最坏情况 O(n²) 的发生概率
使代码实现更简单
以下关于递归与迭代的说法，正确的是（ ）
递归程序一定比迭代程序运行快
递归程序占用的空间一定比迭代少
递归程序不可能出现无限循环
理论上所有递归算法都可以转换为迭代算法
在双向链表头部插入新结点 t（head 为头哨兵），以下代码横线处应填入（ ）
t->next = head->next;
t->prev = head;
head->next->prev = t;
______;
head->next = t;
head->prev = t;
t->prev = head->next;
t->next = head;
以下二分查找的变体用于查找第一个大于等于 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;
}
arr[mid] > target
arr[mid] >= target
arr[mid] < target
arr[mid] <= target
标准 3 柱汉诺塔问题中，移动 n 个盘子所需的最少移动次数是（ ）
O(n)
O(n log n)
O(2ⁿ)
O(n²)
硬币找零问题中，面额为 {1, 5, 10, 25} 分，要找零 40 分。使用贪心策略，得到的硬币数是（ ）
2 枚
3 枚
4 枚
5 枚
高精度乘法中，两个位数分别为 m 和 n 的数相乘，结果最多有多少位？（ ）
m + n
m × n
m + n + 1
max(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++];
}
L[i] > R[j]
L[i] <= R[j]
L[i] >= R[j]
L[i] != R[j]
递归函数 fib(n) 使用朴素递归计算斐波那契数，其时间复杂度是（ ）
O(n)
O(n log n)
O(2ⁿ)
O(1)
循环链表中，要判断指针 p 是否遍历完整个链表回到起点，条件是（ ）
p == NULL
p->next == NULL
p->data == 0
p == head
以下关于 GCD（最大公约数）的叙述，正确的是（ ）
gcd(a, b) = gcd(b, a % b)（当 b ≠ 0）是辗转相除法的核心递推式
gcd(a, b) 总是等于 a 和 b 中较小的那个数
gcd(0, n) 没有定义
辗转相除法的时间复杂度是 O(n)
分治算法解决"最大子数组和"问题时，需要计算跨越中点的最大和，这部分的复杂度是（ ）
O(1)
O(n)
O(n²)
O(log n)
在循环链表中，每个结点都有一个前驱结点和一个后继结点。（ ）
高精度加法的时间复杂度与两个数的位数之和成正比，即 O(n)。（ ）
分治算法的效率一定比直接求解原问题的效率高。（ ）
归并排序需要额外的 O(n) 空间来存放临时数组。（ ）
快速排序在任何输入情况下都能保证 O(n log n) 的时间复杂度。（ ）
理论上所有递归算法都可以转换为等价的迭代算法。（ ）
贪心算法在做出选择后，如果发现选择不是最优的，会回溯重新选择。（ ）
标准 3 柱汉诺塔问题中，移动 n 个盘子所需的最少步数为 2ⁿ − 1。（ ）
链表结点在内存中必须连续存放。（ ）
高精度乘法和除法的实现都涉及逐位相乘和进位处理，两者时间复杂度相同。（ ）
试题名称：高精度加法
时间限制：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