算法复习试题.docx

《算法复习试题.docx》由会员分享，可在线阅读，更多相关《算法复习试题.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法复习试题（）2022一、填空题（每空1分，共15分）1、一个正确的算法应具有五个特性：（有穷性）、（确定性）、（能行性）、输入和输出。2、算法的时间简单性是算法运行所需要的（计算机资源）的量，这个量只依靠于（求解问题的规模）、（详细的输入数据）和（算法本身的设计）。3、函数的渐进表达式为（T（N）,函数log。的渐进表达式为（3n ）。4、快速排序和归并排序策略上是相同的，都是用的（递归与分治）算法。5、对于问题Q,假设满意（Q是NP困难的）、（ QNP）那么称Q为NP完全的。6、要求出一个问题全部的可行解，一般要用（回溯）算法。7、通常能用动态规划法求解的问题应具备（最优子结构）和（或者

2、是重叠字问题）相像）的性质。二、选择题（每题2分，共10分）（D ）1、概率算法是一种非确定性地选择下一计算步骤的方法，（）算法主要目的是消退算法所需计算时间对输入实例的依靠。A.数值概率算法B.蒙特卡罗算法C.拉斯维加斯算法D.舍伍得算法(B)2、ASCII码压缩方法经过两级压缩之后可以削减（）的存储空间。A. 62.5%B. 56.25%C. 50%D. 65%（A） 3、 P类问题与NP类问题的关系是（）D.等于D.等于A.包含于 B.包含C.属于（C ） 4、以下关于判定问题难易处理的表达中正确的选项是（ ）oA.可以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的

3、问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的（C ）5、对于含有n个元素的排列树问题，最坏状况下计算时间简单性为（ ）oA. 2n+,-lA. 2n+,-lC. n!D. 2n三、计算题（每题5分，共20分）（留意：要求写出计算过程）1、设某算法的时间简单度为O（n3）o在某台计算机上实现并完成该算法的时间为t秒。现有此外一 台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模多 大的问题？解：设在本台计算机上的速度为V,设在另一台计算机上的输入规模为X由 计算时间都为t秒有 n3/.V=X3/64

4、V可以求得X=4n2、根据渐近阶从低到高的挨次排列以下表达式：4n2, logo, 3n, n!, n2/3解：由低到高为：n2/3logn4n23nn!3、求解递归方程丁=1T(n) = 2T(n/3) + n2解：D(n)=n2 且 a=2D(3)=32=9 aD(b)所以 T(n)=O (n2)4、设MC(x)是解某个判定问题的蒙特卡罗算法，且是一个p正确的偏真算法。现有如下算法MC2(x), 试分析该算法的正确率。bool MC2(x) if(MC(x) return true; else return MC(x);解：蒙特卡罗算法的特点是只要有一次调用为真，结果就为真，所以该算法的正

5、确率为：1-(1-P)N N为调用的次数四、问答及求解题(每题10分，共40分)1、什么是贪心选择性质？(2分)贪心算法与动态规划算法有什么共同点？(4分)又有什么区分？ (4分)答：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择 来到达。共同点：都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。区分：动态规划每步所作出的选择依靠于相关子问题的解，因而只有在解出相关子问题之后才能 做出选择，而在贪心算法中，仅在当前状态下做出最好选择，所做的贪心选择可以依靠于以往所做 过的选择，但决不依靠于将来所做的选择，也不依懒于子问题的解。动态规划以自

6、底向上的方式 解各子问题，而贪心算法那么以自顶向下的方式进行，以迭代的方式做出相继的选择，而且每一步之 后将所求问题简化为规模更小的子问题。2、设有n=2k个运发动要进行循环赛，现设计一个满意以下要求的竞赛日程表：每个选手必需与其他n-l名选手竞赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。(1)假如11=2，循环赛最少需要进行(n-l)天；(2分)假如nW2,循环赛最少需要进行(n)天。(2分)(2)当n=23=8时，请画出循环赛日程表：(6分)选手第1天第2天第3天第4天第5天第6天第7天123456782143658734127856432187655678123465

7、87214378563412876543213、在字符串匹配中，模式串为acacdacb，假设采纳KMP算法，求NEXT值；(8分)假设某趟 不匹配的情形如下所示，那么指针i, j如何移动？ (2分)1正文：bcacacbabaabaa 模式： acacdacbJ解：*J12345678模式串aCacdacbNEXTj01123123指针i不动，指针j退回到NEXTj的位置，这里退回到3的位置，即模式向右移动3个位置4、有字符串acbcbacbcacbc,假设采纳lzw算法压缩，得到的压缩码是什么？(2分)要求写出字典。(8分)解：压缩码为：1, 3, 2, 5, 4, 6, 8字典如下:原字

8、符串压缩码序号aa1bb2cc3ac1c4cb3b5be2c6cba5a7acb4b8bca6a9aebe8c10五、算法设计题(15分)在8X8的国际象棋棋盘上，只摆5个皇后，每个皇后能掌握它所在的行、列和通过它所在的正方形 的两条对角线，要使这5个皇后能够掌握棋盘上的每一个格子(掌握的格子可以重复)，但皇后之间 不能相互攻击。下面是一种可能的摆法。请设计一个算法，求出全部可能的摆放。请用自然语言描自然与描述如下：对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。假设胜利了，便找到了 一个解；假设失败了，就整个重来，再随机产生此外一组王后的位置。这样作，直至找到解伪代码如下：

9、int queensLV(int rec)int k,i=l,found=l; 第 i 个皇后放在第 k 列while(i=N & found) found=0; for(k= 1 ;k=n) return 1;else return f(m,n-1 )+f(m+1 ,n);斯、蒙特卡罗算法各自的特点。 生有何关系？五、求解题(每题10分，共30分)(留意：要求给出求解过程)1、设多级图 G= (V, E), V= VI, V2, V3, V4, V5, V1=1, V2=2, 3,4, V3=5,6, V4=7,8,9, V5=10o其耗费如右表所示。请用动态规划法 求从顶点1到顶点10的最

10、小耗费路径。2、采纳快速排序对序列E,X,A,M,P,L,F根据字母挨 序，请写出每趟排序后的结果(10分)3、有无向图如下所示，请用Prim算法求出它的最 成树，要求写出求解过程。10b6979边耗费边耗费(1,2)4(5, 8)4(1,3)5(5, 9)6(1,4)3(6, 7)2(2,5)6(6, 8)7(2,6)7(6, 9)3(3,5)2(7, 10)5(3,6)5(8, 10)7L (4,5)9(9, 10)97)8次排小生5042六、算法设计题(15分)(留意：请用自然语言描述你的思路，再写伪代码。)1、子集和问题：子集和问题的一个实例为其中，S = %,/，是一个正整数的集合，c是一个正整数。子集和问题判定是否存在s的一个子集si,使得2% =。xeS试设计一个解子集和问题的回溯法，要求说明所采纳的算法思想（4分），并给出伪代码（8分）, 分析所给出的算法的时间简单度（3分）。