算法复习题精炼版

填空题动态规划算法的基本要素为最优子结构性质与重叠子问题性质1）算法分析中，记号0表示渐进上界，记号表示渐进下界，记号表示紧渐进界2）回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树3）分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）回溯法是回溯法是指（具有限界函数的深度优先生成法）回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架4）二分搜索算法是利用分治策略实现的算法5）衡量一个算法好坏的标准是时间复杂度低6）最长公共子序列算法利用的算法是动态规划法7）Strassen矩阵乘法是利用分治策略实现的算法8）回溯法搜索状态空间树是按照深度优先遍历的顺序9）算法中通常以自底向下的方式求解最优解的是动态规划法10）背包问题的贪心算法所需的计算时间为O（nlogn）11）0-1背包问题的回溯算法所需的计算时间为O（n2n）12）用动态规划算法解决最大字段和问题，其时间复杂性为n13）一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:—有穷性，确定性，可行性，输入，输出

1.算法的复杂性有时间复杂性和空间复杂性之分

2、程序是算法用某种程序设计语言的具体实现

3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的

4.矩阵连乘问题的算法可由动态规划设计实现

6、算法是指解决问题的一种方法或一个过程

7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法

8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

9、以深度优先方式系统搜索问题解的算法称为回溯法

10、数值概率算法常用于数值问题的求解

15、使用回溯法进行状态空间树裁剪分支时一般有两个标准约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题

16、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别

17、矩阵连乘问题的算法可由动态规划设计实现

19.贪心算法的基本要素是贪心选择质和最优子结构性质

21.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解

23、大整数乘积算法是用分治法来设计的

26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主耍区别

27.快速排序算法是基于分治策略的一种排序算法

30.回溯法是一种既带有系统性又带有跳跃性的搜索算法

33.回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数

34.任何可用计算机求解的问题所需的时间都与其规模有关

35.快速排序算法的性能取决于划分的对称性

37.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn,解空间树中每个内结点的孩子数是m o简答题

1.用计算机求解问题的步骤

1、问题分析

2、数学模型建立

3、算法设计与选择

4、算法指标

5、算法分析

6、算法实现

7、程序调试

8、结果整理文档编制

2.最优二叉搜索树问题的动态规划算法void binaiysearchtreeinta[],int b[],int n,int**s,int**wintfbri=1;i〈=n+1;i++w[i][i-l]=a[i-l];m[i][i-l]=0;forl=0;l=n-1;1++//——1是下标j-i的差fbri=l;i=n-l;i++{；j=i+l；w[i]U]=w[i]U-l]+a[j]+bU]m[i]U]=m[i][i-1]+m[i+1]U]+w[i][j];s丽=i；fork=i+l;k=j;k++；t=m[i][k-l]4-m[k4-l]U]+w[i][j]；m[i][j]=t；s[i][j]=k}}编写计算斐波那契Fibonacci数列的第n项函数fib no斐波那契数列为

0、

1、

1、

2、

2.算法定义算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程

3.算法的三要素

1、操作

2、控制结构

3、数据结构

4.算法具有以下5个属性有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成确定性算法中每一条指令必须有确切的含义不存在二义性只有一个入口和一个出口可行性一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的输入一个算法有零个或多个输入，这些输入取自于某个特定对象的集合输出一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法

8.分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同递归地解这些子问题，然后将各个子问题的解合并得到原问题的解

9.分治法所能解决的问题一般具有以下几个特征1该问题的规模缩小到一定的程度就可以容易地解决；2该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3利用该问题分解出的子问题的解可以合并为该问题的解；4该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题

10、分治法的基本步骤分治法在每一层递归上都有三个步骤1分解将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题;2解决若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；3合并将各个子问题的解合并为原问题的解

11.动态规划的基本思想动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略

13.分治法与动态规划法的相同点是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解两者的不同点是适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的而用分治法求解的问题，经分解得到的子问题往往是互相独立的

14.回溯法回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯扩大当前候选解的规模，以继续试探的过程称为向前试探

20.回溯法中常见的两类典型的解空间树是子集树和排列树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树这类子集树通常有2n个叶结点，遍历子集树需O2n计算时间当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树这类排列树通常有n!个叶结点遍历排列树需要On!计算时间

22.请叙述动态规划算法与贪心算法的异同共同点都需要最优子结构性质，都用来求有优化问题不同点动态规划每一步作一个选择一依赖于子问题的解贪心方法每一步作一个选择一不依赖于子问题的解动态规划方法的条件子问题的重叠性质可用贪心方法的条件最优子结构性质；贪心选择性质动态规划自底向上求解；贪心方法自顶向下求解可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用

23.请说明动态规划方法为什么需要最优子结构性质答最优子结构性质是指大问题的最优解包含子问题的最优解动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.

26.在算法复杂性分析中，

0、Q、这三个记号的意义是什么？在忽略常数因子的情况下，

0、Q、分别提供了算法运行时间的什么界？如果存在两个正常数c和NO,对于所有的N2N0,有|fN区C|gN|,则记作fN=OgN这时我们o说fN的阶不高于gN的阶若存在两个正常数C和自然数NO,使得当NNNO时有|fN|2C|gN|,记为fN尸QgN这时我们说fN的阶不低于gN的阶如果存在正常数cl,c2和nO,对于所有的nNnO,有cl|gN|0fN|4c21gN|0贝记作fN尸g,N

0、、分别提供了算法运行时间的上界、下界、平均

1.用动态规划策略求解最长公共子序列问题1给出计算最优值的递归方程2给定两个序列X={B,C,D,A},Y={A,B,C,B},请采用动态规划策略求出其最长公共子序列，要求给出过程eg]=当或时\/i=0j=0A01122最长公共子序列{BC}

2.对下列各组函数fn和gn,确定fn=Ogn或fn=Qgn或fn=0gn,并简要说明理由；1fn=2n gn=n!2fn=V^;g n=log n2；3fn=100gn=loglOO；4fn=n3gn=3n；5fn=3n gn=2n1fn=0gn因为gn的阶比fn的阶高因⑵fn=Qgn为gn的阶比fn的阶低⑶fn=Ogn因为gn与fn同阶4fn=Ogn因为gn的阶比fn的阶高⑸fn=Qgn因为gn的阶比fn的阶低

3.对下图所示的连通网络G,用克鲁斯卡尔Kruskal算法求G的最小生成树[请写出在算法执行过程中，依次加入T的边集TE中的边说明该算法的贪心策略和算法的基本思想,并简要分析算法的时间复杂度答:TE={3,4,2,3,1,5,4,64,5}贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边基本思想首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边时间复杂度为Oeloge4,请用分治策略设计递归的归并排序算法，并分析其时间复杂性要求分别给出divide、conquer、bine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶答Template classTypevoid MergeSortType a[],int left,int right{ifleftright{int i=left+right/2;MergeSort a,left,i;MergeSort a,i+1,right;Mergea,b,left,right;Copya,b,left,right;}Divide阶段的时间复杂性01Conquer阶段的时间复杂性2Tnbine阶段的时间复杂性0n当Tn={01n=1|用套用公式法a=2,b=2,nlog ba=n,fn尸n,因为fn与nlog ba同阶，J Tn=0nlogn

7.考虑在序列L.nL.n]中找最大最小元素的问题一个分治算法描述如下如果心2就直接求解否则，将序列等分成两个子序列A[L.n/2]和A[n/2+L.n],分别找出这两子序列的最大最小元素xl,yl和x2,y2；然后据此求出A[

1..n]的最大元素x=max{xl,x2}及最小元素y=min{yl,y2}请给出该算法计算时间Tn满足的递归方程，并解方程来确定算法的时间复杂度假定n=2k k为正整数答算法时间复杂度满足如下递归方程Tn=2Tn/2+2n2；T2=l因为n=2k k为正整数，所以，Tn尸T2k=2T2k-l+2=22T2k-2+22+2=2k-lT2+2k-2+…+23+22+2=2k-1+-+23+22+2因此，Tn尸n

8.考虑使用动态规划方法求解下列问题01背包数据如下表，求能够放入背包的最有价值的物品集合物品重量价值承重量.1wi viWwl=2vl=1212w2=l v2=10W=53w3=3v3=204w4=2v4=15如设Vi,j——前i个物品中能够装入承重量j的背包中的最大总价值请将如下递推式填写完整V0,j=00个物品，Vi,0=0承重量0Vi,j=Vi-1j第i个物品不能装入，j〈wi超重Vi,j=max{,}jwi不超重i在最优子集中i不在最优子集中自底向上按行或列填写下表V j=123451答11111i=0000000V0J=00个物品,Vi,010=0承重量020Vi,j=Vi-l,j第i个物30品不能装入，jvwi超A n重）Vi,j=max{vi+Vi-1J-wj,Vi-1,j}jwi不超重i在最优子集中i不在最优子集中V2345j=o19,请画出用回溯法解4皇后问i=0000000题的解空间树和搜索空间00121212121树:201012222222解空间树:30101222303240101525303711,请画出用回溯法解n=3的0/背包问题的解空间树和当三个物品的重量为｛20,15,10｝,价值为｛20,30,25）,背包容量为25时搜索空间树答。