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