GESP C++ 五级模拟卷1（链表操作、数论、快速排序、二分查找、贪心算法）
选 单选题（共 15 题，每题 2 分）
与数组相比，链表在以下哪种操作上通常具有更高的效率？（ ）
用辗转相除法求 gcd(72, 30) 时，第一步计算 72 % 30 = 12，则第二步计算的是（ ）
以下代码用于判断正整数 n 是否为质数，横线处应填入（ ）
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (______) return false;
}
return true;
}
以下快速排序的 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;
}
在二分查找中，为避免 (left + right) 溢出，mid 的计算通常写为（ ）
贪心算法的核心特征是（ ）
以下排序算法中，属于稳定排序的是（ ）
在程序运行过程中，如果递归调用的层数过多，通常会因为什么原因引发错误？（ ）
在双向链表中，结点 p 的前驱和后继均非空。要删除结点 p，以下正确的是（ ）
根据唯一分解定理，以下分解正确的是（ ）
快速排序在平均情况下的时间复杂度是（ ）
执行以下代码后，变量 a 的值是（ ）
int a = 1, b = 1, c;
for (int i = 3; i <= 6; i++) {
c = a + b;
a = b;
b = c;
}
cout << a;
在双向循环链表中，head 为头哨兵结点。将新结点 t 插入到链表头部（head 之后），横线处应填入（ ）
void insertHead(Node* head, Node* t) {
t->next = head->next;
t->prev = head;
______;
head->next = t;
}
以下关于质数的说法，正确的是（ ）
活动选择问题中，贪心策略为"每次选择结束时间最早的活动"。使用该策略（ ）
判 判断题（共 10 题，每题 2 分）
链表支持通过下标直接访问任意位置的元素。（ ）
辗转相除法（欧几里得算法）可用于求两个正整数的最大公约数。（ ）
快速排序在最好情况下的时间复杂度为 O(n²)。（ ）
二分查找只适用于有序数组。（ ）
贪心算法能够保证对所有问题都得到全局最优解。（ ）
2 是唯一的偶质数。（ ）
归并排序是一种稳定的排序算法。（ ）
递归调用层数过多可能导致栈空间溢出。（ ）
唯一分解定理适用于所有正整数。（ ）
链表在插入元素时需要移动其他元素。（ ）
编 编程操作题（共 2 题，共 50 分）
试题名称：最大公约数
时间限制：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