算法复习试题

《算法复习试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、(D)1、(B)2、(A)3、(C)4、(C)5、）的存储空问。D.65%D.等于A.2n+1-lC.n!D.2n算法复习试题（仅供参考）2009一、填空题（每空1分，共15分）1、一个正确的算法应当具有五个特性：（有穷性）、（确定性）、（能行性）、输入和输出。2、算法的时间复杂性是算法运行所需要的（计算机资源）的这个:W:只依赖于（求解问题的规模）、（具体的输入数据）和（算法本身的设计〉。3、函数的渐进表达式为（T（N）），函数错误!未找到引用源。的渐进表达式为（3n错误!未找到引用源。）。4、快速

2、排序和归并排序策略上是相同的，都是用的（递归与分治）算法。5、对于问题Q，若满足（Q是NP困难的）、（Q^NP）则称Q为NP完全的。6、要求出一个问题所有的可行解，一般要用（回溯）算法。7、通常能用动态规划法求解的问题应具备（最优子结构）和（或者是重叠字问题）相似）的性质。二、选择题（每小题2分，共10分）概率算法是一种非确定性地选择下一计算步骤的方法，（）算法主要目的是消除算法所需计算时间对输入实例的依赖。A.数值概率算法B.蒙特卡罗算法C.拉斯维加斯算法D.舍伍得算法ASCII码压缩方法经过两级压

3、缩之后可以减少（A.62.5%B.56.25%C.50%P类问题与NP类问题的关系是（）A.包含于B.包含C.属于以下关于判定问题难易处理的叙述中正确的是（）。A.付以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.耑要超过多项式时间算法求解的问题是不能处理的对于含有n个元素的排列树问题，最坏情况下计算时间复杂性为（）。三、计算题(每小题5分，共20分)(注意：要求写出计算过程)1、设某算法的时间复杂度为O(i?)。在某

4、台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模多大的问题？解：设在本台计算机上的速度为V,设在另一台计算机上的输入规模为X由计算时间都为t秒有n3/.V=X3/64V可以求得X=4n2、按照渐近阶从低到高的顺序排列下列表达式：4n2,logn,3n,n!,n273解：由低到高为：n23logn4n23nn!3、求解递归方程T(1)=12⑻=2r("/3)+"2解：D(n)=n2且a=2D(3)=32=9a

5、)所以T(n)=O(n2)4、设MC(x)是解某个判定问题的蒙特卡罗算法，且是一个p正确的偏真算法。现有如下算法MC2(x),试分析该算法的正确率。boolMC2(x){if(MC(x))returntrue;elsereturnMC(x);}解：蒙特卡罗算法的特点是只要有一次调用为真，结果就为真，所以该算法的正确率为：1-(1-p)NN为调用的次数四、问答及求解题(每小题10分，共40分)1、什么是贪心选择性质？(2分)贪心算法与动态规划算法有什么共同点？(4分)又有什么区别？(4分)答：所谓贪心选

6、择性质是指所求问题的整体S优解可以通过一系列局部S优解的选择，即贪心选择来达到。共同点：都需要将M题划分为一个个子H题，然后通过解决这些子W题來解决最终闷题。区别：①动态规划每步所作岀的选择依赖于相关子问题的解，因而只有在解出相关子问题之后才能做出选择，而在贪心算法中，仅在当前状态下做出最好选择，所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依懒于子问题的解。②动态规划以自底向上的方式解各子问题，而贪心算法则以自顶向下的方式进行，以迭代的方式做出相继的选择，而且每一步之后将

7、所求H题简化为规模更小的子闷题。2、设有11=2＜个运动贝要进行循环赛，现设计一个满足以下要求的比赛口程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次;③循环赛要在最短时间内完成。（1）如果n=2k,循环赛最少需要进行（n-1）天；（2分）如果n关2k,循环赛最少需要进行（n）天。（2分）（2）当n=23=8时，请画出循环赛日程表：（6分）选手第1天第2天第3天第4天第5天第6天第7天12345678214365873412785643218765567812346587

8、214378563412876543213、在字符串匹配巾，模式串为“acacdacb”，若采川KMP算法，①求NEXT值；（8分）②若某趟不匹配的情形如下所示，贝11指针i,j如何移动？（2分）1正文：".bcacacbabaabaa…模式：acacdacb解：①參J12345678模式串aCacdacbNEXT[jl01123123②指针i不动，指针j退回到NEXTfjl的位置，这里退回到3的位置，即模式向右移动3个位貫4、有字符串acbcbacbc