GESP C++ 五级 模拟卷1
GESP C++ 五级模拟卷1（链表操作、数论、快速排序、二分查找、贪心算法）
// questions
题目预览
与数组相比，链表在以下哪种操作上通常具有更高的效率？（ ）
在已知位置插入或删除节点
通过下标随机访问元素
在未排序链表中查找指定值
计算链表中元素的总个数
用辗转相除法求 gcd(72, 30) 时，第一步计算 72 % 30 = 12，则第二步计算的是（ ）
gcd(72, 12)
gcd(30, 12)
gcd(12, 6)
gcd(30, 72)
以下代码用于判断正整数 n 是否为质数，横线处应填入（ ）
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (______) return false;
}
return true;
}
n / i == 0
i * i > n
n % i == 0
n - i == 0
以下快速排序的 partition 函数中，横线处应填入（ ）
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (______) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
arr[j] > pivot
arr[j] == pivot
arr[j] >= pivot
arr[j] < pivot
在二分查找中，为避免 (left + right) 溢出，mid 的计算通常写为（ ）
mid = left + (right - left) / 2;
mid = (left + right) * 2;
mid = left - (right - left) / 2;
mid = right - (left + right) / 2;
贪心算法的核心特征是（ ）
总能找到全局最优解
每一步选择当前看起来最优的方案
将问题分解为子问题分别求解
尝试所有可能的组合
以下排序算法中，属于稳定排序的是（ ）
选择排序
快速排序
归并排序
堆排序
在程序运行过程中，如果递归调用的层数过多，通常会因为什么原因引发错误？（ ）
堆空间溢出
全局变量区溢出
代码段溢出
栈空间溢出
在双向链表中，结点 p 的前驱和后继均非空。要删除结点 p，以下正确的是（ ）
p->prev->next = p->next; p->next->prev = p->prev;
p->next = p->prev; p->prev = p->next;
p->prev = p->next; p->next->prev = p;
p->prev->prev = p->next; p->next->next = p->prev;
根据唯一分解定理，以下分解正确的是（ ）
18 = 3 × 6
30 = 2 × 3 × 5
28 = 4 × 7
36 = 2 × 3 × 6
快速排序在平均情况下的时间复杂度是（ ）
O(n)
O(n²)
O(n log n)
O(log n)
执行以下代码后，变量 a 的值是（ ）
int a = 1, b = 1, c;
for (int i = 3; i <= 6; i++) {
c = a + b;
a = b;
b = c;
}
cout << a;
3
5
8
13
在双向循环链表中，head 为头哨兵结点。将新结点 t 插入到链表头部（head 之后），横线处应填入（ ）
void insertHead(Node* head, Node* t) {
t->next = head->next;
t->prev = head;
______;
head->next = t;
}
head->next->prev = t;
head->prev->next = t;
t->next->prev = head;
head->next = t->next;
以下关于质数的说法，正确的是（ ）
1 是质数
2 是唯一的偶质数
所有奇数都是质数
大于 10 的质数个位数一定是 1
活动选择问题中，贪心策略为"每次选择结束时间最早的活动"。使用该策略（ ）
一定能得到全局最优解
不能保证得到最优解
一定能得到全局最优解，前提是按结束时间排序后贪心
需要配合回溯才能得到最优解
链表支持通过下标直接访问任意位置的元素。（ ）
辗转相除法（欧几里得算法）可用于求两个正整数的最大公约数。（ ）
快速排序在最好情况下的时间复杂度为 O(n²)。（ ）
二分查找只适用于有序数组。（ ）
贪心算法能够保证对所有问题都得到全局最优解。（ ）
2 是唯一的偶质数。（ ）
归并排序是一种稳定的排序算法。（ ）
递归调用层数过多可能导致栈空间溢出。（ ）
唯一分解定理适用于所有正整数。（ ）
链表在插入元素时需要移动其他元素。（ ）
试题名称：最大公约数
时间限制：1.0 s | 内存限制：512.0 MB
给定两个正整数 a 和 b，求它们的最大公约数（GCD）。
输入格式 一行，两个正整数 a 和 b（1 ≤ a, b ≤ 10⁹）。
输出格式 一行，一个整数，表示 a 和 b 的最大公约数。
样例输入 #1
72 30
样例输出 #1
6
试题名称：二分查找统计出现次数
时间限制：1.0 s | 内存限制：512.0 MB
给定一个升序排列的整数数组（可能包含重复元素）和一个目标值 target，请统计 target 在数组中出现的次数。
要求使用二分查找实现，时间复杂度 O(log n)。
输入格式 第一行，两个整数 N 和 target（1 ≤ N ≤ 100000）。 第二行，N 个升序排列的整数，绝对值不超过 10⁹，数之间用空格分隔。
输出格式 一行，一个整数，表示 target 在数组中出现的次数。如果不存在则输出 0。
样例输入 #1
8 3
1 2 3 3 3 5 6 7
样例输出 #1
3