算法设计与分析综合练习题

《算法设计与分析综合练习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》综合练习题一．填空题1.算法是指解决问题的一种方法和一个过程，它具有如下四条性质：______、______、______、和______。2.函数3n2+10nlogn的渐近表达式为______；函数3n3+2n的渐近表达式为______。3.算法的复杂性分两种，分别为______和______。4.二分搜索算法在最坏情况下的时间复杂性是______；快速排序算法MergeSort在平均情况下的时间复杂性是______。5.动态规划法的两个基本要素是______和______。6.动态规划算法的一个变形是______

2、方法，该方法为每个子问题建立一个______，用来保存子问题的解并用于表示子问题是否已求解。7.能用贪心算法求得最优解的问题应具有的两个重要性质是______和______。8.贪心算法总是作出在当前看来最好的选择，并不从______最优上加以考虑，只是在某种意义上的______最优选择。9.回溯法有______之称，它以______的方式搜索包括问题所有解的解空间树。10.从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法，最常见的有以下两种：______分支限界法或______分支限界法。11．算法是由若干条指令组成的有穷序

3、列，满足如下四条性质：______、______、______、和______。12.函数logn2+10nlogn的渐近表达式为______；函数n3logn+2n的渐近表达式为______。13.算法的复杂性分两种，需要时间资源的量称为______，需要空间资源的量称为______。14.合并排序算法在最坏情况下的时间复杂性是______；快速排序算法在最坏情况下的时间复杂性是______。15.可以用动态规划法求解的问题应具有的两个重要性质是______和______。16.备忘录方法是______算法的一个变形，该方法为每个子问

4、题建立一个______，用来保存子问题的解并用于表示子问题是否已求解。17.贪心算法的两个基本要素是______和______。18.使用贪心算法解决活动安排问题时使用了______的贪心选择策略，而在解决汽车加油问题中使用了______的贪心选择策略。19.通过回溯法解题时，经常遇到两种典型的解空间树，分别为______和______。20.分支限界法常以______或以______的方式搜索问题的解空间树。21.算法的复杂性有__________和__________之分。22.算法的时间复杂性函数用_______表示，其中参数n是

5、指___________。23.已知渐进意义下的记号O,W,Q,判断下列几组函数的关系：f(n)=log2n,g(n)=logn，满足f(n)=______(g(n))；f(n)=logn2,g(n)=logn+5，满足f(n)=______(g(n))；f(n)=logn2,g(n)=n1/2,满足f(n)=______(g(n))；f(n)=10,g(n)=log1010,满足f(n)=______(g(n))；f(n)=log4n,g(n)=4logn，满足f(n)=______(g(n))；f(n)=logn2,g(n)=5lo

6、gn，满足f(n)=______(g(n))；f(n)=1,g(n)=log1010,满足f(n)=______(g(n))。24.函数n2+2n/10的渐近表达式为______；函数21+1/n2的渐近表达式为______；函数4n2+2n的渐近表达式为______。25.可用动态规划法求解的问题应具有的两个重要性质是________和_________。26.贪心算法的两个基本要素是______和______。27._________与分治法的基本思想非常相似，但是与分治法不同，适用该方法的问题，经分解得到的子问题往往不是互相独立的

7、。28.使用贪心算法解决活动安排问题时使用了_________优先的贪心选择策略，而在解决一般背包问题中使用了__________优先的贪心选择策略。29.通过回溯法解题时，经常遇到两种典型的解空间树，分别为______和______。30.分支限界法类似于回溯法，两者对于当前扩展结点所采用的______方式不同。31.使用贪心算法解决活动安排问题时使用了_________优先的贪心选择策略，而在解决一般背包问题中使用了__________优先的贪心选择策略。32.当问题的最优解包含了其子问题的最优解时，称该问题具有________性质

8、。33.动态规划法与________法的基本思想非常相似，但不同的是适用后者方法的问题，经分解得到的子问题往往是互相独立的。34.可用动态规划法求解的问题应具有的两个重要性质是最优子结构性质和_______