算法分析与设计试题

算法分析与设计试题Thedocumentwasfinallyrevisedon2021算法分析与设计试题一、选择题（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.下面哪种...

Thedocumentwasfinallyrevisedon2021算法分析与设计试题一、选择题（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．递归函数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.下列算法中通常以广度优先方式系统搜索问题解的是（A）。A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。2、大整数乘积算法是用分治法来设计的。3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。4、舍伍德算法总能求得问题的一个解。5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。6.快速排序templatevoidQuickSort(Typea[],intp,intr){if(pusingnamespacestd;intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;while(m%t||n%t)t--;returnt;}intmain(){inta,b;cout<<"Inputa&b(0<=a>a>>b;intm=a*b/Gcd(a,b);cout<<"TheLeastCommonMultipleis:"<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分）}四、简答题（33分）1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解过程。（10分）物品ABCDEFG重量35306050401025价值10403050354030解：使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入%，得到价值为。2.写出分治算法MaxMin算法对下列实例中找最大数和最小数的过程。（10分）数组A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3,5,19,32,7表中元素多于二，对半分割2、48,1261,35,1932,7表中元素多于二，对半分割3、48～61,12～319～32，5～7求前半部分的最大最小和后半部分的最大最小，两个半部分的大者为最大，小者为最小4、61～323～5两个半部分的大者为最大，小者为最小5、613寻找结束3.写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。（13分）5248438631545221674各边的代价如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，Cost(3,6)=C(6，8)+0=5,Cost(3,5)=C(5，8)+0=4Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8按上所述，Cost(1,1)为所求最优值。

                    本文档为【算法分析与设计试题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：￥18.0 已有0 人下载

立即下载

算法分析与设计试题

你可能还喜欢