算法导论试卷

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