参考答案@算法设计与分析综合练习题 -(3)

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

1、《算法设计与分析》综合练习题一．填空题1.算法是指解决问题的一种方法和一个过程，它具有如下五条性质：输入_、_输出、_确定,有穷_、和_可行。2.函数3n2+10nlogn的渐近表达式为_O(n2)；函数3n3+2n的渐近表达式为_O(n3)__。3.算法的复杂性分两种，分别为_时间复杂度_和_空间复杂度__。4.二分搜索算法在最坏情况下的时间复杂性是_O(nlog2n)_；快速排序算法在平均情况下的时间复杂性是__O(nlog2n)_,最坏情况下的时间复杂度是O(n2)。6.动态规划算法的一个变形是备忘录_方法，该方法为每个子问题建立一个_解向量_，用来保存子问题的解并用于表示子问题是

2、否已求解。7.能用贪心算法求得最优解的问题应具有的两个重要性质是_贪心选择_和_最优子结构_。8.贪心算法总是作出在当前看来最好的选择，并不从_整体_最优上加以考虑，只是在某种意义上的_局部最优选择。9.回溯法有_试探法_之称，它以_先根遍历_的方式搜索包括问题所有解的解空间树。10.从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法，最常见的有以下两种：_队列式分支限界法或_优先队列式_分支限界法。12.函数logn2+10nlogn的渐近表达式为_O(nlogn)__；函数n3logn+2n的渐近表达式为_O(n3log2n)_。14.合并排序算法在最坏情况下的时间复杂性是_

3、O(nlog2n)_；快速排序算法在最坏情况下的时间复杂性是_O(n2)_。20.分支限界法常以_广度优先____的方式搜索问题的解空间树。22.算法的时间复杂性函数用_渐近函数O(g(n))_表示，其中参数n是指_输入规模__。23.已知渐进意义下的记号O,W,Q,判断下列几组函数的关系：f(n)=log2n,g(n)=logn，满足f(n)=_W_(g(n))；f(n)=logn2,g(n)=logn+5，满足f(n)=_W_(g(n))；f(n)=logn2,g(n)=n1/2,满足f(n)=_O_(g(n))；f(n)=10,g(n)=log1010,满足f(n)=_Q(g(n)

4、)；f(n)=log4n,g(n)=4logn，满足f(n)=W_(g(n))；f(n)=logn2,g(n)=5logn，满足f(n)=_Q_(g(n))；f(n)=1,g(n)=log1010,满足f(n)=_Q_(g(n))。24.函数n2+2n/10的渐近表达式为_O(2n)_；函数21+1/n2的渐近表达式为_O(1)_；函数4n2+2n的渐近表达式为_O(2n)_。32.当问题的最优解包含了其子问题的最优解时，称该问题具有__最优子结构_性质。33.动态规划法与_分治__法的基本思想非常相似，但不同的是适用后者方法的问题，经分解得到的子问题往往是互相独立的。34.可用动态规划

5、法求解的问题应具有的两个重要性质是最优子结构性质和_子问题的重叠性_。6.分支限界法类似于回溯法，两者对于解空间树的搜索方式_方式不同。二．名词解释和问答题1．什么是算法？P12．算法具有的特性是什么？P13．时间复杂度、空间复杂度P7-95．递归算法P1476．分治法的基本思想P1547．动态规划的基本要素和解题步骤P1898．贪心算法的基本要素P1629．描述回溯法的基本思想P202三．算法复杂度分析题1.用主定理解以下时间复杂度函数的递归方程，并给出简要计算过程：(1)T（n）=T(n/4)+O(n)+O(n/2)=···=T（1）+O（1+2+4+···+n）=O（2n-1）=O

6、（n）(2)T（n）=4T(n/4)+O(n)+O(n/2)=···=nT（1）+O（1+2+4+···+n）=O（n）+O（2n-1）=O（n）(3)T（n）=9T(n/4)+O(n)+O(n/2)=···=3log2nT（1）+O（1+2+4+···+n）=O（n）+O（2n-1）=O（n）(4)T（n）=4T(n/9)+O(n)+O(n/2)=···=2log3nT（1）+O（1+2+4+···+n）=O（n）+O（2n-1）=O（n）2.求解如下递归式，已知T(1)=1，a、b、c均为常数且a=b=c=1。（1）T(n)=aT(n-1)+bnT(n)=T(n-1)+n=T(n-2

7、)+n-1+n=.···=T（1）+2+3+4+···+n=n（n-1）/2（2）T(n)=aT(n/2)+bncT(n)=T(n/2)+n=T(n/4)+n/2+n=T(n/8)+n/4+n/2+n=```=T(1)+2+4+8+```+n/2+n=2n-13.汉诺塔问题的时间复杂性的递推函数如下，试分析其时间复杂性。T(n)=4T（n-2）+2O（1）+O（1）=····=2n+（2n-1）*O（1）时间复杂度为O（2n）四．算