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

GESP-C++五级 题库

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

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

struct Task { 
    int deadline; //截止时间 
    int profit; //利润 
}; 
void sortByProfit(vector<Task>& tasks) { 
    sort(tasks.begin(), tasks.end(), 
        [](const Task& a, const Task& b) { 
            return a.profit > b.profit; 
        }); 
} 
int maxProfit(vector<Task>& tasks) { 
    sortByProfit(tasks); 
    int maxTime = 0; 
    for (auto& t : tasks) { 
        maxTime = max(maxTime, t.deadline); 
    } 
    vector<bool> slot(maxTime + 1, false); 
    int totalProfit = 0; 
    for (auto& task : tasks) { 
        for (int t = task.deadline; t >= 1; t--) { 
            if (!slot[t]) { 
                _______________________ //在此处填入代码 
                break; 
            } 
        } 
    } 
    return totalProfit; 
}
A
slot[t] = true; 
totalProfit += task.profit;
B
slot[t] = false; 
totalProfit += task.profit;
C
slot[t] = true; 
totalProfit = task.profit;
D
lot[t] = false; 
totalProfit = task.profit;
答案与解析
正确答案:A
首先按利润降序排列任务。确定最大截止时间以初始化时间槽数组,每个槽位标记是否被占用。遍历已排序的任务,对每个任务从其截止时间向前查找第一个空闲时间槽。若找到空闲槽位,则将其标记为占用,并将该任务的利润累加到总利润中。遍历所有任务后,返回累计的总利润。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

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

A
总是选择当前最优解
B
回溯尝试所有可能
C
分阶段解决子问题
D
总能找到最优解
答案与解析
正确答案:A

贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

假设有多个孩子,数组 g 保存所有孩子的胃口值。有多块饼干,数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干,每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时,孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子,因此打算采用贪心算法来找出能满足的孩子的数目,则横线上应填写的代码为( )。

int cooki4children(vector<int>& g, vector<int>& s) {
	sort(g.begin(), g.end());
	sort(s.begin(), s.end());
	
	int index = s.size() - 1; // 饼干数组下标
	int result = 0;
	for (int i = g.size() - 1; i >= 0; i--) {
		if (index >= 0 && s[index] >= g[i]) {
			________________________________ // 在此处填入代码
		}
	}
	return result;
}
A
result++; index–;
B
result–; index–;
C
result–; index++;
D
result++; index++;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

贪心算法的核心思想是(   )?

A
在每一步选择中都做当前状态下的最优选择
B
在每一步选择中都选择局部最优解
C
在每一步选择中都选择全局最优解
D
以上都对
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

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

A
对
B
错
答案与解析
正确答案:对
分析贪心算法每一步选择的局部最优性及其不可回溯特性;考察分治算法将原问题划分成独立子问题的过程;明确子问题求解的独立性与后续合并操作的关系;对比两种算法在决策过程与结构处理上的差异;区分局部最优策略与递归分解再合并的解决机制。
题目详情
6 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

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

A
对
B
错
答案与解析
正确答案:错
分析贪心算法的决策机制:每一步选择当前状态下的局部最优解,依据问题是否具有贪心选择性质和最优子结构性质,决定局部最优解的累积是否构成全局最优解。验证该机制需考察问题特性与选择策略之间的匹配关系,不保证所有问题通过局部最优能达到全局最优。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

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

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

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

从该算法的描述可以看出,Dijkstra算法是贪心算法。( )

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

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

A
对
B
错
答案与解析
正确答案:错

贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。

题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

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

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

贪心算法通过每一步选择局部最优解,从而一定能获得最优解。

A
对
B
错
答案与解析
正确答案:错

贪心算法的使用条件是:局部最优能够得到全局最优,不是所有的问题都可以通过贪心实现,因为局部最优不一定能得到全局最优

题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

贪心算法通过每一步选择局部最优解来获得全局最优解,但并不一定能找到最优解。

A
对
B
错
答案与解析
正确答案:对

它通常在每一步做出局部最优选择,并希望通过这种方式最终达到全局最优解。然而,并不是所有问题都适合使用贪心算法,并且即使某些问题可以使用贪心算法,它也不能保证一定能找到全局最优解。

题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

使用贪心算法解决问题时,每一步的局部最优解一定会导致全局最优解。(   )

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

贪心算法是一种可以应用于所有问题的通用解决方案。(   )

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

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

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

贪心算法的解可能不是最优解。(2023.9C++五级)

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