计算机与信息科学学院2010-2011学年第2学期模拟试卷
计算机算法设计与分析—第四章.贪心算法
本卷满分100分 完卷时间120分钟
一. 简答题（每小题2分，共20分）
1. 当一个问题具有 且具有 时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）。
2. 在动态规划可行的基础上满足 才能用贪心。
3. 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 选择。
4. 动态规划算法通常以 的方式解各子问题，而贪心算法则通常 以 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题
5. 贪心算法和动态规划算法都要求问题具有 性质，这是2类算法的一个共同点。
6. 当一个问题的最优解包含其子问题的最优解时，称此问题具有 。
7. 对于具有n 个顶点和e 条边的带权有向图，如果用带权邻接矩阵表示这
个图，那么Dijkstra 算法的主循环体需要
时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。
8. 0-1背包问题指：给定n 种物品和一个背包。物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。应如何选择装入背包的物品，使得装入背包中物品的 最大。
9. 有一批集装箱要装上一艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在 不受限制的情况下，将 装上轮船。
10. 多机调度问题要求给出一种作业调度方案，使所给的n 个作业在 由m 台机器加工处理完成。
二. 综合题（1-6题每题7分，7-8题每题9分，共60分）
1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25,
12)，背包容量为10。试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。
)(n O
2. 使用prim算法构造出如下图G的一棵最小生成树。
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6
3. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i
所需要的处理时间为t
i
。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。
4. 设有n种面值为:d
1≥d
2
≥……≥d
n
的钱币，需要找零钱M，如何选择钱
币d
k ，的数目X
k
，满足 d
1
×X
i
＋……d
n
×X
n
M ，使得X
i
＋……X
n
最小。
请选择贪心策略，并设计贪心算法。
5. 在下列空格中填入适当的语句完成贪心方法的抽象化控制
procedure GREEDY(A，n)
//A(1：n)包含n个输入//
solutions←①；
for i←1 to ② do
x←SELECT(A)
if FEASIBLE(solution，x)
then solutions←③；
endif
④；
return(solution)
end GREEDY
6. 填空完成背包问题的贪心算法
procedure GREEDY-KNAPSACK(P，W，M，X，n)
X←0 //将解向量初始化为零//
cu←M //cu是背包剩余容量//
for i←1 to n do
if ① then exit endif
X(i) ←②；
cu←③；
④；
if i≤n then X(i) ←⑤；
endif
end GREEDY-KNAPSACK
7. 填空完成带有限期的作业排序
line procedure JS(D，J，n，k)
//D(1)，…，D(n)是期限值。n≥1。作业已按p
1≥p
2
≥…p
a
被排序。J(i)
是最优解中的第i个作业，1≤i≤k。终止时，D(J(i)≤D(J(I+1))，1≤i1 integer D(0：n)，J(0：n)，i，k，n，r
2 D(0)←J(0) ←0 //初始化//
3 k←1；J(1) ←1 //计入作业1//
4 for ① to n do
5 ② ;
6 while ③ and ④ do
7 ⑤ ;
8 repeat
9 if D(J(r))≤D(i) and D(i)>r then
10 for ⑥⑦ by-l do
11 ⑧；
12 repeat
13 ⑨；k←k+1；
14 endif
15 repeat
16 end JS
8. 有n 个活动争用一个活动室。已知活动i占用的时间区域为[s
i ，f
i
]，活动
i,j相容的条件是：sj≥f
i ，问题的解表示为(x
i
| x
i
=1，2…，n,)，x
i
表示
顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。
三.简答题（每题5分，共20分）
1.简述贪心法的设计思想。
2.简述Kruskal算法构造G的最小生成树的基本思想
3.试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。
4.简述贪心算法与动态规划算法的差异
