共 2页 第 1 页
5、（15 分）在 0/1 背包问题中，设 f(i , y)表示剩余容量为 y，剩余可选物品为： i，i+1，…，n 时的最优解的值。 1）给出 f(i , y)的递推表达式； 2）请设计计算 f(i , y)的算法； 3）设 W=[10,20,15,30]，P=[6,10,15,18], m=48，请用你的算法求解，要求写 出计算过程。
4、（15 分）[节点覆盖问题] 假设 G=(V,E)为一个无向图，G 的节点覆盖为节点 集合 V 的一个子集 U，满足 E 中每一条边至少与 U 中的一个顶点相关联。 最小节点覆盖是具有最少节点数量的一个覆盖。先制定贪婪准则为：每次 从未被覆盖的顶点中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目 最多。 1）这种法总能产生一个最优解吗？如果能，请证明之；如果不能，请举 出一个反例。 2）用伪代码描述这种贪心算法。
西安交通大学考试题
成绩
课程
系别 专业班号 姓名
算法导论
ቤተ መጻሕፍቲ ባይዱ
考试日期
年 月日
学号
期中
期末 √
1、（10 分）证明：若 f(n)= amnm+…+a1n+a0 那么 f(n)= (nm)，f(n)= (nm)。
(am > 0)，
2、（20 分）到商场购买商品需要找零钱。假设有四种面值分别为 14 角、5 角、 2 角和 1 角的硬币可以找零，售货员希望找零的硬币数目最少。也就是， 优化目标是找零的硬币数目最少，限制条件是所选择的硬币的总面值等于 要找的零钱数。
1）假设要找的零钱数分别是 13 角，21 角和 41 角；(贪婪策略：每一次选 择应该使硬币的面值最大), 给出相应的解。
2）假设要找的零钱数是 n 角，请用 C 语言或伪代码描述算法。
3、（10 分）有 n（=2 k）个硬币，其中 1 个是假币，且假币和真币的重量不同。 请用分而治之方法设计一个找出假币的算法，并用伪代码描述你的算法。
共 2页 第 2 页
6、（15 分）请分别说明分治策略、动态规划、贪心算法、回溯法和分支限界法 的基本思想。
7、（15 分）旅行商问题：给出一个 n 个顶点网络，要求找出一个包含所有 n 个 顶点的具有最小耗费的环路。任何一个包含所有 n 个顶点的环路被称作一 个旅行。在旅行商问题中，要求设法找到一条最小耗费的旅行。 1）若图的邻接矩阵如下，画出旅行商问题的解空间树； 2）对该树运用回溯算法求解，并写出依回溯算法遍历节点的序列； 3） 用 C 语言或伪代码描述求解旅行商问题的回溯算法。 ∞ 20 30 10 11 15 ∞ 16 4 2 35 ∞ 2 4 19 6 18 ∞ 3 16 4 7 16 ∞