算法设计与分析a&k

《算法设计与分析a&k》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络学院算法试题A及答案一．填空题：（前四小题每题3分，第5小题4分，共16分）1.算法的特性有_0至多个输入，至少一个输出，指令无歧义性，指令条数有限且每条指令执行时间有限.2．程序性能是指_运行一个程序所需的内存大小和时间多少_.性能评估主要包含两方面,即性能分析_与性能测量__,前者采用_分析__的方法，后者采用__测量_的方法。3.估算程序运行时间的方法有_操作计数法_和_程序的执行步数__.4．递归函数的两大基本要素是_递归方程和边界条件_.5．在回溯法中，一个问题的解空间是指一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解

2、决一个问题的所有可能的决策序列构成该问题的解空间.二．简答题：（每题6分，共24分）1.什么是实例特征？答：所谓实例特征是指决定问题规模的那些因素.如，输入和输出的数量或相关数的大小，如对n个元素进行排序、n´n矩阵的加法等，都可以n作为实例特征.2．什么是最优子结构性质?答：所谓最优子结构性质，即为一个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。3．什么是贪心选择性质？答：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到.这是贪心算法可行的第一个基本要素.4.对下述的顺序搜索函数，假定以被查数组的长度n为实

3、例特征，分析其空间复杂性intSequentialSearch(inta[],constint&x,intn){//在a[0:n-1]中搜索x，若找到则回所在的位置，否则返回-1inti;for(i=0;i

4、所需的空间计算进来，因为该数组所需的空间已在定义实际参数(对应于a)的函数中分配，不能再加到函数SequentialSearch所需的空间上去。三．计算和编程题：（每小题15分,共60分）1．考虑金钱兑换问题：有一个货币系统，它有n种硬币，它们的面值为v1,v2,…,vn，其中v1=1.我们想这样来兑换价值为y的钱，要让硬币的数目最少。更形式地，我们要让下面的量在约束条件下最小.其中x1,x2,…,xn是非负整数.1)用贪心算法求解该问题；2)如果硬币的面值有1分，5分，7分和11分，给出反例说明用贪心算法并不总是有效的。1)贪心伪代码为：Greedy_exchan

5、ge(intv[],inty,intnum[],intn){inti=0,fori=0tondonum[i]=0;Sort(v);//从大到小排序whiley>0do{num[i]=y/v[i];y=y%num[i++]；}returnnum;}2)反例：假如要给顾客找15分钱，按照上述贪心策略，则应将15分分解为：11分+1分+1分+1分+1分。而事实上15分可分解为：5分+5分+5分。显然后者的张数更少。2.假设有n(nÎN且n>1)个硬币，已知其中有一个是假币且假币较真币轻.请设计分治算法求解该问题.并给出其复杂度分析.Feit_money(low,high)

6、//假定伪币较真币轻{floatmid;ifhigh-low=1thenifA[low]A[high]returnA[high];5elsemid=(low+high)/2;if(high-low+1)%2==0thensum1=sum(low,mid);sum2=sum(mid+1,high);elsesum1=sum(low,mid-1);sum2=sum(mid+1,high);endififsum1=sum2thenreturnA[mid];elseifsum1

7、igh-low+1)%2==0?Feit_money(low,mid):Feit_money(low,mid-1);elseFeit_money(mid+1,high);endifendifreturn0;}其时间复杂度为：O(logn).3.对于以下5个矩阵：A1:10´5,A2:5´4,A3:4´9,A4:9´10,A5:10´2求出这5个矩阵相乘需要的最小数乘次数及相应的加括号方式.（注：要求给出计算公式和计算过程）解答：计算公式为：例如：m123451020056096039220180560292303602524018050S123451011112