2008.1算法设计与分析课程期末试卷.doc

1、精品文档就在这里-各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有-华南农业大学期末考试试卷（A卷）2007学年第一学期 考试科目：算法分析与设计考试类型：（开卷）考试时间：120分钟学号 姓名 年级专业 题号一二三总分得分评阅人一、选择题（20分，每题2分）1、void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 上述算法的时间复杂度为 A。AO（2n）BO（nlog n）C（n！）D（nn）2、当一个确定性算法在最坏情况下

2、的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 B 来消除或减少问题的好坏实例间的这种差别。（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法3、对于下列二分搜索算法，正确的是 D 。（A）public static int binarySearch(int a, int x, int n) int left = 0, right = n-1;while(left amiddle) left = middle;else right = middle; /whilereturn 1;（B）public static int binarySearch(int

3、a, int x, int n)int left = 0, right = n-1;while(left+1 != right)int middle = (left + right) / 2;if(x = amiddle) left = middle;else right = middle;/whileif(x = aleft) return left;else return 1;（C）public static int binarySearch (int a, int x, int n)int left = 0, right = n-1;while(left right-1)int midd

4、le = (left + right) / 2;if(x 0 & x = a0)int left = 0, right = n-1;while(left right)int middle = (left + right + 1) / 2;if(x m）。对于多级调度问题，使用以下哪种贪心策略比较合适 B 。（A） 作业从小到大依次分配给空闲的机器（B） 作业从大到小依次分配给空闲的机器（C） 每个机器分配一样的作业数（D） 使用以上几种贪心策略都能找到最优解，所以都合适7、使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为 。（A）10（B）11（

5、C）500（D）10008、设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为 B 。（A）1 （n=1 | m=1）q(n, n) （n m 1）（B） 1 （n=1 | m=1）q(n, n) （n m 1）（C） 1 （n=1 | m=1）q(n, n) （n m 1）(D) 0 （n 1 & m = 1）1 （n=1）q（n，m）=q(n, n) （n m 1）9、一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N-2个三角形，这称为凸N边形的一种三角剖分。例如N5时，共有以下5种三角剖分：当N8时，总共有 B 种三角剖分。多边形三

6、角剖分公式 D(n+1)Dn =(4n-6)n (Dn表示凸n边形的三角剖分数）D8=(D8D7)*(D7D6)*(D6D5)=(227)*(3)*(145)=132（A）8（B）132（C）14（D）14010、给定6个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。这家医院应建在小区 C ，才能使距离医院最远的小区到医院的路程最短？ABCDEF6132216103（A）A （B）B （C）C （D）E二、简答题（30分，每题6分）1、 试比较回溯法与分支限界算法，分别谈谈这两个算法比

7、较适合的问题？不同点：求解目标，搜索方式，空间消耗。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。分支限界法适合解决大量离散最优化的问题。2、 给定n件物品和一个背包，物品i的重量是wi，体积是vi（wi，vi均为整数），价值是pi；背包的容量为C，容积为D。一件物品只能整个放进背包中或不放进背包中，也

8、不允许重复放入。0-1背包问题问应如何选择装入背包的物品，使得装入背包中的物品不超过背包容量容积限制，并且物品的总价值最大？设m(i，j，k)是背包容量为j，容积为k，可选择物品为1，2，i时0-1背包问题的最优值，请给出计算m(i，j，k)的递归关系式。Wixi=cVixi=dMax (pixi求和)3、 如下图，图中的5个顶点为某乡的5个村，图的边代表公路，现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线，才能使所用的电线最少？请列出一种使用电线最少的架线方案（要求给出求解过程）。A5-b9-c,b7-d,a5-e ,a4-e.Total:304、 请解释什么是P问题，NP问题以及

9、NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题。下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。 接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。“NP问题”，实际上是在探讨NP问题与P类问题的关系。 很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一

10、个问题的解既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。N

11、PC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。 NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。既然所有的NP问题都能约化成NPC问

12、题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信PNP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。5、 有4个矩阵A1，A2，A3，A4，其中Ai与Ai1是可乘的，i = 1，2，3，连乘积为A1A2A3A4。 在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个，并请把所有的子问题列出来。5个（A1(A2(A3A4)）(A1(A2A3)A4)(A1A2)(A3A4)(A1(

13、A2A3)A4)(A1A2)A3)A4)三、算法设计题（50分，每题10分）1、【查找第k最小元】给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。我们把这种算法叫做快速选择(quickselect)。令|Si|为Si中元素的个数，快速选择的步骤如下：1)如果|S|=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且|S|CUTOFF，则将S排序并返回第k个最小元。2)选取一个枢纽元vS。3）将集合S-v分割成S1和S2，就像快速排序中所做的那样。4）如果k|S1|，那么第

14、K个最小元必然在S1中。在这种情况下，返回quickselect(S1,k).如果k=1+|S1|，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第(k-|S1|-1)个最小元。我们进行一次递归调用并返回quickselect(S2,k-|S1|-1). 与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O(N2)。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O(N)。具体分析类似快速排序的分析。 快速排序的实现甚至比

15、抽象描述还要简单，其程序如下。当算法终止时，第k个最小元就在位置k-1上(因为数组开始于下标0)。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。2、【最长单调上升子序列】给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。下面我们来考虑状态转移：假设当前已求出m1.i-1，当前保留的状态集合为S，下面计算mi。1、若存在状态kS，使得xk=xi，则状态mi必定不需保留，不必计算。因为，不妨设mi=mj+1，则xjxi=xk，jS，jk，所以mjmk，则mi=m

16、j+1mk，所以状态mi不需保留。2、否则，mi=1+maxmj|xjxi,jS。我们注意到满足条件的j也满足xj=maxxk|xkxi,kS。同时我们把状态i加入到S中。3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态kS，使得mi=mk，则我们有xixi,jS。于是状态k应从S中删去。从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O(n*logn)。（每个状态转移的状态数仅为O(1)，而每次状态转移的时间变为O(logn)）。3、【旅行规划】G 先生想独自驾驶

17、汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。请设计一个算法使到G先生旅行的费用最省（这里的旅行费用指的是加油的总花费）。解：第一步：判断旅行家能否到达目的地 假设在任一个加油站都加满油，能否到达终点 第二步：预算最少费用 采用贪心算法的思想求解 汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。 如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，总费用

18、为 P p(i) * x(i) i=0,1,.,n 两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即x(i) i=0,1,.,n ）自然也是固定不变的。 根据使费用最少的求解目标，要使费用函数取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加油。 汽车每到达一个油站i（包括出发点第0站，但不包括目的地第n+1站），都要检查是否需要加油。 如果汽车在某个油站i需要加油，那么，就先将该油站的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)=p(i+1)，加油时，只需保证油箱中的汽油能够到达下一油站（第i+1站）即可

19、； 否则，继续将p(i)与第i+2站的汽油价格p(i+2)进行比较， 判断是否需要在第i站加油的条件可以确定为：在到达第i站时，汽车油箱中的剩余汽油（用变量rest表示剩余汽油的多少）是否足够行驶到下一更便宜的油站j，即rest*e是否大于或等于d(j)-d(i)。 如果一直找不到比第i个油站更便宜的油站j，则在第i个油站加满油（如果不用加满就已经到了终点，则加油量应该满足刚好到达终点）4、【符号三角形问题】下图是由14个“+”和14个“”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“”。在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同

20、的符号三角形，使其所含的“+”和“”的个数相同。请针对符号三角形问题设计一个尽可能高效的算法。回溯法实现，注意剪枝！具体如下：对于符号三角形问题，用n元组x1：n表示符号三角形的第一行的n个符号。当x=1时，表示符号三角形的第一行的第i个符号为“+”号； 当x=0时，表示符号三角形的第一行的第i个符号为“-”号；1 i n。由于x是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x1：i 确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了xi+1的值后，只要在前面已确定的符号三角形的右边加一条边，就 可以扩

21、展为x1：i+1所相应的符号三角形。最终由x1：n所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此 在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。对于给定 的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。5、【放苹果】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不

22、放，问共有多少种不同的分法（用K表示）？请设计一个算法计算K值（只需要计算K值，不用把具体的分法输出）。注意：5，1，1和1，5，1 是同一种分法。例：M = 7 N = 3则有K = 8可能的分法为：7，0，0 6，1，0 5，2，0 4，3，0 5，1，1 4，2，1 3，3，1 3，2，2设f(m,n) 为m个苹果,n个盘子的放法数目，则先对n作讨论，如果nm,必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if(nm) f(m,n) = f(m,m)当n=m时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f(m,n) = f(m,n-1);后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).而总的放苹果的放法数目等于两者的和，即f(m,n) =f(m,n-1)+f(m-n,n)。边界条件为m=0或n=1时，只有一种放法。-精品 文档-