CCF GESP 2026年3月认证 C++ 5级
二
判断题
第 1 题
有一个存储了 n 个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是 O(1) ，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 O(1) 。
第 2 题
若数组 a 已按升序排列，则下面代码可以正确实现“在 a 中查找第一个大于等于 x 的元素的位置”。
int lowerBound(vector<int>& a,int x){
int l = 0, r = a.size();
while(l<r){
int mid = (l+r)/2;
if(a[mid] >= x) r = mid;
else l = mid+1;
}
return l;
}
第 3 题
快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。
第 4 题
若某算法满足递推式： $T(n)=2T(n/2)+O(n) $，则其时间复杂度为 $O(n\ log\,n)$ 。
第 5 题
在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i<j 且 a[i]>a[j]，则 a[i] 和 a[j] 是一个逆序对。下面代码可以正确统计数组 a 区间 [1,r] 内的逆序对总数。
long long cnt = 0;
void merge_count(vector<int>& a,int l,int m,int r){
int i = l, j = m + 1;
while(i <= m && j <= r){
if(a[i] <= a[j]) i++;
else{
cnt += (m - i + 1);
j++;
}
}
}
第 6 题
根据唯一分解定理，如果大于 1 的整数不能被任何不超过其平方根的质数整除，那么 n 必定是质数。
第 7 题
假设数组 a 的值域范围是 D，以下程序的时间复杂度是 $O(n\ log\,n+n\ log\,D)$ 。
bool check(int n, int a[], int k, int dist) {
int cnt = 1;
int last = a[0];
for (int i = 1; i < n; i++) {
if (a[i] - last >= dist) {
cnt++;
last = a[i];
}
}
return cnt >= k;
}
int solve(int n, int a[], int k) {
std::sort(a, a + n);
int l = 0;
int r = a[n - 1] - a[0];
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(n, a, k, mid))
l = mid;
else
r = mid - 1;
}
return l;
}
int main() {
int a[] = {1, 2, 8, 4, 9};
int n = 5;
int k = 3;
std::cout << solve(n, a, k) << std::endl;
return 0;
}
第 8 题
若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。
第 9 题
线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度。
第 10 题
任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。
判断题部分已到底了。