首页 › 题库 › GESP编程能力等级认证 › 8 贪心算法

GESP-Python五级 题库

共 11 道题 · 按题型筛选,点「查看答案」核对解析
章节 8 贪心算法 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

给定有 n 个任务,每个任务有截止时间和利润,每个任务耗时 1 个时间单位、必须在截止时间前完成,且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润,可以采用贪心策略,即按利润从高到低排序,尽量安排,则横线处应填写( )。

class Task:
    def __init__(self, deadline, profit):
        self.deadline = deadline
        self.profit = profit
def sort_by_profit(tasks):
    tasks.sort(key=lambda x: x.profit, reverse=True)
def max_profit(tasks):
    sort_by_profit(tasks)
    max_time = 0
    for task in tasks:
        if task.deadline > max_time:
            max_time = task.deadline
    slot = [False] * (max_time + 1)
    total_profit = 0
    for task in tasks:
        t = task.deadline
        while t >= 1:
            if not slot[t]:
                # 填空处完整代码
                slot[t] = True
                total_profit += task.profit
                break
            t -= 1
    return total_profit
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代码逻辑。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法的核心特征是( )。

A
总是选择当前最优解
B
回溯尝试所有可能
C
分阶段解决子问题
D
总能找到最优解
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
3 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。()

A
对
B
错
答案与解析
正确答案:对
贪心无回溯、局部最优;分治拆分求解再合并,定义描述正确。
题目详情
4 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。()

A
对
B
错
答案与解析
正确答案:错
贪心仅局部最优,部分场景局部最优无法推出全局最优(如背包问题)。 三、编程题(每题 25 分,共 50 分)
题目详情
5 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法总能得到全局最优解。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
6 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

求解下图中A点到D点最短路径,其中A到B之间的12可以理解为距离。求解这样的问题,常用Dijkstra算法,其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图(如距离不能为负值)单源最短路径的算法。从该算法的描述可以看出,Dijkstra算法是贪心算法。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。(2025.3五级)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法的空间复杂度通常是O(1)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法虽然可能不是局部最优,但可达到全局最优。 (   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法可以达到局部最优,但可能不是全局最优解。 (   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 8.1 贪心思想

贪心算法的解可能不是最优解。

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