《算法分析与设计》期末考试复习题纲

1、优选文档算法分析与设计期末复习题一、选择题1.算法必定具备输入、输出和（D）等4个特点。A可行性和安全性B确定性和易读性C有穷性和安全性D有穷性和确定性2.算法分析中，记号O表示（B），记号表示（A）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界假定某算法在输入规模为n时的计算时间为T(n)=3*2n。在某台计算机上实现并达成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（B）解题方法：3*2n*64=3*2xAn+8Bn+6Cn+7Dn+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)

2、=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（C）。AO(logN)BO(N)CO(NlogN)DO(N2logN)5.直接或间接调用自己的算法称为（B）。A贪心算法B递归算法C迭代算法D回溯法6.Fibonacci数列中，第4个和第11个数分别是（D）。A5，89B3，89C5，144D3，1447.在有8个极点的凸多边形的三角剖分中，恰有（B）。A6条弦和7个三角形B5条弦和6个三角形C6条弦和6个三角形D5条弦和5个三角形8.一个问题可用动向规划算法或贪心算法求解的重点特点是问题的（B）。A重叠子问题B最优子结构性质C贪心选择性质D定义最优解9.以下哪个问题不用贪心法求

3、解（C）。A哈夫曼编码问题B单源最短路径问题C最大团问题D最小生成树问题10.以下算法中平常以自底向上的方式求解最优解的是（B）。A备忘录法B动向规划法C贪心法D回溯法以下算法中不能够解决0/1背包问题的是（A）。A贪心法B动向规划C回溯法D分支限界法12.以下哪个问题能够用贪心算法求解（D）。.优选文档ALCS问题B批办理作业问题C0-1背包问题D哈夫曼编码问题13.用回溯法求解最优装载问题时，若待选物品为m种，则该问题的解空间树的结点个数为（）。Am!B2m+1C2m+1-1D2m14.二分找寻算法是利用（A）实现的算法。A分治策略B动向规划法C贪心法D回溯法15.以下不是动向规划算法基本

4、步骤的是（B）。P44A找出最优解的性质B结构最优解C算出最优解(应该是最优值)D定义最优解16.下面问题（B）不能够使用贪心法解决。A单源最短路径问题BN皇后问题C最小开销生成树问题D背包问题使用二分找寻算法在n个有序元素表中找寻一个特定元素，在最好情况和最坏情况下找寻的时间复杂性分别为（A）。P17AO(1)，O(logn)BO(n)，O(logn)CO(1)，O(nlogn)DO(n)，O(nlogn)18.优先行列式分支限界法采纳扩展结点的原则是（C）。P162A先进先出B后进先出C结点的优先级D随机19.下面不是分支界线法找寻方式的是（D）。P161A广度优先B最小耗资优先C最大效益

5、优先D深度优先20.分支限界法解最大团问题时，活结点表的组织形式是（B）。A最小堆B最大堆C栈D数组21.以下对于计算机算法的描绘不正确的选项是（C）。P1A算法是指解决问题的一种方法或一个过程B算法是若干指令的有穷序列算法必定要有输入和输出D算法是编程的思想22.以下对于凸多边形最优三角剖分问题描绘不正确的选项是（A）。An+1个矩阵连乘的完好加括号和n个点的凸多边形的三角剖分对应B在有n个极点的凸多边形的三角剖分中，恰有n-3条弦C该问题能够用动向规划法来求解D在有n个极点的凸多边形的三角剖分中，恰有n-2个三角形23.动向规划法求解问题的基本步骤不包括（C）。P44A递归地定义最优值B分

6、析最优解的性质，并刻画其结构特点C依照计算最优值时获取的信息，结构最优解(能够省去的)D以自底向上的方式计算出最优值24.分治法所能解决的问题应拥有的重点特点是（C）。P16.优选文档A该问题的规模减小到必然的程度就能够简单地解决B该问题能够分解为若干个规模较小的相同问题C利用该问题分解出的子问题的解能够归并为该问题的解D该问题所分解出的各个子问题是互相独立的25.以下对于回溯法的描绘不正确的选项是（D）。P114A回溯法也称为试试法B回溯法有“通用解题法”之称C回溯法是一种能防范不用要找寻的穷举式找寻法D用回溯法对解空间作深度优先找寻时只能用递归方法实现26.常有的两种分支限界法为（D）。P

7、161广度优先分支限界法与深度优先分支限界法；行列式（FIFO）分支限界法与货仓式分支限界法；排列树法与子集树法；行列式（FIFO）分支限界法与优先行列式分支限界法；二、填空题1.f(n)=3n2+10的渐近性态f(n)=O(n2)，g(n)=10log3n的渐近性态g(n)=O(n)。2.一个“好”的算法应拥有正确性、可读性、强健性和高效率和低储藏量需求等特点。3.算法的时间复杂性函数表示为C=F(N,I,A)，分析算法复杂性的目的在于比较求解赞成问题的两个不相同算法的效率的效率。4.组成递归式的两个基本要素是递归的界线条件和递归的定义。5.单源最短路径问题可用分支限界法和贪心算法求解。6.

8、用分治法实现迅速排序算法时，最好情况下的时间复杂性为O(nlogn)，最坏情况下的时间复杂性为O(n2)，该算法所需的时间与运行时间和区分两方面要素有关。P267.0-1背包问题的解空间树为完好二叉树；n后问题的解空间树为排列树；8.常有的分支限界法有行列式（FIFO）分支限界法和优先行列式分支限界法。9.回溯法找寻解空间树常常用的两种剪枝函数为拘束函数和剪枝函数。10.分支限界法解最大团问题时，活结点表的组织形式是最大堆；分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆。三、算法填空题递归求解Hanoi塔问题/阶乘问题。例1:阶乘函数n!P12阶乘的非递归方式定义：n!n(n1)(

9、n2)21试写出阶乖的递归式及算法。递归式为：1n0界线条件n!n(n1)!n0.优选文档递归方程递归算法：intfactorial(intn)if(n=0)return1;递归出口returnn*factorial(n-1);递归调用例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15其中Hanoi(intn,inta,intc,intb)表示将塔座A上的n个盘子移至塔座C，以塔座B为协助。Move(a,c)表示将塔座a上编号为n的圆盘移至塔座c上。voidhanoi(intn,inta,intc,intb)if(n0)hanoi(n-1,a,b,c);move(a,c);h

10、anoi(n-1,b,c,a);用分治法求解迅速排序问题。迅速排序算法P25、作业、课件第2章（2）42页-50页templatevoidQuickSort(Typea,intp,intr)if(pr)intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r)；.优选文档Partition函数的详细实现templateintPartition(Typea,intp,intr)inti=p,j=r+1;Typex=ap;将x的元素互换到右边地区while(true)while(a+ix&ix);if(i=j)break;Swap(ai,

11、aj);ap=aj;aj=x;returnj;用贪心算法求解最优装载问题。最优装载问题P95课件第4章(2)第3-8页templatevoidLoading(intx,Typew,Typec,intn)int*t=newintn+1;Sort(w,t,n);for(inti=1;i=n;i+)xi=0;for(intj=1;j=n&wtj=c;j+)xti=1;c-=wtj;.优选文档用回溯法求解0-1背包/批办理作业调动/最大团问题，要会画解空间树。例1：用回溯法求解0-1背包P133课件第5章(2)第24-38页templateclassKnapprivate:TypepBound(int

12、i);/计算上界voidBacktrack(inti);Typewc;/背包括量intn;/物品数Typew*w;/物品重量数组Typep*p;/物品价值数组Typewcw;/目前重量Typepcp;/目前价值Typepbestp;/目前最优价值;voidKnap:Backtrack(inti)if(in)bestp=cp;return;if(cw+wibestp)/进入右子树Backtrack(i+1);TypepKnap:Bound(inti)Typewcleft=c-cw;/节余的背包括量Typepb=cp;/b为目前价值依次装入单位重量价值高的整个物品.优选文档while(i=n&wi

13、=cleft)cleft-=wi;b+=pi;i+;if(i=n)/装入物品的一部分b+=pi*cleft/wi;returnb;/返回上界classObject/物品类friendintKnapsack(int*,int*,int,int);public:intoperator=a.d);intID;/物品编号floatd;/单位重量价值;TypepKnapsack(Typepp,Typeww,Typewc,intn)/为TypepKnapsack初始化TypewW=0;/总重量TypepP=0;/总价值Object*Q=newObjectn;/创办物品数组，下标从0开始for(inti=1

14、;i=n;i+)/初始物品数组数据Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c)/能装入所有物品returnP;if(W=c)/能装入所有物品returnP;QuickSort(Q,0,n-1);/依物品单位重量价值非增排序.优选文档KnapK;K.p=newTypepn+1;K.w=newTypewn+1;for(inti=1;in)for(intj=1;j=n;j+)bestxj=xj;bestf=f;elsefor(intj=i;jf1)?f2i-1:f1)+mxj2;f+=f2i;if(fn)for(intj=1;j=n;j+)bestxj

15、=xj;bestn=cn;return;/判断第i个极点可否与已选极点都有边相连intOK=1;for(intj=1;jbestn)/如有可能在右子树中找到更大的团，则进入右子树xi=0;Backtrack(i+1);计算时间：O(n2n)四、简答题1.请简述使用动向规划算法解题的基本步骤。P44动向规划的设计分为以下4个步骤：(1)找出最优解的性质，并刻划其结构特点。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)依照计算最优值时获取的信息，结构最优解。2.简述动向规划方法与分治法的异同。P44相同点：动向规划算法与分治法近似，其基本思想也是将待求解问题分解成若干个子问题,

16、尔后从这些子问题的解获取原问题的解。不相同点：分治法的子问题互相独立且与原问题相同。与分治法不相同的是，适合于动向规划求解的问题，经分解获取的子问题常常不是互相独立的。也就是各个子问题包括公共的子子问题。3.试比较Prim算法与Kruskal算法的异同。105-P107.优选文档相同点：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都能够看作是应用贪心算法结构最小生成树的例子。利用了最小生成树性质。不相同点：Prim(普里姆)算法：在这个过程中采纳到的所有边恰巧组成G的一棵最小生成树T，T中包含G的n-1条边，且不形成回路。Kruskal(克鲁斯卡尔)算法：是结构最小生成树的另一个常

17、用算法。该算法不是经过扩大连通子集来进行贪心选择。而是经过选择拥有最小权的边的会合来进行贪心选择。在选择的同时能够进行连通操作以便形成生成树。4.请简述分支限界法的找寻策略。P161课件第6章(1)第6页分支限界法以广度优先或以最小耗资（最大效益）优先的方式找寻问题的解空间树。每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。儿子结点中，致使不能行解或致使非最优解的儿子结点被舍弃，其他儿子结点被加入活结点表中。从活结点表中取下一结点成为目前扩展结点，并重复上述结点扩展过程。这个过程素来连续到找到所需的解或活结点表为空时为止。5.试比较分支限界法与回溯法的

18、异同。P161课件第6章(1)第5页不相同点：求解目标：回溯法的求解目标是找出解空间树中知足拘束条件的所有解，而分支限界法的求解目标则是找出知足拘束条件的一个解，或是在知足拘束条件的解中找出在某种意义下的最优解。找寻方式：回溯法以深度优先的方式找寻解空间树，而分支限界法例以广度优先或以最小耗资优先的方式找寻解空间树。五、算法应用题用动向规划求解凸多边形最优三角剖分问题。三角剖分的结构及其有关问题P61语法树与完好加括号方式一个表达式的完好加括号方式相应于一棵完好二叉树，称为表达式的语法树。比方，完好加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。.优选文档(

19、2)语法树与凸多边形三角剖分凸多边形P=v0,v1,vn-1的三角剖分也能够用语法树表示。如图：根结点是边v0v6(能够任选)。其他边则是语法树的叶子节点。v0v6是三角形v0v3v6的一条边。2、三角剖分与矩阵连乘P61一般来说，凸多边形的三角剖分和有n-1个叶节点的语法树存在一一对应关系。(2)N个矩阵连乘的完好加括号和有n个叶节点的语法树也存在一一对应关系。因此，n个矩阵连乘的完好加括号和有n+1个节点的凸多边形的三角剖分也存在一一对应关系。.优选文档(4)矩阵连乘积中A1A2An中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ibestp.(3

20、).连续向下找寻生成结点F，获取可行解(1,1,1,0,0)，获取价值为86，更新bestp=86(如图第3步).优选文档.优选文档第3步第5步第8步(4).回溯：沿E回溯到左孩子D，生成相应右孩子G，获取部分解(1,1,0,1),此时b=93.1bbestp,能够生成右子树（第4步在第5步的基础上没有H和I的图形）(5).连续生成结点H,I，获取可行解(1,1,0,1,0),价值为88，更新bestp=88(如图第5步)(6).回溯H生成J，获取部分解(1,1,0,0),估计部分解b=9288（第6步在第8步的基础上没有K和L的图形）(7).连续生成结点K，获取可行解(1,1,0,0,1),

21、价值为92，更新bestp=92（第7步在第8步的基础上没有L的图形）(8).K是左孩子，生成其对应的右孩子L，获取可行解(1,1,0,0,0)(如图第8步)(9).回溯,沿结点L向上回溯到结点B,生成结点M,获取部分解(1,0),估计部分解b=9092,回溯（第9步在第10步的基础上没有N的图形）(10).向上连续回溯生成结点N，获取部分解(0)，此时获取的b=74+10*(46/27)=91.0392,回溯，此时已回到根结点，结束。最优解(1,1,0,0,1),价值为92.(如图第10步).优选文档练习n=8,M=110，W=(1,11,21,23,33,43,45,55)P=(11,21,31,33,43,53,55,65)用回溯法求此0-1背包问题的最优解。最优装载问题P119课件第P37-P54页假定n=4，w=8,6,2,3，c1=c2=12.试依照改良后的最优装载算法找出最优装载量及相应的最优装载方案。要求：列出问题的解空间。结构解空间树。依照递归回溯算法求出最优解和最优值。.优选文档六、算法设计题使用贪心算法求解。题型一：开会问题：某企业的会议好多，致使于全企业唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适合删除一些会议，使得节余的会议在时间上互不矛盾，要求删除的会议数最少。解题算法:templatevoidGS(intn,Types,Typef,bo