算法复习试题.docx
算法复习试题（）2022一、填空题（每空1分，共15分）1、一个正确的算法应具有五个特性：（有穷性）、（确定性）、（能行性）、输入和输出。2、算法的时间简单性是算法运行所需要的（计算机资源）的量，这个量只依靠于（求解问题的规模）、（详细的输入数据）和（算法本身的设计）。3、函数的渐进表达式为（T（N）,函数log。的渐进表达式为（3n ）。4、快速排序和归并排序策略上是相同的，都是用的（递归与分治）算法。5、对于问题Q,假设满意（Q是NP困难的）、（ Q£NP）那么称Q为NP完全的。6、要求出一个问题全部的可行解，一般要用（回溯）算法。7、通常能用动态规划法求解的问题应具备（最优子结构）和（或者是重叠字问题）相像）的性质。二、选择题（每题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.需要超过多项式时间算法求解的问题是易处理的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/64V可以求得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 a<D(b)所以 T(n)=O (n2)4、设MC(x)是解某个判定问题的蒙特卡罗算法，且是一个p正确的偏真算法。现有如下算法MC2(x), 试分析该算法的正确率。bool MC2(x) if(MC(x) return true; else return MC(x);解：蒙特卡罗算法的特点是只要有一次调用为真，结果就为真，所以该算法的正确率为：1-(1-P)N N为调用的次数四、问答及求解题(每题10分，共40分)1、什么是贪心选择性质？(2分)贪心算法与动态规划算法有什么共同点？(4分)又有什么区分？ (4分)答：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择 来到达。共同点：都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。区分：动态规划每步所作出的选择依靠于相关子问题的解，因而只有在解出相关子问题之后才能 做出选择，而在贪心算法中，仅在当前状态下做出最好选择，所做的贪心选择可以依靠于以往所做 过的选择，但决不依靠于将来所做的选择，也不依懒于子问题的解。动态规划以自底向上的方式 解各子问题，而贪心算法那么以自顶向下的方式进行，以迭代的方式做出相继的选择，而且每一步之 后将所求问题简化为规模更小的子问题。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天12345678214365873412785643218765567812346587214378563412876543213、在字符串匹配中，模式串为"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字典如下:原字符串压缩码序号aa1bb2cc3ac1c4cb3b5be2c6cba5a7acb4b8bca6a9aebe8c10五、算法设计题(15分)在8X8的国际象棋棋盘上，只摆5个皇后，每个皇后能掌握它所在的行、列和通过它所在的正方形 的两条对角线，要使这5个皇后能够掌握棋盘上的每一个格子(掌握的格子可以重复)，但皇后之间 不能相互攻击。下面是一种可能的摆法。请设计一个算法，求出全部可能的摆放。请用自然语言描自然与描述如下：对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。假设胜利了，便找到了 一个解；假设失败了，就整个重来，再随机产生此外一组王后的位置。这样作，直至找到解伪代码如下：int queensLV(int rec)int k,i=l,found=l; 第 i 个皇后放在第 k 列while(i<=N && found) found=0; for(k= 1 ;k<=N && !found; k+) /预备在当前这一行放置皇后reci=k;if(place(rec,i)/推断该位置能否放置皇后if(rand()%2=0) found= 1;即便能放，也还要进行随机处理，只有50%的机会 if (found) i+; /放下一行 return found; /假如found-1,表示找到一种方案解法二：回溯法（最好用这种方法）自然语言描述： 在棋盘的第一行的任意位置安放第一只皇后。 紧接着，我们就来放其次行，其次行的安放就要受一些限制了，由于与第一行的 皇后在同一列或同一对角线的位置上是不能安放皇后的，接下来是第三行，,或许我们会遇到这种状况：在摆到某一行的时候，无论皇后摆放在什么位置，她 都会被其它行的皇后吃掉，这时就必需要回溯，将前面的皇后重新摆放，伪代码如下：（注释可以不写）数据结构说明： 数组recn表示棋盘。假设reci=j, li, jWn,表示棋盘的第i行第j列上有皇后。 数组Cj = l表示第j列上无皇后，IWjWn。 数组Dk = l表示第k条下行（）对角线上无皇后。数组Uk=1表示第k条上行（/）对角线上无皇后。 Record（sJ） k = s -j + n;recs = j; Cj = 0; Ds + j - 1 = 0; Uk = 0; Move-Off（s, j） k = s - j + n;recs = 0; Cj = 1; Ds+j- 1 = 1; Uk = 1; Safe（s,j） k = s -j + n;if（Cj && Uk && Ds+j- 1） return trueelse return false; 一、填空题（每空1分，共15分）1、算法是由假设干条指令组成的（）序列，且满意（）、（）、输入和输出这四条性质。2、一个算法的时空性能是指该算法的（）简单性和（）简单性，前者是算法包含 的计算量，后者是算法需要的存储量。3、函数3n3+10n的渐进表达式为（），函数log/的渐进表达式为（）。4、贪心法得到的解（）（肯定/不肯定）是最优解，用回溯法得到的解（）（肯定/不肯定）是最优解。）算法。）的性质。5、通常能用动态规划法求解的问题应具备（6、快速排序和归并排序策略上是相同的，都是用的（7、计算机产生的随机数都是有周期的，所以被称为（）随机数。）的，在计算速度上是（）的。8、计算模型RAM、RASP以及TM在计算力量上是（二、推断题（每题2分，共10分）（）1、用贪心法求0-1背包可以获得最优解。（）2、n个矩阵连乘积的计算挨次问题同构于凸（n+1）边形的三角剖分问题。）3、分支限界法一般是以深度优先的方式搜寻解空间树。()4、回溯法是最常用的解题方法，有“通用的解题法”之称。()5、可以由多项式时间算法求解的问题是难处理的。三、计算题(共20分)(留意：要求写出计算过程)1、对于下面的各组函数/()和g()，确定/()= O(g()或)=O(g()，或)=)(g(m)并简述理由。(每题5分，共1。分)(1) /()= k)g/,g()= 41og + 10(2) f(n) = 3fg(n) = 5,J 2、假设某算法在输入规模为n时的计算时间为T()= 3x2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法 在t秒内能解输入规模为多大的问题？ (5分)3、分析以下程序段所代表的算法的时间简单性：(5分)四1、2、四1、2、int f(int m, int n) if (m>=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的最小耗费路径。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分）。
