GESP2024
年
6月认证C++五级
题号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
答案
C
B
B
C
C
D
A
D
D
A
C
A
C
D
C
一、单选题(每题2分,共30分)
1、下面
C++
代码用于求斐波那契数列,该数列第
1
、
2
项为
1
,以后各项均是前两项之和。函数
fbo0
属于
( )
A.
枚举算法
B.
贪心算法
C.
迭代算法
D.
递归算法
答案:
C
解析:迭代算法:迭代算法是通过循环实现的,每次迭代利用前面计算的结果来推导出下一个结果。在给定的
C++
代码中,使用了一个循环
for (int i = 3; i <= n; i++)
来计算斐波那契数列第
n
项的值,通过迭代更新
a
和
b
的值,直到计算出第
n
项的值并返回。
2
、下面
C++
代码用于将输入金额换成最少币种组合方案,其实现算法是
( )
。
A.
枚举算法
B.
贪心算法
C.
迭代算法
D.
递归算法
答案:
B
解析:贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。
算法实现分析:
数组
coins
存储了面值从大到小的硬币面额
{100, 50, 20, 10, 5, 2, 1}
。
函数
find_coins()
中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额
money
可以使用的当前面额硬币数量,并更新剩余金额
money
。
循环结束后,
coins_used
数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。
选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。
根据代码实现方式和贪心算法的特性,这段
C++
代码确实属于贪心算法。
3
、小杨采用如下双链表结构保存他喜欢的歌曲列表:
小杨想在头指针为
head
的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。
A
、
O(1)
B、
O(n)
C、
O(log n)
D、
O(n
2
)
答案:
B
解析:该查询函数的时间复杂度为
O(n)
,其中
n
是双链表中节点的数量。
函数使用一个指针
temp
从头指针
head
开始,沿着双链表向后遍历。
在每个节点处,它检查节点中的歌曲名称是否与目标歌曲
my_song
匹配。
最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为
O(n)
这是因为在最坏情况下,需要遍历所有
n
个节点才能确定目标歌曲是否存在。
4
、小杨想在如上题所述的
2024年6月GESP认证C++编程五级真题及答案解析