首页 › 试卷 › GESP编程能力等级认证 › GESP-C++五级 › 2025年3月CCF-GESP编程能力等级认证C++编程五级真题

2025年3月CCF-GESP编程能力等级认证C++编程五级真题 VIP

GESP-C++五级 共 27 题 2025 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

链表【不具备】的特点是?( )

  • A 可随机访问任何一个元素
  • B 插入、删除操作不需要移动元素
  • C 无需事先估计存储空间大小
  • D 所需存储空间与存储元素个数成正比
查看答案与解析
答案:A
这道题暂未补解析。
2. 单选题

双向链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。

设 p 指向链表中的一个结点,它的前驱结点和后继结点均非空。要删除结点 p ,则下述语句中【错误】的是?( )

  • A p->next->prev = p->next;p->prev->next = p->prev;delete p;
  • B p->prev->next = p->next;p->next->prev = p->prev;delete p;
  • C p->next->prev = p->prev;p->next->prev->next = p->next;delete p;
  • D p->prev->next = p->next;p->prev->next->prev = p->prev;delete p;
查看答案与解析
答案:A
解析:

要删除双向链表中的结点 p,需要正确调整其前驱(prev)和后继(next)结点的指针:

让 p->prev->next 指向 p->next(前驱的后继指向 p 的后继)。

让 p->next->prev 指向 p->prev(后继的前驱指向 p 的前驱)。

选项A错误:

p->next->prev = p->next;  // 错误:让后继的前驱指向自己(p->next),破坏了链表结构

p->prev->next = p->prev;  // 错误:让前驱的后继指向自己(p->prev),链表断裂

3. 单选题

假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为 head 和 tail ,链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。

下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是?( )

// 链表结点
template <typename T>
struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;
    // 构造函数
    explicit ListNode(const T& val = T())
        : data(val), prev(nullptr), next(nullptr) {}
};
struct LinkedList {
    ListNode<T>* head;
    ListNode<T>* tail;
};
void InitLinkedList(LinkedList* list) {
    list->head = new ListNode<T>;
    list->tail = new ListNode<T>;
    ________________________________ // 在此处填入代码
};
  • 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;
查看答案与解析
答案:B
解析:

双向循环链表的结构:

头哨兵 head:

head->prev 应该指向链表的最后一个结点(即 tail)。

head->next 应该指向链表的第一个实际结点(如果链表为空,则指向 tail)。

尾哨兵 tail:

tail->prev 应该指向链表的最后一个实际结点(如果链表为空,则指向 head)。

tail->next 应该指向链表的第一个结点(即 head)。

由于链表为空,head 和 tail 应该互相指向对方:

head->next = tail

tail->prev = head

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);
}
  • A 84和60
  • B 60和24
  • C 24和12
  • D 12和0
查看答案与解析
答案:B
解析:

调用gcd(84, 60)函数中:

big=84,small=60,big % small不为零,递归调用:

gcd(60, 24)。

5. 单选题

根据唯一分解定理,下面整数的唯一分解是正确的?( )

  • A 18 = 3 × 6
  • B 28 = 4 × 7
  • C 36 = 2 × 3 × 6
  • D 30 = 2 × 3 × 5
查看答案与解析
答案:D
解析:

唯一分解定理指出:任何一个大于 1 的整数,要么本身是一个质数,要么可以唯一地分解为一系列质数的乘积。

需要检查每个选项的分解是否 全部是质数,只有选项D符合。

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;
}
  • A j < primes.size()
  • B i * primes[j] <= n
  • C j < primes.size() && i * primes[j] <= n
  • D j <= n
查看答案与解析
答案:C
解析:

线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。

内层循环的目的是 筛除 i×primes[j],因此需要满足:

j 不超过 primes 数组的大小(避免越界访问)。

i×primes[j]≤n(筛除的合数不能超过 n)。

本题答案为选项C。

7. 单选题

在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误?

  • A 系统分配的栈空间溢出
  • B 系统分配的堆空间溢出
  • C 系统分配的队列空间溢出
  • D 系统分配的链表空间溢出
查看答案与解析
答案:A
解析:

如果递归层数过深,栈空间会被耗尽,导致 栈溢出错误。

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 *= i;
}
  • A 两个函数的实现的功能相同。
  • B 两个函数的时间复杂度均为 O(n)。
  • C factorialA采用递归方式。
  • D factorialB采用递归方式。
查看答案与解析
答案:D
解析:

两个计算阶乘的函数 factorialA 和 factorialB。

factorialA采用递归的方法,factorialB 采用循环方式实现,二者的时间复杂度均为O(n)。

9. 单选题

下算法中,( )是不稳定的排序?

  • A 选择排序
  • B 插入排序
  • C 归并排序
  • D 冒泡排序
查看答案与解析
答案:A
解析:

稳定排序 是指:如果两个相等的元素在排序前后的相对位置保持不变。

不稳定排序 是指:相等的元素在排序后可能交换位置。

对于选择排序,每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾。

例如:[5, 5, 2]进行排序,[5(1), 5(2), 2](用下标区分两个 5),找到最小值 2,交换 5(1)和 2,数组变为:[2, 5(2), 5(1)],两个5的相对顺序改变了。

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;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  • 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]);
    }
查看答案与解析
答案:B
解析:

快速排序是一种分治算法,其基本步骤如下:

选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。

分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。

递归排序:递归地对基准前后的子数组进行快速排序。

在分区过程中:

i初始化为low - 1,表示小于基准的区域最初为空。

j从low到high - 1遍历数组。

如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。

本题答案为选项B。

11. 单选题

若用二分法在[1, 100]内猜数,最多需要猜( )次?

  • A 100
  • B 10
  • C 7
  • D 5
查看答案与解析
答案:C
解析:

二分查找每次将搜索区间对半分,最坏情况下需要猜测的次数:

2^6<100(6 次不够),2^7>=100(7 次足够)。

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;
}
  • A int mid = left + (right - left) / 2;
  • B int mid = left;
  • C int mid = (left + right) / 2;
  • D int mid = right;
查看答案与解析
答案:A
解析:

计算 mid 需要满足:

正确性:必须保证 mid 是当前区间的中间位置。

安全性:避免整数溢出(当 left 和 right 很大时,left + right 可能溢出)。

选项A:int mid = left + (right - left) / 2,数学等价于选项C,但是通过 right - left 避免直接计算 left + right,防止溢出。

13. 单选题

贪心算法的核心特征是?( )

  • A 总是选择当前最优解
  • B 回溯尝试所有可能
  • C 分阶段解决子问题
  • D 总能找到最优解
查看答案与解析
答案:A
解析:

贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。

14. 单选题

函数 int findMax(int arr[], int low, int high) 计算数组中最大元素,其中数组 arr 从索引low 到 high ,( )正确实现了分治逻辑?

  • 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;
查看答案与解析
答案:D
解析:

分治法的核心思想是:分解,解决,合并。

对于 求数组最大值,分治法的具体实现是:

基准情况:如果 low == high,说明区间只有一个元素,直接返回 arr[low]。

分解:计算中间位置 mid。

递归求左半部分 [low, mid] 的最大值 leftMax。

递归求右半部分 [mid+1, high] 的最大值 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;
}
  • A int temp = c[k];
  • B int temp = c[k] + carry;
  • C int temp = c[k] - carry;
  • D int temp = c[k] * carry;
查看答案与解析
答案:B
解析:

高精度乘法(大数乘法)通过 逐位相乘并处理进位 来实现。

选项B正确,temp 是当前位的值加上前一位的进位。

二、判断题

16. 判断题

单链表中删除某个结点 p(非尾结点),但不知道头结点,可行的操作是将 p 的值设为 p->next 的值,然后删除 p->next 。( )

  • A对
  • B错
查看答案与解析
答案:对
解析:

删除某个结点 p,但不知道头结点,无法直接找到 p 的前驱结点。

但是可以复制后继结点的值,然后删除后继节点。

假设单链表为:A -> B -> C -> D,要删除 B:

将 B 的值设为 C 的值:B->data = C->data(链表变为 A -> C -> C -> D)。

删除 B->next(即 C):B->next = C->next(链表变为 A -> C -> D)。

最终效果:B 被删除了。

17. 判断题

链表存储线性表时要求内存中可用存储单元地址是连续的。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

链表中的结点在内存中,是 动态分配 的。

每个结点可以分布在内存的任意位置,通过指针(next)连接。

存储单元的地址可以不连续,也可以是连续的。

18. 判断题

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )

  • A对
  • B错
查看答案与解析
答案:对
解析:

线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。

而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。

本题答案为正确。

19. 判断题

贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。

20. 判断题

递归函数必须具有一个终止条件,以防止无限递归。( )

  • A对
  • B错
查看答案与解析
答案:对
解析:

正确,如果没有终止条件,函数会无限调用自身;

终止条件是递归的出口,确保问题规模能逐步缩小至可直接求解的情况。

21. 判断题

快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

快速排序的 平均时间复杂度为 O(nlog?n),但最坏情况下退化为 O(n^2)。

其性能与输入数据是否有序及 pivot 选择策略密切相关。

22. 判断题

归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

  • A对
  • B错
查看答案与解析
答案:对
解析:

归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:

分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。

合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。

总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。

23. 判断题

二分查找适用于对无序数组和有序数组的查找。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

二分查找(Binary Search)是一种高效的查找算法,其前提条件:输入数组 必须是有序的。

24. 判断题

小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

分治法的核心是:

分解:将问题划分为若干 相互独立且结构相同 的子问题。

解决:递归解决子问题。

合并:将子问题的解合并为原问题的解。

小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。

不是分治,因为无问题分解,无子问题合并。

25. 判断题

归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )

  • A对
  • B错
查看答案与解析
答案:对
解析:

分治法的核心是:

分解:将问题划分为若干 相互独立且结构相同 的子问题。

解决:递归解决子问题。

合并:将子问题的解合并为原问题的解。

归并排序体现了分治算法。

三、简答题

26. 简答题

平均分配

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有 2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i 件物品,小 B 会以 bi 的价格购买,而小 C 会以 ci 的价格购买。

为了平均分配这 2n 件物品,小 A 决定小 B 和小 C 各自只能买走恰好 n 件物品。你能帮小 A 求出他卖出这 2n 件物品所能获得的最大收入吗?

【输入描述】

第一行,一个正整数 n。

第二行, 2n 个整数 b1、b2、……、b(2n)。

第三行, 2n 个整数 c1、c2、……、c(2n)。

【输出描述】

一行,一个整数,表示答案。

【样例输入1】

3
1 3 5 6 8 10
2 4 6 7 9 11

【样例输出1】

36

【样例输入2】

2
6 7 9 9
1 2 10 12

【样例输出2】

35

【数据范围】

对于 20% 的测试点,保证 1<=n<=8。

对于另外 20% 的测试点,保证 0<=bi<=1,0<=ci<=1 。

对于所有测试点,保证 0<=n<=10^5,0<=bi<=10^9 ,0<=ci<=10^9 。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 2e5 + 5; int n; long long b[N], c[N], d[N]; long long ans; int main() {     scanf("%d", &amp;n);     assert(1 &lt;= n &amp;&amp; n &lt;= 1e5);     for (int i = 1; i &lt;= 2 * n; i++)         scanf("%lld", &amp;b[i]), assert(0 &lt;= b[i] &amp;&amp; b[i] &lt;= 1e9);     for (int i = 1; i &lt;= 2 * n; i++)         scanf("%lld", &amp;c[i]), assert(0 &lt;= c[i] &amp;&amp; c[i] &lt;= 1e9);     for (int i = 1; i &lt;= 2 * n; i++) {         ans += b[i];         d[i] = c[i] - b[i];     }     sort(d + 1, d + 2 * n + 1);     for (int i = n + 1; i &lt;= 2 * n; i++)         ans += d[i];     printf("%lld\n", ans);     return 0; }</pre>
这道题暂未补解析。
27. 简答题

原根判断

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数:

其中 a mod p 表示 a 除以 p 的余数。

小 A 现在有一个整数 T,请你帮他判断 a 是不是 p 的原根。

【输入描述】

第一行,一个正整数 T,表示测试数据组数。

每组测试数据包含一行,两个正整数 a、p。

【输出描述】

对于每组测试数据,输出一行,如果 a 是 p 的原根则输出 Yes ,否则输出 No 。

【样例输入1】

3
3 998244353
5 998244353
7 998244353

【样例输出1】

Yes
Yes
No

【数据范围】

对于 40% 的测试点,保证 3<=p<=1000。

对于所有测试点,保证 1<=T<=20, 3<=p<=10^9,1<a<p , p为质数。

对于所有测试点,保证 ,-100<= A(i,j) <=100 。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; using namespace std; int a, p; int ans; int fpw(int b, int e) {     if (e == 0)         return 1;     int r = fpw(b, e &gt;&gt; 1);     r = 1ll * r * r % p;     if (e &amp; 1)         r = 1ll * r * b % p;     return r; } void check(int e) {     if (fpw(a, e) == 1)         ans = 0; } int main() {     int T;     scanf("%d", &amp;T);     while (T--) {         scanf("%d%d", &amp;a, &amp;p);         ans = 1;         int phi = p - 1, r = phi;         for (int i = 2; i * i &lt;= phi; i++)             if (phi % i == 0) {                 check(phi / i);                 while (r % i == 0)                     r /= i;             }         if (r &gt; 1)             check(phi / r);         printf(ans ? "Yes\n" : "No\n");     }     return 0; }</pre>
这道题暂未补解析。