算法分析与设计试题.doc

《算法分析与设计试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题（20分）1．最长公共子序列算法利用的算法是（    B      ）。A、分支界限法B、动态规划法C、贪心法D、回溯法2．实现棋盘覆盖算法利用的算法是（     A     ）。A、分治法B、动态规划法C、贪心法D、回溯法3.下面是贪心算法的基本要素的是（      C    ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解4.回溯法的效率不依赖于下列哪些因素（D）A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间5.下面哪种函数是回溯法中为避免无效搜索采取的策略（    B   ）A．递归函

2、数B.剪枝函数C。随机数函数D.搜索函数6．采用最大效益优先搜索方式的算法是（   A       ）。A、分支界限法B、动态规划法C、贪心法D、回溯法7．贪心算法与动态规划算法的主要区别是（  B        ）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解8.实现最大子段和利用的算法是（     B     ）。A、分治策略B、动态规划法C、贪心法D、回溯法9.优先队列式分支限界法选取扩展结点的原则是（     C     ）。A、先进先出B、后进先出C、结点的优先级D、随机10.下列算法中通常以广度优先方式系统搜索问题解的是（    

3、  A  ）。A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。2、大整数乘积算法是用分治法来设计的。3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。4、舍伍德算法总能求得问题的一个解。5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。6.快速排序templatevoidQuickSort(Typea[],intp,intr){if(p

4、,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}7.哈密顿环问题的算法可由回溯法设计实现。8.贪心算法不一定产生最优解。9.算法中通常以深度优先方式系统搜索问题解的是回溯法。三、算法设计与分析（25分）1.用欧几里德迭代算法求两个数的最小公倍数（10分）#includeusingnamespacestd;intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;while(m%t

5、

6、n%t)t--;

7、returnt;}intmain(){inta,b;cout<<"Inputa&b(0<=a>a>>b;intm=a*b/Gcd(a,b);cout<<"TheLeastCommonMultipleis:"<

8、+)b[k]=0;……………………………..（5分）for(intj=i;j<=m;j++){for(intk=1;k<=n;k++)b[k]+=a[j][k];intmax=MaxSum(n,b);if(max>sum)sum=max;}}returnsum;……………………………..（10分）}intMaxSum(intn,int*a){intsum=0,b=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}Returnsum;……………………………..（15分）}四、简答

9、题（33分）1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解过程。（10分）物品ABCDEFG重量35306050401025价值10403050354030解：使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。2.写出分治算法MaxMin算法对下列实例中找最大数和最小数的过程。（10分）数组A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3,5,19,

10、32,7表中元素多于二，对半分割2、48,1261,35,1932