算法分析与设计第五次理论作业

一. 单选题（共5题，50分）

(单选题) 贪心算法的基本要素是（）。
A.最优子结构性质与贪心选择性质
B.重叠子问题性质与贪心选择性质
C.最优子结构性质与重叠子问题性质
D.最优子结构性质和递归性质

正确答案: A:最优子结构性质与贪心选择性质;
(单选题) 采用贪心算法求解最优装载问题时，其主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）。
A. \(O(n2^n)\)
B. \(O(nlogn)\)
C. \(O(2n)\)
D. \(O(n)\)

正确答案: B:O(nlogn) ;
10分
(单选题) 用贪心算法求解背包问题所需时间为（）。
A. \(O(n2^n)\)
B. \(O(nlogn)\)
C. \(O(2n)\)
D. \(O(n)\)

正确答案: B:O(nlogn);
10分
(单选题) 关于背包问题和0-1背包问题，以下叙述中正确的是（）。
A. 0-1背包问题是特殊的背包问题，所以，凡是可以求解背包问题的算法都可以用来求解0-1背包问题。
B. 背包问题是特殊的0-1背包问题，所以，凡是可以求解0-1背包问题的算法都可以用来求解背包问题。
C. 背包问题可以用贪心算法求解，而0-1背包问题不能用贪心算法求解。
D. 二者都可以用贪心算法求解。

正确答案: C:背包问题可以用贪心算法求解，而0-1背包问题不能用贪心算法求解。 ;

10分
(单选题) n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。

下列叙述中不正确的是（）。

A.让水桶大的人先打水，可以使得每个人排队时间之和最小。

B.让水桶小的人先打水，可以使得每个人排队时间之和最小。

C.让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水。

D.若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样。

正确答案: A:让水桶大的人先打水，可以使得每个人排队时间之和最小。 ;

10分

二. 填空题（共5题，50分）

(填空题) 有9个待安排的活动，第i个活动的开始时间s[i]与结束时间f[i]如下表所示。如果

以贪心算法求解这个活动安排问题，得到的最大相容活动子集合为（）。

i 1 2 3 4 5 6 7 8 9

s[i] 3 2 4 3 6 5 10 12 6

f[i] 4 5 6 8 9 10 12 14 18

正确答案： (1)
(填空题) 活动安排问题采用的贪心选择策略是_______。

正确答案： (1)总是安排最先完成的相容活动
(填空题) 贪心算法中的贪心选择性质指的是。

正确答案： (1)所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
(填空题) 最优装载问题采用的贪心选择策略是。

正确答案： (1)最轻者先装
(填空题) 背包问题与0-1背包问题的区别在于。

背包问题和0-1背包问题中，可以用贪心算法求解的问题是。

正确答案：

(1)可以选择物品的一部分而不是全部装入背包

(2) 背包问题