算法期末作业题(精炼版)

《算法期末作业题(精炼版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、填空题动态规划算法的基本要素为：最优子结构性质与重叠子问题性质1)算法分析中，记号O表示渐进上界，记号表示渐进下界，记号表示紧渐进界。2)回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。3)分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。回溯法是指（具有限界函数的深度优先生成法）。回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排

2、列树）算法框架。4)二分搜索算法是利用分治策略实现的算法。5)衡量一个算法好坏的标准是时间复杂度低6)最长公共子序列算法利用的算法是动态规划法7)Strassen矩阵乘法是利用分治策略实现的算法8)回溯法搜索状态空间树是按照深度优先遍历的顺序。9)算法中通常以自底向下的方式求解最优解的是动态规划法10)背包问题的贪心算法所需的计算时间为O（nlogn）11)0-1背包问题的回溯算法所需的计算时间为O（n2n）12)用动态规划算法解决最大字段和问题，其时间复杂性为n13)一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的

3、一系列运算，此外，算法还应具有以下五个重要特性:_有穷性，确定性，可行性，输入，输出。矚慫润厲钐瘗睞枥庑赖。1.算法的复杂性有时间复杂性和空间复杂性之分。聞創沟燴鐺險爱氇谴净。2、程序是算法     用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。6、算法是指解决问题的一种方法或一个过程。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统

4、搜索问题解的算法称为回溯法。10、数值概率算法常用于数值问题的求解。1513/13、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。残骛楼諍锩瀨濟溆塹籟。16、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。17、矩阵连乘问题的算法可由动态规划设计实现。19.贪心算法的基本要素是贪心选择质和最优子结构性质。酽锕极額閉镇桧猪訣锥。21.

5、动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。彈贸摄尔霁毙攬砖卤庑。23、大整数乘积算法是用分治法来设计的。26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。27.快速排序算法是基于分治策略的一种排序算法。30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。謀荞抟箧飆鐸怼类蒋薔。33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。厦礴恳蹒骈時盡继價骚。34.任何可用计算机求解的问题所需的时间都与其规模有关。35.快速排序算法的

6、性能取决于划分的对称性。37.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn，解空间树中每个内结点的孩子数是m。茕桢广鳓鯡选块网羈泪。简答题1.用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制鹅娅尽損鹌惨歷茏鴛賴。2.最优二叉搜索树问题的动态规划算法voidbinarysearchtree(inta[],intb[],intn,int**m,int**s,int**w)籟丛妈羥为贍偾蛏练淨。{inti,j,k,t,l;for(i=1;i

7、<=n+1;i++){13/13w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w[i][j];if(t

8、斐波那契（Fibonacci）数列的第n项函数fib（n）。　　斐波那契数列为：0、1、1、2、3、……，即：　　fib(0)=0;　　fib(1)=1;　　fib(n)=fib(n-1)+f