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

《《算法分析与设计》期末考试复习题纲》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末考试复习题纲（22页珍藏版）》请在装配图网上搜索。

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

2、时，某递归算法的时间复杂度记为T（N），已知T（l）=l,T（N）=2T（N/2）+N/2,用0表示的时间复杂度为（C）。A. 0（logN）B.0（N）C.O（NlogN）D.0（N2logN）直接或间接调用自身的算法称为（B）。A. 贪心算法B.递归算法C.迭代算法D.回溯法Fibonacci数列中，第4个和第11个数分别是（D）。A.5，89B.3，89C.5，144D.3，144在有8个顶点的凸多边形的三角剖分中，恰有（B）。A.6条弦和7个三角形B.5条弦和6个三角形C.6条弦和6个三角形D.5条弦和5个三角形一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）A.重叠子问

3、题B.最优子结构性质C.贪心选择性质D.定义最优解下列哪个问题不用贪心法求解（C）。A.哈夫曼编码问题B.单源最短路径问题C.最大团问题D.最小生成树问题下列算法中通常以自底向上的方式求解最优解的是（B）。A.备忘录法B.动态规划法C.贪心法D.回溯法下列算法中不能解决0/1背包问题的是（A）。A.贪心法B.动态规划C.回溯法D.分支限界法下列哪个问题可以用贪心算法求解（D）。13.14.15.16.17.18.19.20.21.22.23.24.A.LCS问题B.批处理作业问题C.0-1背包问题D.哈夫曼编码问题用回溯法求解最优装载问题时，若待选物品为m种，贝y该问题的解空间树的结点个数为（

4、）。A.m!B.2m+1C.2m+1-1D.2m二分搜索算法是利用（A）实现的算法。A.分治策略B.动态规划法C.贪心法D.回溯法下列不是动态规划算法基本步骤的是（B）。P44A找出最优解的性质B构造最优解C.算出最优解（应该是最优值）D.定义最优解下面问题（B）不能使用贪心法解决。A.单源最短路径问题B.N皇后问题C.最小花费生成树问题D.背包问题使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为（A）oP17A.O（1），O（logn）B.O（n），O（logn）C.O（1），O（nlogn）D.O（n），O（nlogn）优先队列式分支限界法选

5、取扩展结点的原则是（C）P162A.先进先出B.后进先出C.结点的优先级D.随机下面不是分支界限法搜索方式的是（D）。P161A.广度优先B.最小耗费优先C.最大效益优先D.深度优先分支限界法解最大团问题时，活结点表的组织形式是（B）。A.最小堆B.最大堆C.栈D.数组下列关于计算机算法的描述不正确的是（C）。P1A. 算法是指解决问题的一种方法或一个过程B. 算法是若干指令的有穷序列C. 算法必须要有输入和输出D. 算法是编程的思想下列关于凸多边形最优三角剖分问题描述不正确的是（A）。A. n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖分对应B. 在有n个顶点的凸多边形的三角剖分中，

6、恰有n-3条弦C. 该问题可以用动态规划法来求解D. 在有n个顶点的凸多边形的三角剖分中，恰有n-2个三角形动态规划法求解问题的基本步骤不包括（C）oP44A. 递归地定义最优值B. 分析最优解的性质，并刻画其结构特征C. 根据计算最优值时得到的信息，构造最优解（可以省去的）D. 以自底向上的方式计算出最优值分治法所能解决的问题应具有的关键特征是（C）oP16A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个规模较小的相同问题C.利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的25. 下列关于回溯法的描述不正确的是(D)。

7、P114A. 回溯法也称为试探法B. 回溯法有“通用解题法”之称C. 回溯法是一种能避免不必要搜索的穷举式搜索法D. 用回溯法对解空间作深度优先搜索时只能用递归方法实现26. 常见的两种分支限界法为(D)。P161A. 广度优先分支限界法与深度优先分支限界法；B. 队列式(FIFO)分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式(FIFO)分支限界法与优先队列式分支限界法；二、填空题1. f(n)=3n2+l0的渐近性态f(n)二0(少),g(n)=10log3n的渐近性态g(n)=0(n)。2. 一个“好”的算法应具有正确性、可读性、健壮性和高效率和低存储量需求等特性。

8、3. 算法的时间复杂性函数表示为C=F(N,I,A)，分析算法复杂性的目的在于比较一求解同意问题的两个不同算法的效率的效率。4. 构成递归式的两个基本要素是递归的边界条件和递归的定义。5. 单源最短路径问题可用分支限界法和贪心算法求解。6. 用分治法实现快速排序算法时，最好情况下的时间复杂性为O(nlogn),最坏情况下的时间复杂性为，该算法所需的时间与运行时间和划分两方面因素有关。P267. 0-1背包问题的解空间树为完全二叉树;n后问题的解空间树为排列树;8. 常见的分支限界法有队列式(FIFO)分支限界法和优先队列式分支限界法。9. 回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝

9、函数。10. 分支限界法解最大团问题时，活结点表的组织形式是最大堆：分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆。三、算法填空题1. 递归求解Hanoi塔问题/阶乘问题。例1:阶乘函数n!P12阶乘的非递归方式定义：n!=n(n-1)x(n-2)xx2x1试写出阶乖的递归式及算法。递归式为：1n，0边界条件n!，n(n-1)!n0递归方程递归算法：intfactorial(intn)if(n=0)return1;递归出口returnn*factorial(n-1);递归调用例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15其中Hanoi(intn,inta,in

10、tc,intb)表示将塔座A上的n个盘子移至塔座C,以塔座B为辅助。Move(a,c)表示将塔座a上编号为n的圆盘移至塔座c上。nni:i111r1n111enniI；i】iii.i-voidhanoi(intn,inta,intc,intb)if(n0)hanoi(n-1,a,b,c);move(a,c);hanoi(n-1,b,c,a);2. 用分治法求解快速排序问题。快速排序算法P25、作业、课件第2章(2)42页-50页templateclassTypevoidQuickSort(Typea,intp,intr)if(pr)intq=Partition(a,p,r);QuickSort

11、(a,p,q-l);QuickSort(a,q+l,r)；Partition函数的具体实现templateintPartition(Typea,intp,intr)inti=p,j=r+1;Typex=ap;/将x的元素交换到左边区域/将X的元素交换到右边区域while(true)while(a+ix&ir);while(a-jx);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;returnj;3. 用贪心算法求解最优装载问题。最优装载问题P95课件第4章(2)第3-8页templateclassTypevoidLoading(intx,Typew,Typec,int

12、n)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;4. 用回溯法求解0-1背包/批处理作业调度/最大团问题，要会画解空间树。例1：用回溯法求解0-1背包P133课件第5章(2)第24-38页templateclassKnapprivate:TypepBound(inti);/计算上界voidBacktrack(inti);Typewc;/背包容量intn;/物品数Typew*w;/物品重量数组Typep*p;/物品价值数组Typewcw;/当前重量Typepcp;/

13、当前价值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=cleft)cleft-=wi;b+=pi;i+;if(i=n)/装入物品的一部分b+=pi*cleft/wi;returnb;/返回上界classObject/物品类friendintKnapsack(in

14、t*,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;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;Qui

15、ckSort(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二xj;bestn二cn;return;/判断第i个顶点是否与已选顶点都有边相连intOK=1;for(intj=1;jbtn)(麻何；BcktracKflir计算时间：0(n2Qifxj&Sai50)(OK0;brea

16、k;卜四、简答题1. 请简述使用动态规划算法解题的基本步骤。P44动态规划的设计分为以下4个步骤：找出最优解的性质，并刻划其结构特征。(2) 递归地定义最优值。(3) 以自底向上的方式计算出最优值。(4) 根据计算最优值时得到的信息，构造最优解。2. 简述动态规划方法与分治法的异同。P44相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。不同点：分治法的子问题互相独立且与原问题相同。与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子子问题。3. 试比较Prim算法与Kr

17、uskal算法的异同。105-P107相同点：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最小生成树的例子。利用了最小生成树性质。不同点：Prim(普里姆)算法：在这个过程中选取到的所有边恰好构成G的一棵最小生成树T,T中包含G的n-1条边，且不形成回路。Kruskal(克鲁斯卡尔)算法：是构造最小生成树的另一个常用算法。该算法不是通过扩充连通子集来进行贪心选择。而是通过选择具有最小权的边的集合来进行贪心选择。在选择的同时可以进行连通操作以便形成生成树。4. 请简述分支限界法的搜索策略。P161课件第6章(1)第6页(1) 分支限界法以广度优先或以最小耗

18、费(最大效益)优先的方式搜索问题的解空间树。(2) 每一个活结点只有一次机会成为扩展结点。(3) 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。(4) 儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。(5) 从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。5. 试比较分支限界法与回溯法的异同P161课件第6章(1)第5页不同点：(1) 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种

19、意义下的最优解。(2) 搜索方式：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。五、算法应用题1. 用动态规划求解凸多边形最优三角剖分问题。三角剖分的结构及其相关问题P61(1)语法树与完全加括号方式一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。(2)语法树与凸多边形三角剖分凸多边形P=vO,v1,vn-1的三角剖分也可以用语法树表示。如图：根结点是边vOv6(可以任选)。其他边则是语法树的叶子节点。vOv6是三角形v0v3v6的

20、一条边。2、三角剖分与矩阵连乘P61(1) 一般来说，凸多边形的三角剖分和有n-1个叶节点的语法树存在一一对应关系。(2) N个矩阵连乘的完全加括号和有n个叶节点的语法树也存在对应关系。(3) 所以，n个矩阵连乘的完全加括号和有n+1个节点的凸多边形的三角剖分也存在对应关系。(4) 矩阵连乘积中A1A2-An中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj,ivj,对应于矩阵连乘积Ai+1:j。(5) 矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的特殊情况。课后习题(第3章小结*)对于如下矩阵链P=10,100,5,50,30,20,60,45

21、,50,请按照构造其最优完全加括号方式，并列出相应的语法树和最优三角剖分图。2. 用贪心算法求解活动安排问题/最小生成树问题/哈夫曼编码问题。贪心算法求解活动安排问题例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:最小生成树问题P103-P105哈夫曼编码问题，前缀码二叉树表示法例子：图a:与固定长度编码对应的树（叶子高度一致）图b:与可变长度编码对应的树（叶子高度不一致）3. 用回溯法求解0-1背包问题/最优装载问题。用回溯法求0-1背包问题。P133,实例:n=5,M=50N12345W155252730P3012444650P/W22.41.761.701.67(

22、1).令bestp=0,将物体的序号按价值体积比排序结果是(2,1,3,4,5)N21345W515252730P1230444650P/W2.421.761.701.67(2) .根据排序得到部分解(1,1,1,0)，估计当前部分解的价值b,86+(50-45)*1.67=94.3,bbestp.(3) .继续向下搜索生成结点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的

23、图形)(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)，价值为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的图形)(

24、10) .向上继续回溯生成结点N,得到部分解(0),此时得到的b=74+10*(46/27)=91.0392,步)回溯，此时已回到根结点，结束。最优解(1,1,0,0,1)，价值为92.(如图第10n=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.试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。要求：a) 列出问题的解空间。b) 构造解空间树。c) 根据递归回溯算法求出最优解

25、和最优值。六、算法设计题使用贪心算法求解。题型一：开会问题：某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。解题算法:templatevoidGS(intn,Types,Typef,boolA)A1=false;intj=1;intsum=0;for(inti=2;i=fj)Ai=false;j=i;elseAi=true;sum+;题型二：试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n比较小的例子，看能否从中找出

26、规律：n分解方案最大的乘积5236624873412835159234241023530算法分析：猜想一下是不是将n拆成尽量多的数乘积最大？（拆出的数中最小为2）。为了使因数个数尽可能多，我们用n减2、3i,直到ni。若此时n和i相等，则先将i+1,同时n-1。若此时n0,则均匀地分给前面各项。因此我们可以得到一个贪心策略，即将n不停地拆分开来，使得所有的数都不同且不能再拆。解题算法：21k+;ak=akl+l;n-=ak;；if(n=ak)ak+;n;for(inti二0;in;i+)aki+;题型三：田忌赛马：如果3匹马变成n匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子。已知国王和田忌的所有马的奔跑速度，并且所有马奔跑的速度均不相同，现已经对两人的马分别从快到慢排好序，请设计一个算法，帮助田忌赢得最多的银子。解题思路：先对两组马按速度排序。如果田忌(A)最快的马比齐王(B)最快的马快,直接赢；如果A最快的马比B慢,用A最慢的马拼B最快的马；如果A最慢的马比B最慢的马快，直接拼掉；如果A最慢的马比B最慢的马慢，用A最慢的马拼B最快的马；如果A和B最快和最慢的马都速度相同，用A最慢的马拼B最快的马算法分析：22