算法分析与设计第四章测试_智慧树知到答案2021年

第四章 贪心算法：本章主要讲授贪心算法的定义和基本要素，学习如何使用贪心算法求解活动安排问题、部分背包问题、最优装载问题、最小生成树问题(Prim算法)和单源最短路径问题(Dijkstra算法)等经典问题，学习求解算法的设计、分析与实现。4.1贪心算法概述:学习贪心算法的定义和基本要素，理解贪心算法与动态规划算法的差异。
4.2贪心算法之活动安排问题:学习活动安排问题的描述以及如何使用贪心算法求解该问题，包括算法的设计、实现与分析。
4.3贪心算法之部分背包问题:学习部分背包问题的描述以及如何使用贪心算法求解该问题，包括算法的设计、实现与分析。
4.4贪心算法之最优装载问题:学习最优装载问题的描述以及如何使用贪心算法求解该问题，包括算法的设计、实现与分析。
4.5贪心算法之Prim算法:学习最小生成树的定义以及如何使用Prim算法构造图的最小生成树，包括算法的设计、实现与分析。
4.6贪心算法之Dijkstra算法（上）:学习单源最短路径问题的描述以及使用Dijkstra算法计算源点到其他点的最短路径的基本思想和算法流程。
4.7贪心算法之Dijkstra算法（下）:学习使用Dijkstra算法计算源点到其他点的最短路径的实例演示、算法实现和分析。

[单选题]在求解部分背包问题时采用的贪心策略是( )。
选择单位价值下重量最大的物品
选择重量最轻的物品
选择单位重量下价值最大的物品
选择价值最大的物品
答案：选择单位重量下价值最大的物品
[多选题]Dijkstra算法可用于求解( )。
单对顶点最短路径问题
单终点最短路径问题
每对顶点间最短路径问题
单源最短路径问题[判断题]Prim算法适合稀疏图，其时间复杂度只与边的数目有关。
错
对[单选题]在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为( )。
无穷小
0
-1
无穷大[多选题]能够使用贪心算法求解的问题需具备的基本要素包括( )。
重复子问题
最优子结构性质
贪心选择性质
递归调用
平衡子问题[多选题]下列关于贪心算法与动态规划算法说法正确的是( )。
贪心算法与动态规划算法求解的问题都具有重复子问题性质
贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质
贪心算法与动态规划算法求解的问题都具备最优子结构性质
贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质[单选题]在解决活动安排问题时应首先对活动进行排序，排序的依据是( )。
按照活动开始时间降序排列
按照活动开始时间升序排列
按照活动结束时间升序排列
按照活动结束时间降序排列[单选题]使用贪心算法求解最优装载问题，其时间复杂度为( )。
O(nlogn)
O(n2n)
O(n3n)
O(n5n)[多选题]( )能够使用贪心算法求解。
0-1背包问题
活动安排问题
最优装载问题
最小生成树问题
单源最短路径问题
部分背包问题[多选题]0-1背包问题与部分背包问题的区别在于( )。
若用贪心算法解决0-1背包问题，只能得到近似最优解
没有区别，它们的含义相同
若用贪心算法解决部分背包问题，只能得到近似最优解
在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分