2015算法设计与分析考试复习刚要及习题(5)

11

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=

法对下列实例中找最大数和最小数的过程。 数组 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 55 70 75 80 85 65 50 2 10 归并排序算法对下

列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7) 参考解答：

61 5, 7, 19，32

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,

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