第四章贪心算法20秋人民大学测试答案
第四章贪心算法1.[问答题]在什么情况下可以应用贪心方法获得问题的最优解？<br>
正确答案:——a）问题满足贪心选择性质。即所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。<br>b）问题满足最优子结构性质。即所求问题的最优解包含其子问题的最优解。<br>——
2.[单选题]背包问题的贪心算法所需的计算时间为（ ）。
A.O（n<img width=17 height=19 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/218379CA1.gif">）
B.O（n<img width=27 height=21 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/218379CB1.gif">） ap5u.com q761296021
C.O（<img width=17 height=19 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/218379CC1.gif">）
D.O（n）
正确答案:——B——
3.[单选题]（ ）是贪心算法与动态规划算法的共同点。
A.重叠子问题
B.构造最优解
C.贪心选择性质
D.最优子结构性质
正确答案:——D——
4.[判断题]同一个问题，其贪心算法的效率一定比动态规划设计的算法高。
A.错误
B.正确
正确答案:————
5.[单选题]下面是贪心算法的基本要素的是（ ）。
A.重叠子问题
B.构造最优解
C.贪心选择性质
D.定义最优解
正确答案:————
6.[问答题]简述0—1背包问题和背包问题的差别，描述求解背包问题的贪心算法。<br>
正确答案:————
7.[判断题]哈夫曼编码算法使用的方法是动态规划。
A.错误
B.正确
正确答案:————
8.[问答题]一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，<img width=128 height=19 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/238976A1.gif">，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。<br>
正确答案:————
转载注明 无忧答案网
页:
[1]