2025年3月CCF-GESP编程能力等级认证C++编程五级真题
2025年3月CCF-GESP编程能力等级认证C++编程五级真题
一、单选题（每题 2 分，共 30 分）
第 1 题 链表不具备的特点是( )。
{{ select(1) }}
- A. 可随机访问任何一个元素
- B. 插入、删除操作不需要移动元素
- C. 无需事先估计存储空间大小
- D. 所需存储空间与存储元素个数成正比
第 2 题 双向链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p，则下述语句中错误的是（ ）。
{{ select(2) }}
- A.
p->next->prev = p->next; - B.
p->prev->next = p->prev; delete p; - C.
p->prev->next = p->next; p->next->prev = p->prev; delete p; - D.
p->next->prev = p->prev; p->prev->next->prev = p->next; delete p;
第 3 题 假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是( )。
struct LinkedList {
ListNode<T>* head;
ListNode<T>* tail;
};
void InitLinkedList(LinkedList* list) {
list->head = new ListNode<T>;
list->tail = new ListNode<T>;
________________________________ // 在此处填入代码
}
{{ select(3) }}
- A.
list->head->prev = list->head; list->tail->prev = list->head; - B.
list->head->next = list->tail; list->tail->prev = list->head; - C.
list->head->next = list->tail; list->tail->next = list->head; - D.
list->head->next = list->tail; list->tail->next = nullptr;
第 4 题 用以下辗转相除法（欧几里得算法）求 gcd(84, 60) 的步骤中，第二步计算的数是（ ）。
int gcd(int a, int b) {
int big = a > b ? a : b;
int small = a < b ? a : b;
if (big % small == 0) {
return small;
}
return gcd(small, big % small);
}
{{ select(4) }}
- A. 84 和 60
- B. 60 和 24
- C. 24 和 12
- D. 12 和 0
第 5 题 根据唯一分解定理，下面整数的唯一分解是正确的（ ）。
{{ select(5) }}
- A. 18 = 3 × 6
- B. 28 = 4 × 7
- C. 36 = 2 × 3 × 6
- D. 30 = 2 × 3 × 5
第 6 题 下述代码实现素数表的线性筛法，筛选出所有小于等于 ( n ) 的素数，横线上应填的最佳代码是( )。
vector<int> sieve_linear(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
if (n < 2) return primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n/2; i++) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; ________________________________ ; j++) { // 在此处填入代码
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break;
}
}
for (int i = n/2 + 1; i <= n; i++) {
if (is_prime[i]) primes.push_back(i);
}
return primes;
}
{{ select(6) }}
- A.
j < primes.size() - B.
i * primes[j] <= n - C.
j < primes.size() && i * primes[j] <= n - D.
j <= n
第 7 题 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
{{ select(7) }}
- A. 系统分配的栈空间溢出
- B. 系统分配的堆空间溢出
- C. 系统分配的队列空间溢出
- D. 系统分配的链表空间溢出
第 8 题 对下面两个函数，说法错误的是（ ）。
int factorialA(int n) {
if (n <= 1) return 1;
return n * factorialA(n-1);
}
int factorialB(int n) {
if (n <= 1) return 1;
int res = 1;
for(int i = 2; i <= n; i++)
res *= n;
}
{{ select(8) }}
- A. 两个函数的实现的功能相同。
- B. 两个函数的时间复杂度均为 ( O(n) )。
- C.
factorialA采用递归方式。 - D.
factorialB采用递归方式。
第 9 题 下面算法中，（ ）是不稳定的排序。
{{ select(9) }}
- A. 选择排序
- B. 插入排序
- C. 归并排序
- D. 冒泡排序
第 10 题 考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是( )。
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 基准值
int i = low - 1;
for (int j = low; j < high; j++) {
________________________________ // 在此处填入代码
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
{{ select(10) }}
- A.
if (arr[j] > pivot) { i++; swap(arr[i], arr[j]); } - B.
if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } - C.
if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; } - D.
if (arr[j] == pivot) { i++; swap(arr[i], arr[j]); }
第 11 题 若用二分法在 [1, 100] 内猜数，最多需要猜（ ）次。
{{ select(11) }}
- A. 100
- B. 10
- C. 7
- D. 5
第 12 题 下面代码实现了二分查找算法，在数组 arr 中找到目标元素 target 的位置，则横线上能填写的最佳代码是（ ）。
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
________________________________ // 在此处填入代码
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
{{ select(12) }}
- A.
int mid = left + (right - left) / 2; - B.
int mid = left; - C.
int mid = (left + right) / 2; - D.
int mid = right;
第 13 题 贪心算法的核心特征是（ ）。
{{ select(13) }}
- A. 总是选择当前最优解
- B. 回溯尝试所有可能
- C. 分阶段解决子问题
- D. 总能找到最优解
第 14 题 函数 int findMax(int arr[], int low, int high) 计算数组中最大元素，其中数组 arr 从索引 low 到 high，（ ）正确实现了分治逻辑。
{{ select(14) }}
- A.
if (low == high) return arr[low]; int mid = (low + high) / 2; return arr[mid]; - B.
if (low >= high) return arr[low]; int mid = (low + high) / 2; int leftMax = findMax(arr, low, mid - 1); int rightMax = findMax(arr, mid, high); return leftMax + rightMax; - C.
if (low > high) return 0; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return leftMax * rightMax; - D.
if (low == high) return arr[low]; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return (leftMax > rightMax) ? leftMax : rightMax;
第 15 题 小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（ ）。
vector<int> multiply(vector<int>& a, vector<int>& b) {
int m = a.size(), n = b.size();
vector<int> c(m + n, 0);
// 逐位相乘，逆序存储
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c[i + j] += a[i] * b[j];
}
}
// 处理进位
int carry = 0;
for (int k = 0; k < c.size(); ++k) {
________________________________ // 在此处填入代码
c[k] = temp % 10;
carry = temp / 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
{{ select(15) }}
- A.
int temp = c[k]; - B.
int temp = c[k] + carry; - C.
int temp = c[k] - carry; - D.
int temp = c[k] * carry;
二、判断题（每题 2 分，共 20 分）
第 1 题 单链表中删除某个结点 p（非尾结点），但不知道头结点，可行的操作是将 p 的值设为 p->next 的值，然后删除 p->next。（ ）
{{ select(16) }}
- 对
- 错
第 2 题 链表存储线性表时要求内存中可用存储单元地址是连续的。（ ）
{{ select(17) }}
- 对
- 错
第 3 题 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。（ ）
{{ select(18) }}
- 对
- 错
第 4 题 贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。（ ）
{{ select(19) }}
- 对
- 错
第 5 题 递归函数必须具有一个终止条件，以防止无限递归。（ ）
{{ select(20) }}
- 对
- 错
第 6 题 快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 ( O(n \log n) )。（ ）
{{ select(21) }}
- 对
- 错
第 7 题 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 ( O(n \log n) )。（ ）
{{ select(22) }}
- 对
- 错
第 8 题 二分查找适用于对无序数组和有序数组的查找。（ ）
{{ select(23) }}
- 对
- 错
第 9 题 小杨有100元去超市买东西，每个商品有各自的价格，每种商品只能买1个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。（ ）
{{ select(24) }}
- 对
- 错
第 10 题 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。（ ）
{{ select(25) }}
- 对
- 错