GESP-Python五级 题库
共 11 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
给定有 n 个任务,每个任务有截止时间和利润,每个任务耗时 1 个时间单位、必须在截止时间前完成,且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润,可以采用贪心策略,即按利润从高到低排序,尽量安排,则横线处应填写( )。
A
slot [t] = True total_profit += task .profit break
B
slot [t] = True total_profit += task .profit
C
slot[t] = False total_profit += task .profit break
D
slot [t] = True total_profit -= task .profit
答案与解析
正确答案:A
标准任务调度贪心,排序后倒序查找空闲时间槽,对应选项A代码逻辑。
3
判断题
偏易
贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。()
A
对
B
错
答案与解析
正确答案:对
贪心无回溯、局部最优;分治拆分求解再合并,定义描述正确。
4
判断题
偏易
使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。()
A
对
B
错
答案与解析
正确答案:错
贪心仅局部最优,部分场景局部最优无法推出全局最优(如背包问题)。
三、编程题(每题 25 分,共 50 分)
6
判断题
偏易
求解下图中A点到D点最短路径,其中A到B之间的12可以理解为距离。求解这样的问题,常用Dijkstra算法,其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图(如距离不能为负值)单源最短路径的算法。从该算法的描述可以看出,Dijkstra算法是贪心算法。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。