2025年12月GESP编程能力认证C++等级考试五级真题(含答案和解析)

2025年12月GESP编程能力认证C++等级考试五级真题(含答案和解析)一、单选题（每题2分，共30分）。1.对如下定义的循环单链表，横线处填写（）。//循环单链表的结点。structNode{intdata;//数据域。Node*next;//指针域。Node(intd):data(d),next(nullptr){}};//创建一个只有一个结点的循环单链表。Node*createList(intvalue){Node*head=newNode(value);head->next=head;returnhead;}//在循环单链表尾部插入新结点。voidinsertTail(Node*head,intvalue){Node*p=head;while(p->next!=head){p=p->next;}Node*node=newNode(value);node->next=head;p->next=node;}//遍历并输出循环单链表。voidprintList(Node*head){if(head==nullptr)return;Node*p=head;_______________________//在此处填入代码。cout<<endl;}A.while(p!=nullptr){cout<<p->data<<"";p=p->next;}B.while(p->next!=nullptr){cout<<p->data<<"";p=p->next;}C.do{cout<<p->data<<"";p=p->next;}while(p!=head);D.for(;p;p=p->next){cout<<p->data<<"";}答案：C。解析：循环单链表的遍历需保证从头结点开始，直到再次回到头结点才结束。选项C使用do…while保证至少输出一次，并在p回到head时停止，防止无限循环；A、B、D因循环条件不适合循环链表结构而错误。2.区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（）。//区块（节点）。structBlock{intindex;//区块编号（高度）。stringdata;//区块里保存的数据。Block*prev;//指向前一个区块。Block(intidx,conststring&d,Block*p):index(idx),data(d),prev(p){}};//区块链。structBlockchain{Block*tail;//初始化。voidinit(){tail=newBlock(0,"GenesisBlock",nullptr);}//插入新区块。voidaddBlock(conststring&data){_______________________//在此处填入代码。}//释放内存。voidclear(){Block*cur=tail;while(cur!=nullptr){Block*p=cur->prev;deletecur;cur=p;}tail=nullptr;}};A.Block*newBlock=newBlock(tail->index+1,data,tail);tail=newBlock->prev;B.Block*newBlock=newBlock(tail->index+1,data,tail);tail=newBlock;C.Block*newBlock=newBlock(tail->index+1,data,tail->prev);tail=newBlock;D.Block*newBlock=newBlock(tail->index+1,data,tail->prev);tail=newBlock->prev;答案：B。解析：区块链尾部插入新区块时，新区块的prev指向当前尾区块，并更新tail指针指向新节点。选项B正确：tail->index+1生成新区块编号，prev指向旧tail，最后tail=newBlock更新链尾。其他选项要么更新tail错误，要么编号不正确。3.下面关于单链表和双链表的描述中，正确的是（）。structDNode{intdata;DNode*prev;DNode*next;};//在双链表中删除指定节点。voiddeleteNode(DNode*node){if(node->prev){node->prev->next=node->next;}if(node->next){node->next->prev=node->prev;}deletenode;}structSNode{intdata;SNode*next;};//在单链表中删除指定节点。voiddeleteSNode(SNode*head,SNode*node){SNode*prev=head;while(prev->next!=node){prev=prev->next;}prev->next=node->next;deletenode;}A.双链表删除指定节点是O(1)，单链表是O(1)。B.双链表删除指定节点是O(n)，单链表是O(1)。C.双链表删除指定节点是O(1)，单链表是O(n)。D.双链表删除指定节点是O(n)，单链表是O(n)。答案：C。解析：在双链表中，节点含有前驱指针prev和后继指针next，只要知道该节点指针即可在O(1)时间内调整前驱、后继指向并删除节点。单链表没有前驱指针，若要删除某节点，必须从链表头开始找到它的前驱节点，需遍历链表，时间复杂度为O(n)。因此正确答案为C：双链表删除指定节点是O(1)，单链表是O(n)。4.假设我们有两个数a=38和b=14，它们对模m同余，即a≡b(modm)。以下哪个值不可能是m？A.3B.4C.6D.9答案：D。解析：由a≡b(modm).可得m|(a-b)。这里a-b=38-14=24，所以m必须是24的约数。24的正约数为：1,2,3,4,6,8,12,24。选项中3、4、6都是24的约数，可以成立；9不是24的约数，所以不可能是m。因此正确答案是D。5.下面代码实现了欧几里得算法。下面有关说法，错误的是（）。intgcd1(inta,intb){returnb==0?a:gcd1(b,a%b);}intgcd2(inta,intb){while(b!=0){inttemp=b;b=a%b;a=temp;}returna;}A.gcd1()实现为递归方式。B.gcd2()实现为迭代方式。C.当a较大时，gcd1()实现会多次调用自身，需要较多额外的辅助空间。D.当a较大时，gcd1()的实现比gcd2()执行效率更高。答案：D。解析：gcd1()使用递归实现，gcd2()使用迭代实现，A和B正确。递归在调用栈中会为每次调用分配额外空间，因此当a较大且递归次数多时，gcd1()辅助空间消耗也会多，C正确。D错误，因为递归通常比迭代多了函数调用开销，执行效率并不会更高，甚至可能更低。因此正确答案是D。6.唯一分解定理描述的内容是（）。A.任何正整数都可以表示为两个素数的和。B.任何大于1的合数都可以唯一分解为有限个质数的乘积。C.两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。D.所有素数都是奇数。答案：B。解析：唯一分解定理指出：任何大于1的整数都可以唯一地表示为若干个质数的乘积。A是“哥德巴赫猜想”的表述，不是唯一分解定理。C公式错误，最大公约数与最小公倍数的关系是a×b=gcd(a,b)×lcm(a,b)。D错，因为素数2是偶数。因此正确答案是B。7.下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是（）。vector<int>linear_sieve(intn){vector<bool>is_prime(n+1,true);vector<int>primes;is_prime[0]=is_prime[1]=0;//0和1两个数特殊处理。for(inti=2;i<=n;++i){if(is_prime[i]){primes.push_back(i);}________________________________{//在此处填入代码。is_prime[i*primes[j]]=0;if(i%primes[j]==0)break;}}returnprimes;}A.for(intj=0;j<primes.size()&&i*primes[j]<=n;j++)B.for(intj=sqrt(n);j<=n&&i*primes[j]<=n;j++)C.for(intj=1;j<=sqrt(n);j++)D.for(intj=1;j<n&&i*primes[j]<=n;j++)答案：A。解析：线性筛法的内层循环应遍历当前已找到的素数列表，条件是i×primes[j]≤n，以保证不越界。选项A使用j<primes.size()并同时检查乘积不超过n，符合线性筛法的正确写法。B以图片为起点不符合线性筛法的遍历逻辑。C、D循环范围和索引均不正确，会导致逻辑错误或越界。因此正确答案是A。8.下列关于排序的说法，正确的是（）。A.快速排序是稳定排序B.归并排序通常是稳定的C.插入排序是不稳定排序D.冒泡排序不是原地排序答案：B。解析：稳定排序指相等元素的相对位置在排序后不变。快速排序由于交换和分区过程可能改变相等元素的相对位置，因此通常是不稳定排序，A错。归并排序在合并时按顺序处理两边的相等元素，因此通常是稳定排序，B对。插入排序每次插入时不会改变相等元素的相对位置，因此它是稳定排序，C错。冒泡排序只通过相邻元素交换完成排序，不需要额外空间，是原地排序，因此D错。正确答案是B。9.下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（）。voidmerge(vector<int>&arr,vector<int>&temp,intl,intmid,intr){inti=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(arr[i]<=arr[j])temp[k++]=arr[i++];elsetemp[k++]=arr[j++];}while(i<=mid)temp[k++]=arr[i++];while(j<=r)temp[k++]=arr[j++];for(intp=l;p<=r;p++)arr[p]=temp[p];}voidmergeSort(vector<int>&arr,vector<int>&temp,intl,intr){if(l>=r)return;intmid=l+(r-l)/2;mergeSort(arr,temp,l,mid);mergeSort(arr,temp,mid+1,r);merge(arr,temp,l,mid,r);}A.归并排序的平均复杂度是O(nlogn)。B.归并排序需要O(n)的额外空间。C.归并排序在最坏情况的时间复杂度是O(n2)。D.归并排序适合大规模数据。答案：C。解析：归并排序是一种典型的分治算法，平均和最坏情况下的时间复杂度均为O(nlogn)，A正确，C错误。它在合并过程中需要一个临时数组存放结果，因此额外空间复杂度为O(n)，B正确。由于归并排序稳定且时间复杂度低，适合大规模数据处理，D正确。因此不正确的说法是C。10.下述C++代码实现了快速排序算法，最坏情况的时间复杂度是（）。intpartition(vector<int>&arr,intlow,inthigh){inti=low,j=high;intpivot=arr[low];//以首元素为基准。while(i<j){while(i<j&&arr[j]>=pivot)j--;while(i<j&&arr[i]<=pivot)i++;if(i<j)swap(arr[i],arr[j]);}swap(arr[i],arr[low]);returni;}voidquickSort(vector<int>&arr,intlow,inthigh){if(low>=high)return;intp=partition(arr,low,high);quickSort(arr,low,p-1);quickSort(arr,p+1,high);}A.O(n)B.O(logn)C.O(n2)D.O(nlogn)答案：C。解析：该快速排序算法以首元素为基准，如果输入是有序或接近有序的数组，将导致每次分区一边为空，另一边为n-1个元素，递归深度达到n。在这种情况下，比较和交换次数总量为1+2+…+(n-1)≈O(n2)。因此最坏情况的时间复杂度是O(n2)，正确答案为C。11.下面代码尝试在有序数组中查找第一个大于等于x的元素位置。如果没有大于等于x的元素，返回arr.size()。以下说法正确的是（）。intlower_bound(vector<int>&arr,intx){intl=0,r=arr.size();while(l<r){intmid=l+(r-l)/2;if(arr[mid]>=x)r=mid;elsel=mid+1;}returnl;}A.上述代码逻辑正确B.上述代码逻辑错误，while循环条件应该用l<=r。C.上述代码逻辑错误，mid计算错误。D.上述代码逻辑错误，边界条件不对。答案：A。解析：该代码实现的是典型的二分查找中“lower_bound”功能。在有序数组中查找第一个大于等于x的位置；若不存在，则返回arr.size()。循环条件使用l<r，将区间[l,r)不断缩小；mid计算方式可避免整数溢出。当arr[mid]>=x时收缩右边界，否则收缩左边界。结束时l正好为目标位置。因此逻辑正确，选项A正确。12.小杨要把一根长度为L的木头切成K段，使得每段长度小于等于x。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小x（x为正整数），则横线处应填写（）。//判断：在不超过K次切割内，是否能让每段长度<=x。boolcheck(intL,intK,intx){intcuts=(L-1)/x;returncuts<=K;}//二分查找最小可行的binary_cut(intL,intK){intl=1,r=L;while(l<r){intmid=l+(r-l)/2;________________________________//在此处填入代码。}returnl;}intmain(){intL=10;//木头长度。intK=2;//最多切K刀。cout<<binary_cut(L,K)<<endl;return0;}A.if(check(L,K,mid))r=mid;elsel=mid+1;B.if(check(L,K,mid))r=mid+1;elsel=mid+1;C.if(check(L,K,mid))r=mid+1;elsel=mid-1;D.if(check(L,K,mid))r=mid+1;elsel=mid;答案：A。解析：该问题是典型的“二分答案”求最小可行值。若check(L,K,mid)为真，说明当前mid已满足条件，可以尝试更小的值，让r=mid。若为假，则mid太小，需要增大，令l=mid+1。这样最终l会收敛到最小可行的X。选项A正确，其余选项边界更新方向错误，会导致结果不正确或死循环。13.下面给出了阶乘计算的两种方式。以下说法正确的是（）。intfactorial1(intn){if(n<=1)return1;returnn*factorial1(n-1);}intfactorial2(intn){intacc=1;while(n>1){acc=n*acc;n=n-1;}returnacc;}A.上面两种实现方式的时间复杂度相同，都为O(n)。B.上面两种实现方式的空间复杂度相同，都为O(n)。C.上面两种实现方式的空间复杂度相同，都为O(1)。D.函数factorial1()的时间复杂度为O(2n)，函数factorial2()的时间复杂度为O(n)。答案：A。解析：两种实现都要对n进行一次逐步递减的乘法运算，调用次数或循环次数都是n次，因此时间复杂度均为O(n)，A正确。递归实现factorial1()每次调用会在调用栈上存储局部变量和返回地址，空间复杂度为O(n)。迭代实现factorial2()只需常量额外空间，空间复杂度为O(1)。因此B、C都错误，D中递归的时间复杂度不是O(2n)。正确答案是A。14.给定有n个任务，每个任务有截止时间和利润，每个任务耗时1个时间单位、必须在截止时间前完成，且每个时间槽最多做1个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（）。structTask{intdeadline;//截止时间。intprofit;//利润。};voidsortByProfit(vector<Task>&tasks){sort(tasks.begin(),tasks.end(),[](constTask&a,constTask&b){returnfit>fit;});}intmaxProfit(vector<Task>&tasks){sortByProfit(tasks);intmaxTime=0;for(auto&t:tasks){maxTime=max(maxTime,t.deadline);}vector<bool>slot(maxTime+1,false);inttotalProfit=0;for(auto&task:tasks){for(intt=task.deadline;t>=1;t--){if(!slot[t]){_______________________//在此处填入代码。break;}}}returntotalProfit;}A.slot[t]=true;totalProfit+=fit;B.slot[t]=false;totalProfit+=fit;C.slot[t]=true;totalProfit=fit;D.slot[t]=false;totalProfit=fit;答案：A。解析：此题是贪心策略为：按利润从高到低排序任务，并在其截止时间之前找一个空闲时间槽安排。当找到可用的时间槽t时，应将该时间槽标记为已占用slot[t]=true，并累加该任务的利润totalProfit+=fit。选项A符合该逻辑，其余选项要么不标记占用，要么利润累减，均不正确。因此答案是A。15.下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（）。vector<int>add(vector<int>a,vector<int>b){vector<int>c;intcarry=0;for(inti=0;i<a.size()||i<b.size();i++){if(i<a.size())carry+=a[i];if(i<b.size())carry+=b[i];_______________________//在此处填入代码。}if(carry)c.push_back(carry);returnc;}A.c.push_back(carry/10);carry%=10;B.c.push_back(carry%10);carry/=10;C.c.push_back(carry%10);D.c.push_back(carry);carry/=10;答案：B。解析：高精度加法按位相加并处理进位，本题数组低位在前，因此每次的当前位结果是carry%10，进位是carry/10。选项B完整地把当前位压入结果数组，并更新进位，符合高精度加法逻辑。A中用carry/10压入结果是错误的。C没有更新进位。D把完整carry压入结果也是错误的。因此正确答案是B。二、判断题（每题2分，共20分）。16.数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。（）。答案：错误。解析：链表的优点是插入、删除元素时不需要像数组那样移动大量元素，只需修改指针即可完成操作。但链表不能随机访问元素，查找某个特定位置的元素必须从头节点顺序遍历，时间复杂度为O(n)。因此题中“并且能随机查找”这一说法错误，故答案为错误。17.假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm(a，b)函数能正确找到两个正整数a和b的最小公倍数。（）。intlcm(inta,intb){returna/gcd(a,b)*b;}答案：正确。解析：两个正整数a和b满足关系：a×b=gcd(a,b)×lcm(a,b)，因此图片。代码中先计算a/gcd(a,b)，再乘以b，避免大数乘法直接导致溢出，逻辑正确。故答案为正确。18.在单链表中，已知指针p指向要删除的结点（非尾结点），想在O(1)删除p，可行做法是用p->next覆盖p的值与next，然后删除p->next。（）。答案：正确。解析：在单链表中，如果我们要删除的节点p已知，但它不是尾节点时，传统做法需要找到它的前驱节点才能修改指针，这通常要从链表头遍历，时间复杂度是O(n)。但是这里有一个“巧妙”的O(1)方法。首先，把p的下一个节点p->next的数据和p->next的指向复制到p。这样p看起来就变成了它的下一个节点（数据和next都相同）。然后释放原本的p->next节点，相当于直接跳过该节点。本质上，这种方法不是直接删除p，而是用p->next覆盖p，然后删除原来的下一个节点，从整体链表来看，原本位置的节点被移除，且无需从头查找前驱，因此可以O(1)完成。19.在求解所有不大于n的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(nloglogn)。（）。答案：错误。解析：虽然线性筛法（欧拉筛）的理论时间复杂度是O(n)，而埃氏筛法是O(nloglogn)，看上去线性筛法更优，但在实际运行中，由于常数因子、缓存局部性等因素，埃氏筛法在多数情况下会更快且实现更简单。另外，小规模n时两者复杂度差异微乎其微，因此并不是所有情况下都优先使用线性筛法。题中“都应当优先使用”的绝对说法是错误的，故答案为错误。20.二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。（）。答案：正确。解析：二分查找依赖数据的有序性才能正确定位元素，在无序数据上无法直接使用。如果只是进行一次查找，把数据先排序的时间复杂度为O(nlogn)，而一次线性查找只需O(n)，通常排序的成本会超过二分带来的查找效率提升。因此在这种情况下不划算，题中结论正确，故答案为正确。21.通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。（）。答案：正确。解析：快速排序的性能依赖于枢轴选择的质量，若枢轴使分区极不均衡（如已经有序数组取首元素为枢轴），会导致最坏复杂度O(n2)。从首元素、中间元素和末元素中选出中间大小的值作为枢轴，可以避免枢轴过偏，提升分区平衡性，从而降低进入最坏情况的概率。这种方法在实践中可以明显提高快速排序的平均性能，故答案为正确。22.贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。（）。答案：正确。解析：贪心算法的核心思想是在每一步选择中，都选取当前看起来最优的局部解，并且不再回溯检查之前的决策，它适用于具有贪心选择性质和最优子结构的问题。分治算法的思想是把原问题拆分成若干个规模更小的子问题，分别独立求解，再将子问题的解合并，得到原问题的解；适用于问题可以自然分割，且各子问题结构相似的情况。题述准确地概括了两者的本质区别，因此答案为正确。23.以下fib函数计算第n项斐波那契数（fib(0)=0,fib(1)=1），其时间复杂度为O(n)。（）。intfib(intn){if(n<=1)returnn;returnfib(n-1)+fib(n-2);}答案：错误。解析：该实现是朴素递归版本的斐波那契数计算。每次调用fib(n)会递归计算fib(n-1)和fib(n-2)，而这些子问题又会重复计算大量相同的子结果。递归调用树的规模呈指数增长，时间复杂度O(φn)，其中φ≈1.618（即黄金分割比），而不是O(n)。若要达到O(n)的时间复杂度，需要使用循环或带记忆化的递归。因此题中说法错误，答案为错误。24.递归函数一定要有终止条件，否则可能会造成栈溢出。（）。答案：正确。解析：在程序运行时，函数调用的信息（如参数、返回地址、局部变量等）会存放在调用栈中。递归调用每深入一层，都会在栈上压入一帧。如果递归没有终止条件或终止条件始终无法满足，就会无限地调用自身，使调用栈越来越深。调用栈的空间是有限的，当压入的栈帧数量超过该空间时，就会发生栈溢出（stackoverflow），造成程序崩溃或运行异常。25.使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。（）。答案：错误。解析：贪心算法在每一步选择中只考虑当前看起来最优的方案，不进行回溯，因此并不能保证所有问题都能得到全局最优解。它只能在满足贪心选择性质（全局最优可以由每一步的局部最优构成）和最优子结构的问题中保证最终解是全局最优。对于不满足这些性质的问题，贪心可能得到次优甚至错误的解。因此题目的绝对表述“最终一定能找到全局最优解”是错误的，答案为错误。三、编程题（每题25分，共50分）。26.试题名称：数字移动。时间限制：1.0s。内存限制：512.0MB。题目描述：小A有一个包含N个正整数的序列A={A1,A2…AN}，序列A恰好包含N/2对不同的正整数。形式化地，对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。小A希望每对相同的数字在序列中相邻，为了实现这一目的，小A每次操作会选择任意i（1≤i≤N），将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。例如，假设序列A={1,2,1,3,2,3}，小A可以选择i=2，将A2移动到A3的后面，此时序列变为A={1,1,2,3,2,3}，耗费2点体力。小A也可以选择i=3，将A3=1移动到A2=2的前面，此时序列变为A={1,1,2,3,2,3}，花费1点体力。小A可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小A希望你能帮他计算出一个最小的x，使得他能够在每次花费的体力均不超过x的情况下令每对相同的数字在序列中相邻。输入格式：第一行一个正整数N，代表序列长度，保证N为偶数。第二行包含N个正整数A1,A2…AN，代表序列A。且对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。数据保证小A至少需要执行一次操作。输出格式：输出一行，代表满足要求的x的最小值。输入样例。输出样例。数据范围：对于40%的测试点，保证1≤N,Ai≤100。对于所有测试点，保证1≤N,Ai≤105。参考程序。#include<iostream>usingnamespacestd;constintN=100010;inta[N];intb[N];intpos;intmain(){intn;cin>>n;for(inti=0;i<n;i++){cin>>a[i];}intleft=1,right=1e6,ans=1e6;while(left<=right){intmid=(left+right)/2;boolpossible=true;pos=0;for(inti=0;i<n;i++){if(a[i]>mid){b[pos++]=a[i];}}for(inti=0;i<pos;i+=2){if(b[i]!=b[i+1]){possible=false;break;}}if(possible){ans=mid;right=mid-1;}else{left=mid+1;}}cout<<ans<<endl;return0;}解析：40%部分分可以采用枚举+验证的方法，枚举上限ans，验证该上限时能否达成目标；时间复杂度为O(N.max(Ai))。验证的逻辑：当力气上限是ans时，所有≤ans的数都可以任意移动，因此这些数必然可以相邻。验证的关键在于＞ans的数，这些数的位置是固定不能移动的。对于初始位置不相邻的>ans的一组数对，其之间所有≤ans的数都可以移走，但是如果有其他>ans的数不能移走，就证明力气上限ans无法达成，需要将ans变大，重新验证。例：(1323)，两个3之间存在一个2。假设最大只能挪动1，则不论如何，两个3之间的2不会被挪动，最终无法完成任务。实现方法为先用列表b按顺序存储所有大于上限的数，遍历列表b，如果相邻两项(b[i],b[i+1])不是相同的数，表明其中间有其他无法移动的数，判断任务失败；遍历完成没有提前终止循环，则证明任务成功。100%满分做法可以发现，上限ans越大，可以移动的数越大，当上限=ans可以完成任务时，上限>ans一定也可以完成任务；反之，上限=ans不可以完成任务时，上限<ans一定也不可以完成任务，存在单调性，因此可以使用二分枚举上限ans，时间复杂度优化为O(N·log(max(ai)))。27.试题名称：相等序列。时间限制：1.0s。内存限制：512.0MB。题目描述：小A有一个包含N个正整数的序列A