海大算法设计与分析考试复习试题

.

6.（13分）有0-1背包问题如下：

n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。

其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。

P=(15，8，6，4，3，1) W=(2，3，4，5，8，10)，单位重量物品价值（7.5，2.67，1.5,0.8,0.375,0.1）

参考解答：（13分）

可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。

1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。 2.把重量为3的物品放进背包，此时剩余载重量为14，P为23； 3.把重量为4的物品放进背包，此时剩余载重量为10，P为29； 4.把重量为5的物品放进背包，此时剩余载重量为5，P为33. 由于8>5，所以不能再放进背包。

结果是把重量为2，3，4，5的物品装进背包，总价值最大为33.

. .

.

7、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分) 参考解答：（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。 （2）a[1:n]的最大子段和与的最大子段a[n/2+1:n]和相同。

⑶

a[1:n]

的

最

大

子

段

和

为

∑

ak(i=

且

1<=i<=n/2,n/2+1<=J<=n。

8 写出maxmin算法对下列实例中找最大数和最小数的过程。

数组 A=(48,12,61,3,5,19,32,7)

参考解答：写出maxmin算法对下列实例中找最大数和最小数的过程。

数组 A=()

1、 48,12,61,3, 5,19,32,7 2、 48,12 61,3 5,19 32,7 3、 48～61, 12～3 19～32，5～7 4、 61～32 3～5 5、 61 3

9 速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。

A=(65,70,75,80,85,55,50,2)

参考解答：第一个分割元素为65

(1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 . 65 2 75 80 85 55 50 70 3 7 .

65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6

.

10 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7)

参考解答： 48,12,61,3 5,19,32,7

48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32

3, 12, 48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61

欢迎您的光临，Word文档下载后可修改编辑双击可删除页眉页脚谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语；、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！、现在你不玩命的学，以后命玩你。、我不知道年少轻狂，我只知道胜者为王。、不要做金钱、权利的奴隶；应学会做金钱、权利的主人。、什么时候离光明最近？那就是你觉得黑暗太黑的时候。、最值得欣赏的风景，是自己奋斗的足迹。 7、压力不是有人比你努力，而是那些比你牛×几倍的人依然比你努力。

. .