GESP第五次认证真题解析|C++五级真题回顾

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

1、唯一分解定理描述的内容是(         )？

A.任意整数都可以分解为素数的乘积

B.每个合数都可以唯一分解为一系列素数的乘积

C.两个不同的整数可以分解为相同的素数积

D.以上都不对

【答案】B

【考纲知识点】唯一分解定理

【解析】任何一个大于1的整数n都可以分解成若干个素因数的连乘积，若n为素数，则乘积为n本身，若n为合数,则乘积包含若干素数的乘积。

2、贪心算法的核心思想是(         )。

A.在每一步选择中都做当前状态下的最优选择

B.在每一步选择中都选择局部最优解

C.在每一步选择中都选择全局最优解

D.以上都对

【答案】A

【考纲知识点】贪心算法

【解析】贪心算法核心思想是选择当前状态下的最佳选择，动态规划的核心思想应该是“最优子结构”和“重叠子问题”

3、下面的c++代码片段用于计算阶乘。请在横线处填入(  )，实现正确的阶乘计算。

A.return n*factorial(n-1);

B.return factorial(n-1)/n;

C.return n*factorial(n);

D.return factorial(n/2)*factorial(n/2);

【答案】A

【考纲知识点】递归算法

【解析】由递归式,if(n>=2)return fact[n-1]*n;

4、下⾯的代码⽚段⽤于在双向链表中删除⼀个节点 。请在横线处填⼊（）  ，使其能正确实现相应功能。

A.if(current->next!=nullptr) current->next->prev = current->prev;

B.current->prev->next = current->next;

C.delete current->next;

D.current->prev=current->next;

【答案】B

【考纲知识点】链表

【解析】

双链表current的删除需要处理两个指针

current的前驱的next指针更新到prev的后继

current的后继的prev指针更新到current的前驱

空白处需要填写的是 将current的前驱的next更新为current的next

A更新的是current的后继显然不对,C是删除了current的后继，D更新的是current的前驱 而不是前驱的next

5、辗转相除法也被称为（   ）。

高斯消元法

费马定理

欧几里得算法

牛顿迭代法

【答案】C

【考纲知识点】辗转相除法

【解析】

高斯消元法 是线性代数中求解线性方程组的一种求解方法

费马定理 分为费马小定理和费马大定理 是初等数论中的两个重要原理。

欧几里得算法 又称辗转相除法是求解最大公约数的一种算法 另一种算法为更相减损法是出自《九章算术》中 中国古代提出的一种最大公约数的算法

牛顿迭代法 又称牛顿-拉夫逊（拉弗森）方法，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

6、下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（   ）。

A.

B.

C.

D.

【答案】C

【考纲知识点】算法复杂度的估计

【解析】

斐波那契递推式为:f(n)=f(n-1)+f(n-2),结合递归树，以最坏的情况考虑，f(n)每次减少1的问题规模需要变为两个分支，记为f(n)=2¹f(n-1)=2²f(n-2)=…=2^n-1f(1)=2^n-1，因此复杂度为O(2ⁿ)。

7、下⾯的代码⽚段⽤于将两个⾼精度整数进⾏相加 。请在横线处填⼊（）  ，使其能正确实现相应功能。

A.result =to_string(sum%10)+result

B.result=to_string(carry%10)+result

C.result=to_string(sum/10)+result

D.result=to_string(sum%10+carry)+result

【答案】A

【考纲知识点】数组模拟高精度

【解析】

string下标0的位置对应num1和num2的最高位,模拟加法从个位开始，第4行的i,j两个指针指向了num1和num2的数组最高下标，对应个位;

第5行自低位向高位模拟加法计算，同时保证了:只要有其中一个数参与加法或者最终产生更高进位carry就执行技法。

第6,7行将字符转换为数字，同时若有一方已超过位数，补0参与加法运算。

第8行为模拟计算，第9行为处理进位，第10行处理当前位为sum%10

同时程序返回了string类型的result,输出result时自高位向低位进行，新的位sum需要在右侧衔接result

8、给定序列：1 ，3，6 ，9，17 ，31，39 ，52，61 ，79，81 ，90，96。使⽤以下代码进⾏⼆分查找查找元素82 时 ，需要循环多少次， 即最后输出的 times 值为（） 。

A. 2

B. 5

C. 3

D. 4

【答案】D

【考纲知识点】二分查找

【解析】82并没有出现在序列中，二分的层数如下，对[L,R],mid将区间分为了:

[L,mid-1],mid,[mid+1,R]三个部分，每向下一层times都需要自增一次；

time=1 left =0 mid=6 right=12

time=2 left =7 mid=9 right=12

time=3 left =10 mid=11 right=12

time=4 left =10 mid=10 right=10

共需四次，也是图中的红色的查找路线。

9、下⾯的代码⽚段⽤于判断⼀个正整数是否为素数 。请对以下代码进⾏修改 ，使其能正确实现相应功能 。  ()

A. num < 2 应该改为  num <= 2

B.循环条件  i * i < num 应该改为  i * i <= num

C.循环条件应该是  i <= num

D.循环体中应该是  if (num % i != 0)

【答案】B

【考纲知识点】素数判定

【解析】对于判断n是否为素数，如果整数k是n的一个约数，那么n/k也是n的一个约数，k和n/k必然满足，一个小于等于sqrt（n），另一个大于等于sqrt(n)，sqrt(n)为根号n。所以只要判断n是否能被2,3…sqrt(n)中的一个数整除，即可判定n是否为素数，时间复杂度为O(sqrt(n))。

I≤sqrt(n) 或者i*i≤n

10、在埃拉托斯特尼筛法中 ，要筛选出不⼤于  n 的所有素数 ，最外层循环应该遍历什么范围  ()   ?

A.  for (int i = 2; i <= n; ++i)

B.  for (int i = 1; i < n; ++i)

C.  for (int i = 2; i <= sqrt(n); ++i)

D.  for (int i = 1; i <= sqrt(n); ++i)

【答案】C

【考纲知识点】素数表的埃式筛法

【解析】下图就是埃式筛法的过程；因此i只需进行到sqrt(n)即可；程序第15行进行了超过sqrt(n)部分的质数统计；

11、素数的线性筛法时间复杂度为（） 。

A. O(n);

B. O(nloglogn)

C. O(nlogn)

D. O(n²)

【答案】A

【考纲知识点】素数表的线性筛法

【解析】线性筛法(欧拉筛)是一个能够做到O(n)的时间复杂度，也就是线性的质数筛法，是目前性能最优秀的质数筛法。一秒钟可以处理1e8范围的质数;B选项为埃式筛法的复杂度，一秒钟可以处理2e7范围内的质数。

12、归并排序的基本思想是（） 。

A. 动态规划

B. 分治

C. 贪⼼算法

D. 回溯算法

【答案】B

【考纲知识点】分治算法(归并排序和快速排序)

【解析】归并排序基于分治思想时间复杂度为O(N *logN),空间复杂度为O(N)；

13、在快速排序中，选择的主元素（pivot）会影响算法的（） 。

A. 不影响

B. 时间复杂度

C. 空间复杂度

D. 时间复杂度和空间复杂度

【答案】B

【考纲知识点】分治算法(归并排序和快速排序)

【解析】快速排序平均复杂度为O(N *logN)，对区间[L,R],每次选出主元素pivot，将区间划分为两部分，左侧子区间≤pivot,右侧子区间>pivot，如果排序过程中这两个子区间一直比较均衡，则快速排序复杂度达到最优为O(nlogn)，比较极端时，某一个子区间一直不存在，此时排序复杂度达到上界O(n²)

14、递归函数在调⽤⾃⾝时 ，必须满⾜（） ， 以避免⽆限递归？

A.有终⽌条件

B.函数参数递减（或递增）

C.函数返回值固定

D.以上都对

【答案】A

【考纲知识点】递归

【解析】一个问题要用递归算法来解决，须满足以下三个条件：

1.能自己调用自己；

2.调用自己时问题规模有规律地递减；

3.有递归终止条件，也就是经过有限次调用，问题得到解决。

15、假设给定链表为: 1->3->5->7->nullptr，若调⽤searchValue(head, 5) ，函数返回值为（） 。

A.返回 1

B.返回 0

C.死循环 ，⽆法返回

D.返回 - 1

【答案】A

【考纲知识点】单链表

【解析】5在单链表中存在，因此函数返回1

判断题(每题2分，共20分)

1、辗转相除法⽤于求两个整数的最⼤公约数。

【答案】正确

【考纲知识点】辗转相除法

【解析】欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述这种算法,被命名为欧几里得算法。

2、插⼊排序的时间复杂度是O(NlogN)。

【答案】错误

【考纲知识点】排序算法(插入排序)

【解析】插入排序的时间复杂度在平均情况下为O(n²)，最好情况下的时间复杂度为O(n)，最坏情况下的时间复杂度为O(n²)。这是因为：

平均情况：当待排序数组中的元素分布较为均匀时，插入排序需要进行的比较次数大约是输入规模的一半，即O(n²)。

最好情况：如果待排序数组已经是有序的，那么插入排序只需进行n-1次比较即可完成排序，此时的时间复杂度为O(n)。

最坏情况：当待排序数组是完全逆序的，即所有元素都比前一个元素大（或小），此时需要进行的比较次数达到最大，即1+2+3+…+N-1，总次数为N(N-1)/2，因此时间复杂度为O(n²)。

3、⼆分查找要求被搜索的序列是有序的 ，否则⽆法保证正确性。

【答案】正确

【考纲知识点】二分查找

【解析】二分查找的前提是查找的数据具备单调性

4、使⽤贪⼼算法解决问题时 ，每⼀步的局部最优解⼀定会导致全局最优解。

【答案】错误

【考纲知识点】贪心算法

【解析】贪心算法(greedy algorithm)又称贪婪算法)是一种常用的算法设计思想，用于解决最优化问题。基本思想是通过每一步的局部最优选择来达到全局最优解。

5、分治算法的核⼼思想是将⼀个⼤问题分解成多个相同或相似的⼦问题进⾏解决 ，最后合并得到原问题的解。

【答案】正确

【考纲知识点】分治算法(归并排序和快速排序)

【解析】分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的精髓：

分--将问题分解为规模更小的子问题；

治--将这些规模更小的子问题逐个击破；

合--将已解决的子问题合并，最终得出“母”问题的解

6、分治算法的典型应⽤之⼀是归并排序 ，其时间复杂度为O(N *logN),。

【答案】正确

【考纲知识点】分治算法(归并排序和快速排序)

【解析】归并排序基于分治思想

时间复杂度为O(N *logN),空间复杂度为O(N)；

7、素数表的埃⽒筛法和线性筛法的时间复杂度都是O(NlogN)。

【答案】错误

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】线性筛法(欧拉筛)是一个能够做到O(n)的时间复杂度，也就是线性的质数筛法，是目前性能最优秀的质数筛法。一秒钟可以处理1e8范围的质数;埃式筛法的复杂度为O(NloglogN)，一秒钟可以处理2e7范围内的质数。

8、贪⼼算法是⼀种可以应⽤于所有问题的通⽤解决⽅案。

【答案】错误

【考纲知识点】贪心算法

【解析】贪心算法核心思想是选择当前状态下的最佳选择，动态规划的核心思想应该是“最优子结构”和“重叠子问题”。贪心不能解决动态规划类问题。

9、单链表和双链表都可以在常数时间内实现在链表头部插⼊或删除节点的操作。

【答案】正确

【考纲知识点】单链表、双链表

【解析】无论是单链表还是双链表，头结点是一开始就可以访问的，做链表的插入操作即可。

10、在C语⾔中 ，递归的实现⽅式通常会占⽤更多的栈空间 ，可能导致栈溢出。

【答案】正确

【考纲知识点】递归

【解析】递归调用的特点是每递归一次，就要创建一个新的栈帧，而且还要保留之前的环境（栈帧），直到遇到结束条件。所以递归调用一定要明确好结束条件，不要出现死循环，而且要避免栈太深。

三、编程题(每题25分，共50分)

1、成绩排序

问题描述

有N名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序：

1.比较总分，高者靠前；

2.如果总分相同，则较语文和数学两科总分，高者靠前；

3.如果仍相同，则比较语文和数学两科的最高分，高者靠前；

4.如果仍相同，则二人并列。

你需要输出每位同学的排名，如遇多人并列，则他们排名相同，并留空后面的-1 个名次。例如，有3名同学并列第1，则后1名同学自动成为第4名。

输入描述

第一行1个整数N，表示同学的人数。

接下来N行，每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。

保证0≤ci,mi,ei≤150。

输出描述

输出N行，按输同学的顺序，输出他们的排名。

注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名

特别提醒

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输、输出中附带任何提示信息。

样例输入1

样例输出1

数据规模

对于30%的测试点,保证N≤100，且所有的同学的总分各不相同

对于100%的测试点,保证2≤N≤10000

【题目大意】给定N个同学的语数英成绩，按照题目的要求对学生求解排名。

【考纲知识点】排序算法

【解题思路】该题目做法多样，可用结构体/pair数组/tuple等

总体流程:输入人数和对应的成绩,注意此时需要将人员的编号也存储下来,接下来按照比较优先级对人员进行排名：

优先级从高到低依次为:总分、语文数学总分、语文或数学最高分大的优先。

可以考虑用tuple,将对应的优先级数值存储后，做一次sort降序即可。

【参考程序】

2、B-smooth数

题面描述

小杨同学想寻找一种名为B-smooth数的正整数。

如果一个正整数的最大质因子不超B，则该正整数为B-smooth数。

小杨同学想知道，对于给定的n和B，有多少个不超过n的B-smooth数。

输入格式

第一行包含两个正整数n,B，含义如题面所示。

输出格式

输出一个非负整数 ，表示不超过n的B-smooth数的数量。

样例1

样例解释

在不超过10的正整数中,3-smooth数有{1,2,3,4,6,8,9},共7个。

数据范围

对于全部数据，保证有1≤n ≤10⁶，1≤B ≤10⁶。

【题目大意】给定n和B，求解有多少个<=n的最大质因子不超过B的B-smooth数

【考纲知识点】唯一分解定理

【解题思路】

①比较朴素的思路为循环遍历1~n,对于每个i，对其分解质因子，得到最大质因子，将质因子和B作比较，并统计到答案中，该算法循环复杂度为O(n),调用分解质因子的复杂度为O(sqrt(n))，总体复杂度为O(nsqrt(n)),加上需要初始化等常数操作，通过1e6的数据是比较危险的。

②考虑在筛法求素数时,对素数P，其倍数都包含素因子P,可以在筛掉素因子P的倍数的同时，用P更新这些倍数的最大素因子。埃式筛法没问题，当然也可以选择欧拉线性筛进一步将复杂度降低为线性。

【参考程序】

技术支持：查昊昊

策划：GESP技术委员会副主席 刘晓庆