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++编程五级真题及答案解析