《算法设计与分析》模拟试卷三

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

1、《算法设计与分析》模拟试卷三考试形式：闭卷考试时间：120分钟站点：_________姓名：_________学号：_________成绩：_________1．到商场购买商品需要找零钱。假设有四种面值分别为14角、5角、2角和1角的硬币可以找零，售货员希望找零的硬币数目最少。也就是，优化目标是找零的硬币数目最少，限制条件是所选择的硬币的总面值等于要找的零钱数。1）假设要找的零钱数分别是13角，21角和41角；(贪婪策略：每一次选择应该使硬币的面值最大),给出相应的解。2）假设要找的零钱数是n角，请用C语言或伪代码描述算法。2．对于二分图覆盖问题设计一种贪婪启发算法，贪婪准

2、则是：如果B中某一个顶点被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。给出这种贪婪算法的伪代码。3．有n（=2k）个硬币，其中1个是假币，且假币和真币的重量不同。请用分而治之方法设计一个找出假币的算法，并用伪代码描述你的算法。4．请用分治法设计算法：在一个整数组A[1..n]中，同时寻找最大值和最小值。[假设n为2的方幂]。请用伪代码描述你的算法并分析算法的时间复杂度。5．定义0/1/2背包问题为：。限制条件为：，且。设f(i,y)表示剩余容量为y，剩余物品为：i，i+1，…，n时的最优解的值。1）给出f(i,y)的递

3、推表达式；2）请设计求解f(i,y)的算法，并用伪代码描述你的算法；3）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。第6页共6页6．请设计一个有效的算法，可以进行两个n位（n=2k）十进制大整数的乘法运算。7．子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。1）画出子集和问题的解空间树；2）该树运用回溯算法，写出依回溯算法遍历节点的顺序；3）如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。参考答案1.1)13角：2个5角+1个2角+1个1角；21角：1个14角+1个5角+1个2

4、角；41角：2个14角+2个5角+1个2角+1个1角；2)当要找的钱数是n角时，用伪代码描述此贪婪算法如下：floatexchange(intfund,intcoin[],intx[]){intn=coin.length,opt=fund;Sort(coin);//从大到小for(inti=0;i0){x[j]=opt/coin[j];opt=opt%coin[j];}returnx;}2．贪婪算法的伪代码为m=0//当前覆盖的大小对于A中的所有i,Out[i]=outdegree[i];对于B中的所有i,In[i]=

5、indegree[i];对于B中的所有i,Cov[i]=false;for(对于B中所有入度为1的顶点i){设v是邻接于B[i]的顶点C[m++]=v;for(所有邻接于v的顶点j){if(!Cov[j]){Cov[j]=true;对于所有邻接于j的顶点，使其Out[k]减1}}}第6页共6页while(对于A中的某些i,Out[i]>0){设v是具有最大Out[i]的顶点C[m++]=v;for(所有邻接于v的顶点j){if(!Cov[j]){Cov[j]=true;对于所有邻接于j的顶点，使其Out[k]减1}}}if(有些顶点未被覆盖)失败else找到一个覆盖3.Fe

6、it_money(low,high)//假定伪币较真币轻ifhigh-low=1thenifA[low]A[high]returnA[high];elsemid=(low+high)/2;sum1=sum(low,mid);sum2=sum(mid+1,high);ifsum1

7、low]