算法复习试题

1、算法复习试题（仅供参考）2009一、填空题（每空1分，共15分）1、一个正确的算法应当具有五个特性：（有穷性）、（确定性）、（能行性）、输入和输出。2、 算法的时间复杂性是算法运行所需要的（计算机资源）的量，这个量只依赖于（求解问题的规模）、（具体的输入数据）和（算法本身的设计）。3、 函数的渐进表达式为（T（N），函数错误！未找到引用源。的渐进表达式为（3n错误！未找到引用源。）。4、快速排序和归并排序策略上是相同的，都是用的（ 递归与分治 ）算法。5、 对于问题Q,若满足（ Q是NP困难的）、（QENP）则称Q为NP完全的。6、要求出一个问题所有的可行解，一般要用（ 回溯 ）算法。7、通常

2、能用动态规划法求解的问题应具备 撮优子结构）和（或者是重叠字问题）相似）的性质。二、选择题（每小题2分，共10分）（D ）1、 概率算法是一种非确定性地选择下一计算步骤的方法，（）算法主要目的是消除算法所需计算时间对输入实例的依赖。数值概率算法B.蒙特卡罗算法C.拉斯维加斯算法D.舍伍得算法（B）2、 ASCII码压缩方法经过两级压缩之后可以减少（）的存储空间。A. 62.5%B. 56.25%C. 50%D. 65%（A）3、 P类问题与NP类问题的关系是（ ）A.包含于B.包含C.属于 D.等于（C ） 4、以下关于判定问题难易处理的叙述中正确的是（）。可以由多项式时间算法求解的问题是难处

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

4、为t秒有n3/.V=X3/64V可以求得X=4n2、按照渐近阶从低到高的顺序排列下列表达式：4n2，logn， 3n，n!，n2/3 解：由低到高为：n2/3 log n 4n2 3n n!3、求解递归方程T(1) 二 1T (n) = 2T (n /3) + n 2解：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-1名选手比赛各一次；每个选手一天至多只能赛一次;循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行（n-1）天；（2分）如果nN2k，循环赛最少需要进行（n）天。（2分）（2）当n=23=8时，请画出循环赛日程表：（6分）选手第1天第2天第3天第4天第5天第6天第7天1234567821436

7、5873412785643218765567812346587214378563412876543213、在字符串匹配中，模式串为“acacdacb”，若采用KMP算法，求NEXT值；（8分）若某趟 不匹配的情形如下所示，则指针i，j如何移动？ （2分）i正文：ca ca cb a b a a b a a模式： a c a c d a c bj解：j12345678模式串acacdacbNEXTj01123123指针i不动，指针j退回到NEXT j的位置，这里退回到3的位置，即模式向右移动3个位置4、有字符串acbcbacbcacbc，若采用lzw算法压缩，得到的压缩码是什么？ （2分）要求写

8、出字典。（8分）解：压缩码为：1，3，2，5，4，6，8字典如下:：原字符串压缩码序号aa1bb2cc3ac1c4cb3b5bc2c6cba5a7acb4b8bca6a9acbc8c10五、算法设计题（15分）在8X8的国际象棋棋盘上，只摆5个皇后，每个皇后能控制它所在的行、列和通过它所在的正方形解法一：满足题目要求的八皇后问题算法如下：（用的是书上的Las Vegas算法）自然与描述如下：对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。若成功了，便找到了 一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，直至找到 解伪代码如下：int queensLV(i

9、nt rec)int k,i=1,found=1; /第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);四、问答题（每题5分，共10分）1、什么是概率算法？试说说舍伍德、拉斯维加斯、蒙特卡罗算法各自的特点。2、什么是NP问题？什么是NP完全问题？二者有何关系?五、求解题（每题10分，共30分）边耗费边耗费(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)7(4, 5)9(9, 10)9(5, 7)8（注意：要求给出求解过程）1、设多级图 G= （V,E）,V= V1,V2,V3,V4,V5, V1=1,V2=2,3,4, V3=5,6, V4=7,8,9, V5=10。其耗费如右表所示。请用动态规划法 求从顶点1到顶点10的最小耗费路径。2、采用快速排序对序列E,X,A,M,P,L,F按照字母顺序排序，请写出每趟排序后的结果（10分）3、有无向图如下所示，请用Prim算法求出它的最小生成树，要求写出求解过程。六、算法设计题（15分）（注意：请用自然语言描述你的思路，再写伪代码。）1、子