《算法分析与设计》期末考试复习题纲(完整版)

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

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

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

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

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

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

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

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

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

9、函数为约束函数和 剪枝函数 。10.分支限界法解最大团问题时，活结点表的组织形式是最大堆；分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆 。三、算法填空题1. 递归求解 Hanoi 塔问题 / 阶乘问题。例 1 :阶乘函数 n! P12阶乘的非递归方式定义： n!n( n1)( n 2)2 1试写出阶乖的递归式及算法。递归式为：1n0边界条件n!n(n1)! n03递归方程递归算法：int factorial (int n) if (n=0) return 1;递归出口return n * factorial (n-1);递归调用例 2:用递归技术求解Hanoi 塔问题 ,Hano

10、i 塔的递归算法。P15其中 Hanoi (int n, int a, int c, int b) 表示将塔座A 上的 n 个盘子移至塔座C，以塔座 B 为辅助。Move(a,c) 表示将塔座a 上编号为 n 的圆盘移至塔座c 上。void hanoi (int n, int a, int c, int b)if (n 0)hanoi(n-1, a, b, c);move(a,c);hanoi(n-1, b, c, a);2. 用分治法求解快速排序问题。快速排序算法P25、作业、课件第2 章（ 2） 42 页 -50 页templatevoid QuickSort (Type a, int p

11、, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1);QuickSort (a,q+1,r)；4Partition函数的具体实现templateint Partition (Type a, int p, int r)int i = p, j = r + 1;Type x=ap;/ 将 x 的元素交换到右边区域while (true) while (a+i x & ix);if (i = j) break;Swap(ai, aj);ap = aj;aj = x;return j;3. 用贪心算法求解最优装载问题。最优装载问题 P95

12、 课件第 4 章 (2) 第 3-8 页templatevoid Loading(int x, Type w, Type c, int n)int *t = new int n+1;Sort(w, t, n);for (int i = 1; i = n; i+) xi = 0;for (int j = 1; j = n & wtj = c; j+)xti = 1; c -= wtj;54. 用回溯法求解 0-1 背包 / 批处理作业调度 / 最大团问题，要会画解空间树。例 1：用回溯法求解0-1 背包P133 课件第 5 章 (2) 第 24-38 页templateclass Knappri

13、vate:Typep Bound(int i); /计算上界void Backtrack(int i);Typew c; /背包容量int n; /物品数Typew *w; /物品重量数组Typep *p; /物品价值数组Typew cw; /当前重量Typep cp; /当前价值Typep bestp; /当前最优价值;void Knap:Backtrack(int i) if(in) bestp=cp; return; if(cw+wibestp) /进入右子树Backtrack(i+1);Typep Knap:Bound(int i)Typew cleft=c-cw; /剩余的背包容量T

14、ypep b=cp; /b为当前价值/ 依次装入单位重量价值高的整个物品6while(i=n&wi=cleft) cleft-=wi;b+=pi;i+;if(i=n) /装入物品的一部分b+=pi*cleft/wi;return b; /返回上界class Object /物品类friend int Knapsack(int *,int *,int,int);public:int operator =a.d);int ID; /物品编号float d; /单位重量价值;Typep Knapsack( Typep p,Typew w,Typew c,int n) /为 Typep Knapsac

15、k 初始化Typew W=0; /总重量Typep P=0; /总价值Object* Q=new Objectn; /创建物品数组，下标从0 开始for(int i=1;i=n;i+) /初始物品数组数据 Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c) /能装入所有物品return P;if(W=c) /能装入所有物品return P;QuickSort(Q,0,n-1); /依物品单位重量价值非增排序7Knap K;K.p=new Typepn+1;K.w=new Typewn+1;for(int i=1;i n) for (int j = 1;

16、 j = n; j+)bestxj = xj;bestf = f;elsefor (int j = i; j f1)?f2i-1:f1)+mxj2;f+=f2i;if (f n) for(int j=1;j=n;j+) bestxj=xj; bestn=cn; return; / 判断第 i 个顶点是否与已选顶点都有边相连int OK=1;for(int j=1;jbestn) /如有可能在右子树中找到更大的团，则进入右子树xi=0;Backtrack(i+1);计算时间： O(n2n )四、简答题1.请简述使用动态规划算法解题的基本步骤。P44动态规划的设计分为以下4 个步骤：(1)找出最优

17、解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。2.简述动态规划方法与分治法的异同。P44相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。不同点：分治法的子问题互相独立且与原问题相同。与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子子问题。3.试比较 Prim 算法与 Kruskal算法的异同。 105-P10710相同点：Prim( 普里姆 ) 算法和 Kruskal( 克鲁斯卡

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

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

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

21、三角剖分与矩 乘P61(1) 一般来 ，凸多 形的三角剖分和有n-1 个叶 点的 法 存在一一 关系。(2)N 个矩 乘的完全加括号和有n 个叶 点的 法 也存在一一 关系。(3) 所以，n 个矩 乘的完全加括号和有 n+1 个 点的凸多 形的三角剖分也存在一一 关系。12(4) 矩 乘 中 A1 A2 An 中的每个矩 Ai 于凸 (n+1) 形中的一条 vi-1vi 。三角剖分中的一条弦 vivj ， ibestp.(3).继续向下搜索生成结点F，得到可行解 (1,1,1,0,0) ，得到价值为86，更新 bestp=86 (如图第 3 步 )1617第 3 步第 5 步第 8 步(4).

22、 回溯：沿 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 ),价值为 92，更新 bestp=92 （第 7 步在第 8 步的基础上

23、没有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步 )18练习n=8, M=110 ，W=( 1, 11,21,23,33,43,45,55 )P=(1

24、1,21,31,33,43,53,55,65 )用回溯法求此0-1 背包问题的最优解。最优装载问题P119课件第 P37-P54 页假定 n= 4 ， w= 8 , 6 , 2 , 3 ， c1 = c 2 =12.试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。要求：a) 列出问题的解空间。b) 构造解空间树。c) 根据递归回溯算法求出最优解和最优值。19六、算法设计题使用贪心算法求解。题型一：开会问题：某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。解题算法 :tem

25、platevoid GS (int n, Type s, Type f, bool A)A1=false;int j=1;int sum=0;for (int i=2;i=fj) Ai=false; j=i; else Ai=true; sum+;题型二：试用贪心算法求解下列问题：将正整数n 分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n 比较小的例子，看能否从中找出规律：20算法分析：猜想一下是不是将 n 拆成尽量多的数乘 最大？（拆出的数中最小 2）。 了使因数个数尽可能多，我 用n 减 2、 3 i ，直到 n0， 均匀地分 前面各 。因此我 可以得到

26、一个 心策略，即将n 不停地拆分开来，使得所有的数都不同且不能再拆。解 算法 :21题型三：田忌赛马： 如果 3 匹马变成n 匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200 两银子，输一局，田忌就要输掉200两银子。 已知国王和田忌的所有马的奔跑速度，并且所有马奔跑的速度均不相同，现已经对两人的马分别从快到慢排好序，请设计一个算法，帮助田忌赢得最多的银子。解题思路：先对两组马按速度排序。如果田忌 (A) 最快的马比齐王(B) 最快的马快 , 直接赢 ;如果 A 最快的马比B 慢 , 用 A 最慢的马拼B 最快的马 ;如果 A 最慢的马比B 最慢的马快 , 直接拼掉 ;如果 A 最慢的马比B 最慢的马慢 , 用 A 最慢的马拼B 最快的马 ;如果 A 和 B 最快和最慢的马都速度相同, 用 A 最慢的马拼B最快的马算法分析 :22