《算法分析与设计》期末考试复习题纲(完整版)Word文件下载.doc

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

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

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

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

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

6、限界法和优先队列式分支限界法。9. 回溯法搜索解空间树时常用的两种剪枝函数为 约束函数 和 剪枝函数 。10. 分支限界法解最大团问题时，活结点表的组织形式是 最大堆 ；分支限界法解单源最短路径问题时，活结点表的组织形式是 最小堆 。三、 算法填空题1. 递归求解Hanoi塔问题/阶乘问题。例1 :阶乘函数n! P12阶乘的非递归方式定义：试写出阶乖的递归式及算法。递归式为： 边界条件 递归方程递归算法：int factorial （int n） if （n=0） return 1; 递归出口 return n * factorial （n-1）; 递归调用 例2:用递归技术求解Hanoi塔问

7、题,Hanoi塔的递归算法。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, int

8、r） if （pr） int q=Partition（a,p,r）; QuickSort （a,p,q-1）; QuickSort （a,q+1,r）； Partition函数的具体实现int 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 课件

9、第4章（2）第3-8页void 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 class Knap private: Typep Bound（int i）; /计算上界 void Backtrack（int i）; Typew c; /背包容量 int n; /物品数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前重

10、量 Typep cp; /当前价值 Typep bestp; /当前最优价值;void Knap:Backtrack（int i） if（in） bestp=cp; return; if（cw+wibestp） /进入右子树Typep KnapBound（int i） Typew cleft=c-cw; /剩余的背包容量 Typep b=cp; /b为当前价值 /依次装入单位重量价值高的整个物品 while（i=n&wi=cleft） cleft-=wi; b+=pi; i+; if（i=n） /装入物品的一部分 b+=pi*cleft/wi; return b; /返回上界class Obj

11、ect /物品类 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 Knapsack初始化 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

12、/wi; P+=pi; W+=wi; if（W=c） /能装入所有物品 return P; return P; QuickSort（Q,0,n-1）; /依物品单位重量价值非增排序 Knap n） for （int j = 1; j+） bestxj = xj; bestf = f; else for （int j = i; j+） f1+=mxj1;/第j个作业在第一台机器上所需时间 f2i=（f2i-1f1）?f2i-1:f1）+mxj2; f+=f2i; if （f bestf） /约束函数 Swap（xi, xj）; Backtrack（i+1）; Swap（xi, xj）; f1 -

13、 =mxj1; f - =f2i; 例3：最大团问题，要会画解空间树。class Clique friend int MaxClique（int *,int ,int）; void Print（）; /输出最优解 private: int *a; /图G的邻接矩阵，下标从1开始 /图G的顶点数 int *x; /当前解 int *bestx; /当前最优解 int cn; /当前团的顶点数 int bestn; /当前最大团的顶点数void Clique:n） for（int j=1;jbestn） /如有可能在右子树中找到更大的团，则进入右子树 xi=0; Backtrack（i+1）; 计

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

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

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