算法设计与分析试卷

算法试卷

算法设计与分析期末考试试卷

考试形式：闭卷 考试时间：120分钟

班级： 姓名： 学号： 成绩：

1. 到商店购买商品需要找零钱。假设有四种面值分别为14角，5角，2角，1角的硬币可以找零，售货员希望找零的硬币数目最少。也就是，优化目标是找零的硬币数目最少，限制条件是所选择的硬币的总面值等于要找的零钱数。

（1） 假设要找的零钱数分别是13角，21角和41角；（贪婪策略：每一次

选择应该使硬币的面值最大），给出相应的解。

（2） 假设要找的零钱数是n角，请用C语言或伪代码描述算法。（15分）

2. 在用分治法求两个n位大整数u和v的乘积时，将u和v都分割成长度为n/3位的3段，证明可以用5次n/3位整数的乘法求得uv的值。按这些思想设计一个求得两个大整数乘积的分治算法，并分析算法的时间复杂性。（20分）

3. 给定n种物品和一背包。物品i的重量是wi，体积是bi,其价值为vi,背包的容量为C,容积为D。问：应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法，试分析算法的计算复杂性。（15分）

4. 子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和为d=9。（20分）

（1） 画出子集和问题的解空间树；

（2） 该树运用回溯算法，写出依回溯算法遍历节点的顺序；

（3） 如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算

法。

5.码头上有n艘船舶同时等待装卸，而码头每次只能装卸一艘船舶。船舶i需要装卸的时间为ti，1≤i≤n。应如何安排这n艘船舶的装卸次序才能使得总的等待时间达到最小？总的等待时间是每艘船舶的等待时间的总和。（20分）

（1）证明此问题具有贪心选择性质；（2）给出此问题的贪心选择策略；

（3）给出求解此问题的贪心算法；（4）说明你所给出的算法的时间复杂性。

6. 请用分枝限界法设计一个算法求解单源最短路径问题。（10分）