CCF-GESP 等级考试 2023年12月认证C++五级真题解析

2023年12月真题

一、单选题（每题2分，共30分）

在这里插入图片描述
正确答案：C
考察知识点：算法
解析：fiboA 是很好理解的，但是执行效率不高，有的计算是重复的，导致效率低。

在这里插入图片描述

正确答案：C
考察知识点：算法
解析：本题考察归并排序。归并排序需要先将排序序列一分为二，左边的元素的区间是[s,m],右边元素区间是[m+1,t]，然后递归排序两个子序列后，将有序的子序列合并。

在这里插入图片描述
正确答案：D
考察知识点：算法
解析：本题考察递归算法。输出 fracA 函数，是先输出1，再输出5 的阶乘，120；23行代码，执行fracB函数，此时stepCount从2开始计数，依次输出2/3/4/5/6，再输出 5 的阶乘 120。

在这里插入图片描述

正确答案：A
考察知识点：排序算法
解析：本题考察排序算法。前一个数字，下标是 j 的数字是偶数，后面的数字下标是 j+1 的是奇数，按照要求，偶数在奇数的后面，要交换。A 符合题意条件。

在这里插入图片描述
正确答案：B
考察知识点：指针
解析：本题考察双链表知识点。每个节点需要 2 个指针，指向前驱节点和后继节点。按照要求，新的节点要求插入到链表头部。头节点和新插入的节点都需要修改。B 选项能够完成新节点的插入。

在这里插入图片描述
正确答案：A
考察知识点：数学
解析：本题考察数学算法，求最大公约数。这是典型的最大公约数写法的变形。排除法选 A。

在这里插入图片描述

正确答案：C
考察知识点：排序算法
解析：本题考察快速排序。Less 数组保存的是小于等于pivot，然后加上pivot
元素，再加上大于等于 pivot 的数组。

在这里插入图片描述
正确答案：B
考察知识点：数学
解析：本题考察数学知识，判断质数。A 函数时间复杂度是O(n/2)，B 函数算法是 O(sqrt(n))，大部分情况后者是优的，值更小。

在这里插入图片描述

正确答案：D
考察知识点：算法
解析：本题考察算法知识点。二分法每次规模减半，查找平均时间复杂度是B。

在这里插入图片描述
正确答案：B
考察知识点：算法
解析：本题考察算法知识点。二分法每次规模减半，单词查找平均时间复杂度是 B。

在这里插入图片描述
正确答案：D
考察知识点：算法
解析：本题考察高精度知识点。每次保存对应位和的最低位数字，去掉最低位数字后，保持进位，循环执行。

在这里插入图片描述

正确答案：B
考察知识点：链表
解析：本题考察链表知识点。每个节点指向自己前一个节点和后一个节点，因此是双向链表。

在这里插入图片描述
正确答案：B
考察知识点：计算机基础知识
解析：本题考察计算机基础知识。通信卫星可以转发无线电信号，实现通信地球站间或地球站与航天器间的无线电通信，因此具有信号中继作用。选B。

在这里插入图片描述
正确答案：C
考察知识点：数学
解析：本题考察数学知识。线筛和埃筛都可以判断素数，枚举也可以，二分规模减半，不能合理判断。

在这里插入图片描述
正确答案：B
考察知识点：排序算法
解析：本题考察排序算法知识。需要了解每种排序算法的特点。快速排序是选定一个数字，每次把比它小的放在左边，比元素大的放在右边，不能确定最值。

二、判断题（每题2分，共20分）

在这里插入图片描述
正确答案：正确
考察知识点：排序算法
解析：本题考察排序算法知识。归并排序算法的时间复杂度的描述正确。

在这里插入图片描述
正确答案：错误
考察知识点：算法
解析：因为考纲中对二分法同时列出了“二分查找”和“二分答案（或二分枚举）”。

在这里插入图片描述
正确答案：错误
考察知识点：算法
解析：本题考察递归算法知识。递归函数要调用自己。

在这里插入图片描述
正确答案：正确
考察知识点：算法
解析：本题考察贪心算法知识。贪心是局部达到最优。

在这里插入图片描述
正确答案：正确
考察知识点：数学
解析：本题考察数学知识。素数分解定理规定:任何一个整数都可以被分解为一系列因子的乘积,乘积中所有的因子都是质数(即素数)。（更严谨一点：大于1的整数）

在这里插入图片描述
正确答案：正确
考察知识点：排序
解析：本题考察排序算法知识。当数据初始有序时，插入排序的最快时间复杂度是 O(n)，快排最坏时间复杂度是 $O(N^2)$ 。

在这里插入图片描述
正确答案：错误
考察知识点：进制转换
解析：本题考察进制转换知识。转换后的内容要倒序输出并以0 开头。

在这里插入图片描述
正确答案：正确
考察知识点：排序
解析：本题考察排序算法知识。sort 默认是从小到大排序。

在这里插入图片描述
正确答案：正确
考察知识点：数学知识
解析：本题考察数学知识。可以循环 N 的一半找到所有因数。

在这里插入图片描述
正确答案：正确
考察知识点：排序算法
解析：本题考察排序算法知识。冒泡排序，相邻的数据交换，而且修改节点链的操作不会改变复杂度。

三、编程题（每题25分，共50分）

在这里插入图片描述

本题考察数学知识，埃筛。

幸运数：所有大于等于 $a$ 的完全平方数都是超级幸运数。所有超级幸运数的倍数都是幸运数。

那最小的幸运数必然是大于等于 $a$ 的最小完全平方数，也就是 ceil(sqrt(a)) 的平方。定义一个数组，标记从 ceil(sqrt(a)) 开始的所有数的平方以及他们的倍数。给了数据范围 1000001，离1000001最近的完全平方数是1002001，可作为边界值。

#include<bits/stdc++.h>
using namespace std;
const int N=1002001; //1002001是离1000001最近的完全平方数 
int luckyNumBase[N]; //幸运数，下标等于元素值为幸运数，非幸运数存储它的幸运化
int main() {int a, n, num;cin>>a>>n;for(int i=ceil(sqrt(a)); i*i<=N; i++) {for(int num=1; i*i*num<=N; num++) {luckyNumBase[i*i*num]=i*i*num;}}int base=N;for(int i=N; i>=1; i--){if(luckyNumBase[i]==i) base=i;else luckyNumBase[i] = base;}for(int i=1; i<=n; i++) {cin>>num;if(luckyNumBase[num]==num) cout<<"lucky"<<endl;else cout<<luckyNumBase[num]<<endl;}return 0;
}

在这里插入图片描述

本题考察位运算，循环。

题目给出了ai的范围， 0≤ai ≤2147483647，int类型（32位）可以存下的数，最左边符号位，把最右边算作0位，则表示数的最高位下标是30。两种食材的契合度是使用按位与运算得到的，按位与：都是1才是1，则契合度的值也必定是一个int类型能存储的值，且 1 越靠左边出现，该值越大。

可以从最高位开始枚举，如果有两个以上的数截止到第i位都相同，则契合度res这一位可为1，否则，契合度res这一位为0。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n, arr[N];//美味度
int main() {cin >> n;for (int i = 1; i <= n; i++) cin>>arr[i];//题目给出了ai的范围， 0≤ai ≤2147483647，int类型可以存下的数，32位存储//最左边表示符号，把最右边算作0位，则表示数的最高位下标是第30位int res=0, tmp=pow(2,30);//两种食材的契合度是使用按位与运算得到的，按位与：都是1才是1，则契合度的值也必定是一个int类型能存储的值，且 1 越靠左边出现，该值越大 //可以从最高位开始枚举，如果有两个以上的数截止到第i位都相同，则契合度res这一位可为1for(int i=30; i>=0; i--) {res+=tmp;    //预置res的 i 位为1int cnt=0;for(int j=1; j<=n; j++) {//如果 (a[j]&res)==res 成立，意味着a[j]和res截止到第i位都相同if ((arr[j]&res)==res) cnt++;}if (cnt<2) { //cnt<2 意味着没有或者只有1个数截止到第i位和res相同，无法通过按位与使得res的第i位为1,置res的 i 位为0res-=tmp;}tmp >>= 1;}cout<<res;return 0;
}