算法设计与分析基础习题参考答案

2.a. 算法optimalBST的时间效率为什么是立方级? b. 算法optimalBST的空间效率为什么是平方级? 解:a.最内层循环执行的次数:

37

b. 算法optimalBST使用了两个表:C--(n+1)×(n+1),R--n×n,并且每个表只填了一半. 3.写一个线性时间算法的伪代码,来从根表中生成最优二叉查找树 Algorithms OptimalTree(i,j) //输入:有序列表的第一和最后序号

//输入:先序遍历最优二叉查找树节点编号的列表

38

习题9.1 1、 2、

给出一个找零问题的实例,使得贪婪算法不能输出一个最优解.

为找零问题写一个贪婪算法的伪代码,它以金额n和硬币的面额d1>d2>…>dm作为输入.以n的函数形式给出该算法的效率类型.

Hints:

Algorithms change(n,D[1..m]) //用贪婪法求找零问题

//输入:非负整数n,硬币面额以降序排列的数组D

//输出:数组A[1..m]----每种面额硬币的数量,或者无解

习题9.4 1.(题略) a.

39

b. c.

b.该问题的实例中共有多少个不同的最优子集？ 解答：只有一个，为{0,0,1,0,1}

c.一般来说，如何从动态规划算法所生成的表中判断背包问题的实例是不是具有不止一个最优子集？

40