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

1、一、选择题1一个.java文件中可以有（）个public 类。一个B两个C多个D零2一个算法应该是（）A程序B问题求解步骤的描述C要满足五个基本特性DA和C用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）唯一性B有穷性C有0个或多个输入D有输出生会主席竞选，得票数依次130，20，98，15，67，3。若采用冒泡排序算法对其行排序，则完成第二遍时的结果是（）A3，15，130，20，98，67 C3，15，20，67，130，98B3，15，20，130，98，67 D3，15，20，67，98，130下列关于算法的描述，正确的是（）一个算法的执行步骤可以

2、是无限的B一个完整的算法必须有输出C算法只能用流程图表示D一个完整的算法至少有一个输6JavaApplication 源程序的主类是指包含有（）方法的类。、main 方法B、toString方法C、init 方法、actionPerfromed方7找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） 分治法B减治法C蛮力法D变治法在编写JavaApplication 程序时，若需要使用到标准输入输出语句，必须在程序的开头写上()语句。A、importjava.awt.* ;B、importjava.applet.Applet ;C、importjava.io.* ;D、importja

3、va.awt.Graphics ;c用来记录已输入球员的人数，sum数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。图中空白处理框和处应填入的是（）A sum sum + dB sum sum +c c c+ 1 c c +1C sum sum+ dD sum sum +c d d+ 1 d d +1报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。利用折半查找，查找学号为33号生的过程中，依次被访问到的学号是（）A5，11，33B8，33C11，45，33（short）8/9.2*5的值的类型为AshortB intCdoubleDfloat12x in

4、t 型变量，则执行一下语句段后，x x=10;x+=x-=x-x;A10B2013下列代码的执行结果是public class StringTestpublic static void main(String int a=4,b=6,c=8;String s=”abc”;System.out.println(a+b+s+c); System.out.printin(); D30AababccB464688C46abc8D10abc814 下列程序段执行后t3 的结果intt1= 2,t2= 3,t3; t3=t1t2?t1:t2+t1A2B4C5150 x10 时，y=x，应当使用的语句是Ai

5、f(0 x10)y=x;Bif(0 x|x10)y=x; Cif(0 x&x 1时，F(n) = F(n-1) + F(n-2)F(0) = 0，F(1) = 1请编写Java应用程序，由键盘输入n的值代表要生成斐波那契数列的项数，在屏幕上输出n项斐波那契数列。import java.io.*; public class Fb/*斐波那契数列算法*/int f(int n)int r;if(n = 1)r = n;elser = f(n-1) + f(n-2);return r;public static void main(String args) throws IOException Sy

6、stem.out.println(请输入所求斐波那契数列的项数：); byte buf = new byte20;System.in.read(buf);String t1 = new String(buf);int n = Integer.parseInt(t1.trim(); Fb f1 = new Fb();int b;System.out.println(输出包含 + n + 项的斐波那契数列：); for(int i = 0; i = n; i+)b = f1.f(i);System.out.print(b + );System.out.println();编写基于Java语言的选择

7、排序算法。/*功能：该算法用选择排序对给定的数组排序输入：一个乱序的整数数组a 输出：升序排列的整数数组a */public void selectionSort (inta )int temp,min;for(int i=0;ia.length-1;i+)min = i;for(int j=i+1;j aj)min = j; temp = ai;ai = amin; amin = temp;编写基于Java语言的冒泡排序算法。/*功能：该算法用冒泡排序对给定的数组排序输入：一个乱序的整数数组a 输出：升序排列的整数数组a */public void bubbleSort(int a )int

8、 temp;for(int i=0;ia.length-1;i+)for(int j=0;jaj+1)temp = aj+1; aj+1 = aj; aj = temp;编写基于Java语言的顺序查找算法。/*功能：该算法实现顺序查找功能输入：一个整数数组a k输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1*/public int seqSearch(int a ,int k)int i = 0;while(i a.length ) & ( ai != k ) i = i + 1;if( i a.length)return i;elsereturn -1;

9、编写基于Java语言的折半查找算法。/*功能：该算法实现折半查找功能输入：一个已经按照升序排列好的整数数组a k输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1*/public int binarySearch(int a , int k)int low = 0;int upper = a.length - 1; while(low = upper)int mid = (low+upper) / 2; if(k = amid)return mid;elseif(des amid)upper = mid - 1;return -1;elselow = mid

10、+ 1;编写基于Java语言的字符串匹配算法。/*功能：该算法实现字符串匹配功能输入：一个n个字符的字符串str代表一段文本一个个字符的字符串key否则返回-1*/public int stringMatch(String str,String key)int j;int n = str.length(); int m = key.length();for(int i = 0; i = (n - m); i+)j = 0;while(j m) & (key.charAt(j) = str.charAt(i+j)j = j + 1;System.out.println(i + , + j); i

11、f(j = m)return i;return -1;编写基于Java语言的直接插入排序算法。/*功能：该算法用直接插入排序对给定的数组排序输入：一个乱序的整数数组a 输出：升序排列的整数数组a */public void insertSort (inta )int temp,i,j; for(i=1;i=0 & aj=temp)aj+1=aj; j-;aj+1=temp;算法分析与设计期末复习题一、选择题算法必须具备输入、输出和（ D ）等 4 个特性。A可行性和安全性确定性和易读C有穷性和安全性有穷性和确定性算法分析中，记号O表示（B ），记号表示（ A）n 时的计算时间为 T(n)=3*

12、2n完成概算法的时间为t 秒。现有另一台计算机，其运行速度为第一台的64 倍，那么在这台新机器上用同一算法在tB 解题方法：3*2n*64=3*2xn+8Cn+7设问题规模为 N 时，某递归算法的时间复杂度记为 T(N)，已知 T(1)=1T(N)=2T(N/2)+N/2，用O（ C ）。AO(logN)CO(NlogN)直接或间接调用自身的算法称为（B ） 。A贪心算法递归算C迭代算法回溯法Fibonacci数列中，第4个和第11个数分别是（D ） A5，89C5，144在有8个顶点的凸多边形的三角剖分中，恰有（ B）。A6条弦和7个三角形条弦和6个三角形C6条弦和6个三角形条弦和5个三角形

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

14、索算法是利用（ A）实现的算法。 A分治策略动态规划C贪心法回溯法下列不是动态规划算法基本步骤的是（ B。 P44 A找出最优解的性质构造最优解C算出最优应该是最优)D定义最优下面问题（B）不能使用贪心法解决。 A单源最短路径问题BN皇后问C最小花费生成树问题D背包问题使用二分搜索算法在n下搜索的时间复杂性分别为（A）。P17AO(1)，O(logn)BO(n)，O(logn)CO(1)，O(nlogn)DO(n)，O(nlogn)优先队列式分支限界法选取扩展结点的原则是（ C。A先进先出后进先出C结点的优先级随机下面不是分支界限法搜索方式的是（D ） P161 A广度优先最小耗费优C最大效益

15、优先深度优先分支限界法解最大团问题时，活结点表的组织形式是（ B）A最小堆最大堆C栈数组下列关于计算机算法的描述不正确的是（ C ）。A算法是指解决问题的一种方法或一个过程 B算法是若干指令的有穷序列C. 算法必须要有输入和输出D算法是编程的思想下列关于凸多边形最优三角剖分问题描述不正确的是（ A）。An+1 个矩阵连乘的完全加括号和n 个点的凸多边形的三角剖分对B在有n 个顶点的凸多边形的三角剖分中，恰有n-3 条弦C该问题可以用动态规划法来求解D在有n 个顶点的凸多边形的三角剖分中，恰有n-2 个三角形（ C ）P44 A递归地定义最优值 B分析最优解的性质，并刻画其结构特征 CD以自底向

16、上的方式计算出最优值分治法所能解决的问题应具有的关键特征是（ C）。P16该问题的规模缩小到一定的程度就可以容易地解决 B该问题可以分解为若干个规模较小的相同问题 CD该问题所分解出的各个子问题是相互独立的下列关于回溯法的描述不正确的是（D ）P114 A回溯法也称为试探法 B回溯法有“通用解题法”之称 C回溯法是一种能避免不必要搜索的穷举式搜索D用回溯法对解空间作深度优先搜索时只能用递归方法实现常见的两种分支限界法为（ D）P161广度优先分支限界法与深度优先分支限界法；队列式（FIFO）分支限界法与堆栈式分支限界法；排列树法与子集树法；队列式（FIFO）分支限界法与优先队列式分支限界法；二

17、、填空题1. f(n)=3n2+10的渐近性态f(n)= O( n2)，g(n)=10log3n的渐近性态g(n)= O(n。一个“好”的算法应具有正确性、可读性、健壮性和高效率低存储量需求等特性。算法的时间复杂性函数表示为C=F(N,I,A)，分析算法复杂性的目的在于比求解同意问题的两个不同算法的效率的效率。构成递归式的两个基本要素是 递归的边界条件 和 递归的定义。单源最短路径问题可用 分支限界法 和贪心算法求解。用分治法实现快速排序算法时最好情况下的时间复杂性为 O(nlogn)最坏情况的时间复杂性为O(n2)，该算法所需的时间与 运行时间和划分两方面因素有关P260-1n常见的分支限界

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

19、递归算法。P15其中Hanoi (int n, int a, int c, int b表示将塔座A 上的n 个盘子移至塔座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, move(a,c); hanoi(n-1, b, c, 用分治法求解快速排序问题。快速排序算法P25 、作业、课件第2章（2）42页-50templatevoid QuickSort (Type a, int p, int r)if (pr) int q=Partition

20、(a,p,r); QuickSort (a,p,q-1); QuickSort (a,q+1,r)；Partition 函数的具体实现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;用贪心算法求解最优装载问题。最优装载问题 P954(2)3-8templatevoid Loading(

21、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 Knapprivate: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

22、)if(in)bestp=cp;return;if(cw+wibestp) /Backtrack(i+1);Typep Knap:Bound(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 Object /物品类friend int Knapsack(int *,int *,int,int); public:int operator =a.d);int

23、 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; 0for(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); /依物品单位重量价值非增排序Knap K; K.p=new Typepn

24、+1; K.w=new Typewn+1; for(int K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;delete Q;delete K.w;delete K.p;return K.bestp;例 2：批处理作业调度 课件第 5 章(2)P2-5 问题描述,课本 P125-127算法描述： class Flowshopstaticint m,/ 各作业所需的处理时间 x,/ 当前作业调度 bestx, / 当前最优作业调度 f2,/ 2完成处理时间f1,/ 1 完成处理时间f,/ 完成时间和bestf,/ 当

25、前最优的完成时间和n;/ 作业数static void Backtrack(int i)if (i n) for (int j = 1; 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);计算

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

27、树的例子。利用了最小生成树性质。不同点：Prim(普里姆)算法：在这个过程中选取到的所有边恰好构成G 的一棵最小生成树 中包Gn-1Kruskal通子集来进行贪心选择。而是通过选择具有最小权的边的集合来进行贪心选择。在选择的 同时可以进行连通操作以便形成生成树。P16166(1)分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。(2)每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。结点表中。直持续到找到所需的解或活结点表为空时为止。P161 课件第 6(15不同点：求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，

28、而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。小耗费优先的方式搜索解空间树。五、算法应用题三角剖分的结构及其相关问题P61语法树与完全加括号方式一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。语法树与凸多边形三角剖分凸多边形P=v0,v1,vn-1的三角剖分也可以用语法树表示。如图：根结点是边 v0v 6(可以任选)。其他边则是语法树的叶子节点。 v0v 6 是三角形v0v3v6 的一条边。2、三角剖分与矩阵连乘P61(1)一般来说，凸多边形的三角剖分和有n-1 个叶节点的语法树存在一一对应关系。(2)N 个矩阵连乘的完全加括号和有n 个叶节点的语法树也存在一一对应关系 。n个矩阵连乘的完全加括号和有n+1关系。矩阵连乘积中A1 A2 An 中的每个矩阵Ai (n+1)边形中的一条边vi-1vi剖分中的一条弦vivj，ibestp,可以生成右子树（4 5 步的基础上没有H I 的图形）H,I，得到可行解( 1,1,0,1,0bestp=88(5 步) (6).HJ，得到部分解( 1,1,0,0 ),估计部分解b=9288（6 8 步的基础