老师已为大家备好电子打印版，需要完整电子版文件的朋友，可以拉到文末查看。 【答案解析】
1.解释：答案选C。 考察数组与链表的相关知识。存储相同数目的整数的时候，数组用的内存应该是更少的，因为数组不需要记录下一个值的地址。 2.解释：答案选D。 选项A，最后一句，此时为 p->next已经变成了 s ，所以错了；选项B，最后一句，此时为 p->next 已经变成了 s ，所以错了； 选项C，最后一句，应该是 s->next->prev= s。选项D正确。 3.解释：答案选C。
本题考察递推与递归的相关概念。sumA() 函数是递推，sumB() 函数是递归，两个函数都是求 1~n 的和，两个函数的时间复杂度基本一致，都是O(n)。
4.解释：答案选C。
本题考察欧几里得算法(辗转相除法)的相关概念。函数为辗转相除求两数的最大公约数，结果为 4 ，如果没有看出函数作用，也可以手动模拟递归过程。
5.解释：答案选C。
本题考察埃氏筛的相关知识点。第六行判断当前的 i 是质数，所以 i 的倍数一定不是质数，这里要枚举 i 的所有的倍数。
6.解释：答案选A。
本题考查欧拉筛的相关知识点。这个地方是要枚举质数表，然后把质数的 i 倍数都筛掉，所以应该是选A。
7.解释：答案选C。
第12行的代码是要枚举所有的质因子，时间复杂度为O(√n)，第13行的while() 循环的作用为枚举包含多少个当前的质因子，时间复杂度为O(logn)。
8.解释：答案选A。
本题考查快速幂的相关知识。题干代码解释如下——
如果指数 n为0，任何数的0次幂都是1，所以直接返回1；如果指数 n为1，任何数的1次幂都是它本身，所以直接返回x；对于其他情况，函数会递归地计算 x的n/2次幂，然后将这个结果平方，如果n是奇数，还需要乘以一个额外的x。题干的代码属于快速幂的朴素写法，算法时间复杂度是
O(n)。如果按照下面的代码，可以将时间复杂度进一步降为O(logn)——doublequick_power(double x, unsigned n){if (n == 0) return1;if (n == 1) return x;double half_power = quick_power(x, n / 2);return half_power * half_power * ((n & 1) ? x : 1);}9.解释：答案选C。 详细解析见下图——
相关知识点的复习与拓展：
截至考试当年9月，关于快速的实现原理，可以参考下面视频所示，加深理解—— 10.解释：答案选B。
本题考察归并排序的实现。
函数 merge_sort 的作用是递归进行分治的过程，每次把序列分成两半，然后分别处理，merge 函数的作用是把两个有序序列，通过双指针操作，合并为一个有序序列。merge 函数的调用次数，先是两个数的合并，执行次数为n/2，然后是4个数合并，执行次数为n/4……故，时间复杂度大约为O(n)。
11.解释：答案选B。
本题考察对贪心算法的理解。重量已经按照从小到大排序了，然后双指针处理，双指针的过程为最轻的人和最重的人尝试能否在同一个船上，如果可以，那么他们在同一个船上，否则，当前最重的人不能和其他人在一个船上，得单独一条船。采用的是贪心的思想。
12.解释：答案选A。
本题考察分治算法的理解，的思想就是把问题划分成子问题，然后继续划分，知道子问题可以直接解决，然后合并子问题得到的结果，推到原问题的答案。
选项B，归并排序的思想就是分治；
选项C，规模越大的问题同样适合分治思想；
D选项，分治算法划分子问题的时间一般为O(logn)，总的时间复杂度常为O(nlogn)，如归并排序。
13.解释：答案选C。
详细解析见下图——
14.解释：答案选C。
本题考察高精度算法的相关知识点。选项C错误，因为对于高精度的乘法，运算时间和两个整数的长度之和有关，两个长度分别为 len1 和 len2 的整数相乘，结果的长度至少为
len1+len2。15.解释：答案选C。
如下图，根据题干代码，画出递归树，手搓模拟即可——
【答案解析】
1.解释：正确。 进程是循环的，一个进程的时间片用完之后，进行下一个进程，所以进程可以用循环链表实现。 相关知识点的复习与拓展：
截止考试当年9月，有关进程与线程的理解，可以参考下图——
2.解释：正确。 本题考察质数筛法的相关知识。常见的质数筛有埃氏筛和欧拉筛(线性筛法)，其中埃氏筛的时间复杂度为O(nlogn)，经过一定的优化，可以到O(nloglogn)，欧拉筛的时间复杂度为O(n)，大部分情况下，欧拉筛的效率更高。 3.解释：错误。
根据唯一分解定理，任何一个大于等于2的整数，都可以唯一的分解为若干个质数的幂次方的乘积的形式。
4.解释：错误。
贪心算法的使用条件是：局部最优能够得到全局最优，但是，并不是所有的问题都可以通过贪心实现，因为局部最优不一定能得到全局最优。
5.解释：错误。
快速排序的平均时间复杂度为O(nlogn)，归并排序的时间复杂度是稳定的O(nlogn)，所以对于时间复杂度的描述是正确的，但是快速排序不是稳定排序。
相关知识点的复习与拓展：
截至考试当年9月，有关十大经典排序的特点对比，可以参考下面的图片——
6.解释：错误。
插入排序的时间复杂度为O(n²)，快速排序的平均时间复杂度为O(nlogn)，但是，快速排序的最坏情况下，时间复杂度也是O(n²)。
7.解释：正确。
分治算法的思想就是把问题划分成子问题，然后继续划分，知道子问题可以直接解决，然后合并子问题得到的结果，推得原问题的答案，分治提高了算法的效率，减少了操作数量。
8.解释：正确。
二分查找的前提条件是，序列有序。
9.解释：正确。
递归会占用栈空间，而栈空间往往不是很大，递归层数过多的时候，可能会导致栈溢出。
相关知识点的复习与拓展：
截至考试当年9月，有关C++程序的内存分配，可以参考下面的图片——
10.解释：错误。
递归是指的函数不断的调用自身，直到当前传参可以得到结果，并返回结果，递归应该是一个从大问题到小问题的分解，然后小问题有了结果并返回，解决大问题，而题干这个写法只能算是函数嵌套使用。
#include<bits/stdc++.h>using namespace std;intmain(){long long n,m,maxn=-1e5,o;//maxn一定要小！cin>>n>>m;for(long long i=1; i<=n; i++){cin>>o;if(o>maxn) maxn=o;//打擂台}for(long long j=1; j<=m; j++){cin>>o;if(o>0 || n==1) maxn+=o;}cout<<maxn;return 0;}
代码思路解析——对于每一个武器，我们用 maxn 来记录熟练度最高的一个。接着每输入一场比赛的熟练值，就判断是不是正数，是就给 maxn 加上。这样，就能保证 maxn 是最大的。不过，要小心的是，当 n 为 1 时，只有一个武器，熟练值不管是不是正数都要加。
GESP 2024年9月 C++五级 挑战怪物
#include<bits/stdc++.h>using namespace std;boolprime(int x){for(int i=2;i*i<=x;i++){if(x%i==0) return false;}return true;}intmain(){int t;cin >> t;while(t--){int n;bool flag=false;//标记血量是否被打到0cin >> n;int w=1,ans=0;//w表示物理攻击伤害，ans是答案while(n>0){if(n<=0) break;//没血量了，退出if(prime(n)){//是个质数，一击必杀ans++;flag=1;break;}n-=w;//否则就是物理伤害w*=2;//伤害翻倍ans++;//次数加一}if(flag) cout << ans;//如果打死了就输出结果else cout << -1;//否则输出-1cout << endl;}return 0;}
代码思路解析——
学习路径——
需要无水印PDF格式文件的朋友，欢迎扫下面二维码加好友垂询。
▍ 声明：本文整理自网络，如有侵权，请联系删除。
本公号刊载此文，是出于合法合理地分享和传播信息，扩大大受众范围，促进学术交流，推动共同进步之目的。公众号持有人郑重声明，本文的发布，将严格遵守相关规定和法律法规，不侵犯任意潜在作者的权益，不改变引用原文（若有）的意图和内容。若有来源标注错误或侵犯了您的合法权益，请随时与我们联系协商，联系（QQ）：993225721，我们将及时更正、删除。文章若有幸得到转载，首先，公众号持有人感谢转载人为读者阅读提供了有价值的信息和知识，希望文章能够在被转载的平台上得到更广泛的传播和交流；其次，转载人应充分考虑到转载动作本身所可能带来的相应的风险和责任，包括但不限于侵犯知识产权、侵犯他人权益等行为所引起的法律责任，确保本文的合法传播和使用。同时，本人也极其愿意在转载过程中尽力配合转载人了解、关注、规避、消除相关的潜在风险。若转载人有相任何关疑虑，同样欢迎随时与我们联系协商，联系（QQ）：993225721。 喜欢您关注我们哦——
