CCF GESP 2026年6月认证 C++ 5级
二
判断题
第 1 题
数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。
第 2 题
带哨兵头尾节点的双向循环链表，在表头插入节点
p，以下四步操作无论什么顺序执行结果都正确。① p->next = head->next;
② p->prev = head;
③ head->next->prev = p;
④ head->next = p;
第 3 题
对任意正整数
a、b，以下两种写法的 gcd 函数返回值完全相同。int gcd1(int a, int b) {
return b ? gcd1(b, a % b) : a;
}
int gcd2(int a, int b) {
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
第 4 题
在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组
L 和 R 合并回原数组 arr 中。void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
第 5 题
分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。
第 6 题
贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。
第 7 题
二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 $O(1)$ 时间内的随机访问。
第 8 题
以下函数
f1 的时间复杂度比函数 f2 的更高。void f1(int n) {
for (int i = 1; i < n; i *= 2);
}
void f2(int n) {
if (n <= 1) return;
f2(n - 1);
f2(n - 1);
}
第 9 题
唯一分解定理表明，任何一个大于 $1$ 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。
第 10 题
归并排序和快速排序在平均情况下的时间复杂度均为 $O(nlog n)$。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。
判断题部分已到底了。