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

一、单选题 (每题2分,共30分)

第1题 链表不具备的特点是( )。

A.可随机访问任何一个元素

B.插入、删除操作不需要移动元素  

C.无需事先估计存储空间大小

D.所需存储空间与存储元素个数成正比

【答案】A

【考纲知识点】链表

【解析】链表是非线性存储，顺序访问的存储结构，动态分配内存，需要从头节点遍历，不支持随机访问

第2题 双向链表中每个结点有两个指针域 prev和next，分别指向该结点的前驱及后继结点 。设 p指向链表中的 一个结点 ，它的前驱结点和后继结点均⾮空 。要删除结点p，则下述语句中错误的是（  ）。

A.

B.

C.

D.

【答案】A

【考纲知识点】链表

【解析】双链表中删除非头尾结点p，需要将p的前驱结点和p的后继结点相连后释放p结点

p的前驱节点的next需要指向p的后继结点，p的后继结点的prev需要指向p的前驱结点

p.prev.next = p.next;p.next.prev = p.prev;

C选项 因为先执行了p->next->prev = p->prev;所以p->next->prev->next等价于p->prev->next

D选项同理

第3题 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为head和tail，链表中每个结点有两个指针域 prev和next，分别指向该结点的前驱及后继结点 。下面代码实现了一个空的双向循环链表 ，横线上应填的最 佳代码是( )。

A.

B.

C.

D.

【答案】B

【考纲知识点】链表

【解析】双向循环链表中，头结点的next指针应指向尾结点，尾结点的prev指针应指向头结点，选择B选项

理论上，头结点的prev指针还要指向尾结点，尾结点的next指针指向头结点，以形成完整的循环，B选项最接近答案，足够实现一个双向循环链表

第4题 用以下辗转相除法（欧⼏⾥得算法）求gcd(84, 60)的步骤中 ，第二步计算的数是（  ）。

A. 84和60

B. 60和24

C. 24和12

D. 12和0

【答案】B

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

【解析】代入代码，第一步big=84,small=60,84%60 == 24，递归调用gcd(60,24);所以第二步计算60和24

第5题 根据唯一分解定理 ，下面整数的唯一分解是正确的（  ）。

A. 18 = 3 × 6

B. 28 = 4 × 7

C. 36 = 2 × 3 × 6

D. 30 = 2 × 3 × 5

【答案】D

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

【解析】唯一分解定理是指每一个大于1的整数都可以分解为若干个素数的乘积，A,B,C选项选项都可以继续分解，可得D选项

第6题 下述代码实现素数表的线性筛法 ，筛选出所有小于等于n的素数 ，横线上应填的最佳代码是( )。

A.  j < primes.size()

B.  i * primes[j] <= n

C.  j < primes.size() && i * primes[j] <= n   

D.  j <= n

【答案】C

【考纲知识点】线性筛法

【解析】线性筛法核心是每个合数只被最小质因数筛一次，在内层循环中会和前面筛出的所有质数相乘，所以循环范围为j < primes.size(),但同时要保证乘积在线性筛的范围内，即i*primes[j] <= n，所以选C选项

第7题 在程序运行过程中 ，如果递归调用的层数过多 ，会因为（  ）引发错误。 

A.系统分配的栈空间溢出

B.系统分配的堆空间溢出

C.系统分配的队列空间溢出

D.系统分配的链表空间溢出

【答案】A

【考纲知识点】递归

【解析】递归调用时会为分配栈空间，调用过多会导致栈溢出

第8题 对下⾯两个函数 ，说法错误的是（  ）。

A.两个函数的实现的功能相同。

B.两个函数的时间复杂度均为O(n)。

C. factorialA采用递归⽅式。

D. factorialB采用递归⽅式。

【答案】D

【考纲知识点】递归

【解析】函数A计算n的阶乘，函数B中res*=n,计算的是n的n-1次方,B函数并未进行递归

第9题 下算法中，（  ）是不稳定的排序。

A.选择排序

B.插入排序

C.归并排序

D.冒泡排序

【答案】A

【考纲知识点】排序算法

【解析】选择排序是不稳定的排序

第10题 考虑以下C++代码实现的快速排序算法 ，将数据从小到大排序 ，则横线上应填的最佳代码是( )。

A.

B.

C.

D.

【答案】B

【考纲知识点】排序算法

【解析】快速排序将待排序数组分为两部分，小于基准值和大于等于基准值

代码中i记录当前最后一个小于基准值的元素的位置，当arr[j]小于基准值时，应该将arr[j]放在i的下一个位置，也就是i++之后，将arr[j]和arr[i]交换，确保arr[i]是小于基准值的，遍历结束之后再将基准值放在i+1的位置保证左侧全部是小于基准值的，右边则是大于等于基准值的

第11题 若用⼆分法在[1, 100]内猜数 ，最多需要猜（  ）次。

A. 100

B. 10

C. 7

D. 5

【答案】C

【考纲知识点】二分查找

【解析】二分查找最多次数即为最大深度⌈log2n⌉,区间[1,100]包含100个元素，计算可得约为6点多，向上取整为7；

第12题  下面代码实现了二分查找算法 ，在数组arr找到目标元素 target的位置 ，则横线上能填写的最佳代码 是（  ）。

A.  int mid = left + (right - left) / 2;

B.  int mid = left;

C.  int mid = (left + right) / 2;

D.  int mid = right;

【答案】A

【考纲知识点】二分查找

【解析】为了避免left+right相加溢出，一般使用left + (right - left) / 2;

第13题  贪心算法的核心特征是（  ）。

A.总是选择当前最优解

B.回溯尝试所有可能

C.分阶段解决子问题

D.总能找到最优解

【答案】A

【考纲知识点】贪心算法

【解析】贪心算法的核心是局部最优解

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

A.

B.

C.

D.

【答案】D

【考纲知识点】分治算法

【解析】分治需要分成两部分分别找最大值，然后比较返回较大的一个

A选项直接返回中间值，B选项返回的是结果的和，C选项返回的是结果的积

第15题小杨编写了一个如下的高精度乘法函数 ，则横线上应填写的代码为（  ）。

A.  int temp = c[k];

B.  int temp = c[k] + carry;

C.  int temp = c[k] - carry;

D.  int temp = c[k] * carry;

【答案】B

【考纲知识点】高精度

【解析】c[k]为当前这位相乘之后的结果，15行部分在处理进位，需要将当前位的值c[k]与前一位的进位值carry相加，然后更新当前位的值为temp%10，并将新的进位值设置为temp/10。

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

第1题 要删除单链表中删除某个结点 p (⾮尾结点)，但不知道头结点 ，可行的操作是将p->next的数据拷贝到p的数据部分，将p->next设置为p->next->next ，然后 删除 p->next。

【答案】对

【考纲知识点】链表

【解析】因为不知道头结点，无法更新head，所以可以将p->next的值赋给p，这样就变为了删除p的下一个结点，无需更改头结点

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

【答案】错

【考纲知识点】链表

【解析】链表是非线性的，可用存储单元不需要连续

第3题 线性筛相对于埃拉托斯特尼筛法 ，每个合数只会被它的最小质因数筛去一次， 因此效率更⾼ 。

【答案】对

【考纲知识点】线性筛法

【解析】线性筛每个合数只被最小质因数筛掉，复杂度O(n)，埃筛复杂度O(nlog log n)

第4题 贪心算法通过每一步选择当前最优解 ，从而一定能获得全局最优解。

【答案】错

【考纲知识点】贪心算法

【解析】贪心算法不保证一定全局最优解，比如01背包问题

第5题 递归函数必须具有一个终止条件， 以防止无限递归。

【答案】对

【解析】递归需要有边界条件和递归式

第6题 快速排序算法的时间复杂度与输入是否有序无关 ，始终稳定为O(nlogn)。

【答案】错

【考纲知识点】排序算法

【解析】快速排序最坏情况为O(n^2），比如输入已经有序且每次选择的都是第一个元素作为基准

第7题 归并排序算法的时间复杂度与输入是否有序无关 ，始终稳定为O(nlogn)。

【答案】对

【考纲知识点】排序算法

【解析】归并排序不受输入数据的影响

第8题 ⼆分查找适用于对无序数组和有序数组的查找。

【答案】错

【考纲知识点】二分查找

【解析】二分查找适用于有序数组

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

【答案】错

【考纲知识点】贪心算法

【解析】采用的是贪心

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

【答案】对

【考纲知识点】归并算法

【解析】归并的基本原理

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

3.1     编程题1

.  时间限制：1.0 s

.  内存限制：512.0 MB

3.1.1  平均分配

3.1.2   题目描述

小A有2n件物品 ，小B和小C想从小A⼿上买走这些物品 。对于第 i件物品 ，小B会以b_i的价格购买 ，而小C会 以 c_i的价格购买 。为了平均分配这 2n件物品 ，小A决定小B和小C各自只能买走恰好n件物品 。你能帮小A求出 他卖出这 2n件物品所能获得的最大收入吗？

3.1.3    输入格式

第一行，一个正整数 n。

第⼆行，2n个整数b₁, b₂,....,b_2n。

第三行，2n个整数c1 , c₂,....,c_2n。

3.1.4    输出格式

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

3.1.5    样例

3.1.5.1    输入样例1

3.1.5.2    输出样例1

3.1.5.3    输入样例2

3.1.5.4    输出样例2

3.1.6    数据范围

对于20%的测试点 ，保证 1 ≤ n ≤ 8。

对于另外20%的测试点 ，保证 0 ≤ b_i≤ 1 ，0 ≤ c_i≤ 1 。

对于所有测试点 ，保证 1 ≤ n ≤ 10⁵，0 ≤ b_i≤ 10⁹，o ≤ c_i≤ 10⁹。

【题目大意】

有2n个物品，每个物品卖给A,B的价格不同，必须分别卖给A,B各n件物品，每件物品只能卖一次，问最后的售价最高是多少

【考纲知识点】

模拟算法，sort排序

【思路分析】

先假设所有物品都卖给一个人，比如A，得到收益sumA,接下来计算每个物品卖给B和卖给A的差价c_i=b_i-a_i，将差价从高到低排序，最高的n个选择卖给B，得到的差价和sumB,最后的收益就是全部卖给A的收益加上差价最高的n件物品的差价和

3.1.7    参考程序

3.2     编程题2

.  时间限制：1.0 s

.  内存限制：512.0 MB

3.2.8    原根判断

3.2.9    题目描述

小A知道 ，对于质数 p而⾔，p的原根g是满⾜以下条件的正整数：

.   1 < g < p；

.  g^p-1mod p = 1 ；

对于任意1 ≤ i < P-1均有gⁱmod p≠1。

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

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

3.2.10    输入格式

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

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

3.2.11    输出格式

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

3.2.12    样例

3.2.12.5    输入样例1

3.2.12.6    输出样例1

3.2.13    数据范围

对于40%的测试点 ，保证 3 ≤ p≤ 10³。

对于所有测试点 ，保证 1 ≤ T ≤ 20 ，3 ≤ p ≤ 10⁹，1 < a < P，P为质数。

【题目大意】 给定一个质数 p和一个整数a，判断a是否是p的原根

【补充概念】

原根：

若正整数g满足g模m的阶等于φ(m),则g为m的原根。

阶：

满足同余式aⁿ≡ 1( mod m)的最小正整数n被称为a模m的阶，记作δ_m(a)或ord_m(a)。

欧拉函数

欧拉函数φ(n)是定义在正整数n上的函数，表示小于或等于n的正整数中与n互质的数的个数。

若n是质数p，则φ(p)=p-1.

这是因为除了1以外，其他所有小于p的正整数都与p互质。

费马小定理：

如果p是一个质数，而整数a不是p的倍数，则有a^(p-1)≡1(mod p)。

原根判定定理

设m ≥3,(g,m)=1，则g是模m的原根的充要条件是，对于φ(m)的每个素因数p，都有g^φ(p)/p≢1(mod m).

【思路分析】

由上述数学推论可以知道，只需要判断所有质因子是否满足条件即可

3.2.14    参考程序

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

技术支持：鲍天玙