2026年NOIP普及组复赛贪心算法经典题型训练

2026年NOIP普及组复赛贪心算法经典题型训练一、单选题（每题5分，共10题）1.贪心算法的核心思想是什么？A.分治策略B.动态规划C.每次选择当前最优解D.回溯法2.以下问题中，最适合使用贪心算法解决的是？A.最长公共子序列问题B.0-1背包问题C.单源最短路径问题（Dijkstra算法）D.旅行商问题3.在活动选择问题中，贪心策略是？A.选择时间最早结束的活动B.选择时间最晚结束的活动C.选择持续时间最长的活动D.选择编号最小的活动4.以下算法中，不属于贪心算法的是？A.Dijkstra算法B.Huffman编码C.快速排序D.Prim算法5.在最优装载问题中，贪心策略是？A.按重量从大到小排序后依次装载B.按重量从小到大排序后依次装载C.按价值密度从大到小排序后依次装载D.随机选择物品装载6.在分数背包问题中，贪心策略是？A.按价值从大到小排序后尽可能装满B.按重量从大到小排序后尽可能装满C.按价值密度从大到小排序后尽可能装满D.按重量从小到大排序后尽可能装满7.贪心算法的适用条件不包括？A.问题具有最优子结构B.问题具有贪心选择性质C.问题具有无后效性D.问题必须能够通过暴力搜索解决8.在最小生成树问题中，Prim算法和Kruskal算法的本质区别是？A.Prim算法从单个顶点开始，Kruskal算法从所有顶点开始B.Prim算法适用于稠密图，Kruskal算法适用于稀疏图C.Prim算法使用贪心策略，Kruskal算法使用动态规划D.Prim算法需要维护一个顶点集合，Kruskal算法需要维护一个边集合9.在任务调度问题中，贪心策略通常是？A.按任务执行时间从大到小排序B.按任务执行时间从小到大排序C.按任务优先级从高到低排序D.按任务依赖关系排序10.在区间调度问题中，贪心策略是？A.选择结束时间最早的活动B.选择开始时间最早的活动C.选择持续时间最长的活动D.选择优先级最高的活动二、填空题（每空2分，共10空，共20分）1.贪心算法的核心思想是每次选择当前最优解，以期望通过局部最优达到全局最优。2.活动选择问题中，贪心策略是按结束时间从小到大排序，并选择不冲突的活动。3.最优装载问题中，贪心策略是按价值密度从大到小排序，尽可能装满背包。4.分数背包问题与0-1背包问题的区别在于，分数背包允许部分装载物品。5.最小生成树问题中，Prim算法和Kruskal算法都满足贪心选择性质。6.在任务调度问题中，贪心策略通常是按执行时间从小到大排序，以最大化完成任务的数目。7.Huffman编码利用贪心算法构造最优二叉树，其核心思想是每次选择权值最小的两个节点合并。8.贪心算法的适用条件之一是问题具有贪心选择性质，即局部最优解能够推出全局最优解。9.在区间调度问题中，贪心策略是选择结束时间最早且不与已选活动冲突的活动。10.贪心算法的时间复杂度通常取决于排序和选择操作，常见的时间复杂度为O(nlogn)。三、简答题（每题10分，共5题，共50分）1.简述贪心算法的基本步骤。答：贪心算法的基本步骤包括：（1）确定问题的贪心选择性质；（2）设计一个数据结构来维护当前状态；（3）每次从可选方案中选择当前最优解，并更新状态；（4）重复步骤（3），直到找到全局最优解。2.为什么贪心算法不适用于所有问题？答：贪心算法不适用于所有问题，因为：（1）问题不满足最优子结构性质；（2）问题不满足贪心选择性质；（3）局部最优解不能推导出全局最优解；（4）某些问题需要回溯或动态规划等策略。3.在活动选择问题中，贪心策略是什么？如何证明其正确性？答：贪心策略是按活动结束时间从小到大排序，选择不冲突的活动。正确性证明：（1）贪心选择性质：选择结束时间最早的活动不会影响后续活动的选择；（2）最优子结构性质：剩余活动集合仍然满足贪心选择性质；（3）通过数学归纳法可以证明该策略能找到最多不冲突活动。4.在最小生成树问题中，Prim算法和Kruskal算法的贪心策略有何不同？答：-Prim算法：从单个顶点开始，每次选择与当前生成树相邻且权重最小的边；-Kruskal算法：按边权重从小到大排序，每次选择不形成环的最小边；两者都利用贪心选择性质，但Prim算法适用于稠密图，Kruskal算法适用于稀疏图。5.在分数背包问题中，贪心策略是什么？为什么该策略有效？答：贪心策略是按价值密度（价值/重量）从大到小排序，尽可能装满背包。有效性在于：（1）高价值密度的物品能更快填满背包，从而最大化总价值；（2）部分装载不受限制，可以充分利用背包容量。四、编程题（每题15分，共2题，共30分）1.活动选择问题输入：n个活动的开始时间和结束时间，输出最多不冲突活动的集合。输入示例：3142346输出示例：活动1和活动3解析：按结束时间排序：活动2（2,3）、活动1（1,4）、活动3（4,6）。选择活动2，排除活动1；选择活动3，不冲突。2.最优装载问题输入：背包容量W和若干物品的重量和价值，输出能装入背包的最大价值。输入示例：10440350270180输出示例：150解析：按价值密度排序：物品4（80/1）、物品3（70/2）、物品2（50/3）、物品1（40/4）。装入物品4（80）、物品3（70），总价值150。答案与解析一、单选题答案1.C2.C3.A4.C5.C6.C7.D8.D9.B10.A二、填空题答案1.最优解2.结束时间3.价值密度4.部分装载5.贪心选择性质6.执行时间7.权值最小8.贪心选择性质9.结束时间最早10.排序三、简答题解析1.贪心算法的基本步骤：-确定贪心选择性质；-设计数据结构维护状态；-每次选择当前最优解并更新状态；-重复直到找到全局最优解。2.贪心算法不适用的原因：-问题不满足最优子结构或贪心选择性质；-局部最优解无法推导全局最优解；-需要回溯或动态规划等策略。3.活动选择问题：-贪心策略：按结束时间排序，选择不冲突活动；-正确性证明：通过数学归纳法证明剩余活动集合仍满足贪心选择性质。4.最小生成树算法差异：-Prim算法从单个顶点扩展，Kruskal算法按边排序合并；-Prim适用于稠密图，Kruskal适用于稀疏图。5.分数背包问题：-贪心策略：按价值密度排序，尽可能装满背包；-有效性：高价值密度物品能更快填满背包，最大化总价值。四、编程题解析1.活动选择问题：-