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

.

i s(i) f(i) 1 0 6 2 3 5 3 1 4 4 5 9 5 3 8 6 5 7 7 11 13 8 8 12 9 8 11 10 6 10 同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。

参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表：

i s(i) f(i) 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 11 13 ⑴选择申请1（1,4）

⑵依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申请4（5,7）、申请8（8,11）、申请10（11,13） ⑶最后，可以满足：申请1（1,4）、申请4（5,7）、申请8（8,11）、申请10（11,13）共4个客户申请。这已经是可以满足的最大客户人数。 4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：

0i?j??m[i,j]??

min{m[i,k]?m[k?1,j]?pi?1pkpj}i?j??i?k?j其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，

pi为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：

A1 50?10 A2 10?40 A3 40?30 A4 30?5 . .

.

p 0? p 1 p 1? p 2 p 2? p 3 p 3? p 4 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。 参考解答：

?m[1][1]?m[2][4]?p0p1p4?0?8000?50?10?5?10500?m[1][4]?min?m[1][2]?m[3][4]?p0p2p4?20000?6000?50?40?5?36000?m[1][3]?m[4][4]?ppp?27000?0?50?30?5?34500

034??105005、（8分）有这样一类特殊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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？

参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。 6.请用英文写出三种以上能求解0-1背包问题的设计算法策略。 参考解答：

Dynamic Programming Backtrack Branch-and-Bound （每答对一条给一分）

. .

.

7.请说明动态规划方法为什么需要最优子结构性质。

参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构 8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？ 参考解答：（1）堆。(1分)

（2）在小根堆中，将元素x插入到堆的末尾，

然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字，

则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。(4分)

（3）O( log n)（1分）

9..设计动态规划算法的主要步骤是怎么的？请简述。

参考解答：（1）找出最优解的性质，并刻划其结构特征。(6分) （2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

10.分治法所能解决的问题一般具有哪几个特征？请简述。

参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分)

. .

.

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有

最优子结构性质;

（3） 利用该问题分解出的子问题的解可以合并为该问题的解；

（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不

包含公共的子问题。

11.分支限界法的搜索策略是什么？

参考解答：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。(6分) 12 算法的要特性是什么？

参考解答：确定性、可实现性、输入、输出、有穷性 13 算法分析的目的是什么？

参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

14 算法的时间复杂性与问题的什么因素相关？

参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。 15 算法的渐进时间复杂性的含义？

参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

. .