搜索
1华南农业大学期末考试试卷（A卷）2007学年第一学期考试科目：算法分析与设计考试类型：（开卷）考试时间：120分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（20分，每题2分）1、voidhanoi(intn,inta,intb,intc){if(n0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的时间复杂度为A。A．O（2n）B．O（nlogn）C．Θ（n！）D．Θ（nn）2、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用B来消除或减少问题的好坏实例间的这种差别。（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法3、对于下列二分搜索算法，正确的是D。（A）publicstaticintbinarySearch(int[]a,intx,intn)2{intleft=0,right=n-1;while(left=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle;elseright=middle;}//whilereturn–1;}（B）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x=a[middle])left=middle;elseright=middle;}//whileif(x==a[left])returnleft;elsereturn–1;}（C）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(leftright-1){intmiddle=(left+right)/2;if(xa[middle])right=middle;elseleft=middle;}//whileif(x==a[left])returnleft;elsereturn–1;}3（D）publicstaticintbinarySearch(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0,right=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle-1;elseleft=middle;}//whileif(x==a[left])returnleft;}//ifreturn–1;}4、当输入规模为n时，算法增长率最快的是C。（A）12n（B）100log2n（C）2n2（D）3nlog3n5、关于0－1背包问题以下描述正确的是。（A）可以使用贪心算法找到最优解（B）能找到多项式时间的有效算法（C）使用教材介绍的动态规划方法可求解任意0－1背包问题（D）对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题6、有n个独立的作业{1,2,..,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（nm）。对于多级调度问题，使用以下哪种贪心策略比较合适B。（A）作业从小到大依次分配给空闲的机器（B）作业从大到小依次分配给空闲的机器（C）每个机器分配一样的作业数（D）使用以上几种贪心策略都能找到最优解，所以都合适47、使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为。（A）10（B）11（C）500（D）10008、设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为B。（A）1（n=1||m=1）q(n,n)（nm）q（n，m）=1+q(n,n-1)（n=m）q(n,m-2)+q(n-m,m)（nm1）（B）1（n=1||m=1）q(n,n)（nm）q（n，m）=1+q(n,n-1)（n=m）q(n,m-1)+q(n-m,m)（nm1）（C）1（n=1||m=1）q(n,n)（nm）q（n，m）=1+q(n,n-1)（n=m）q(n,m-1)+q(n-m,m-1)（nm1）(D)0（n1&&m=1）1（n=1）q（n，m）=q(n,n)（nm）1+q(n,n-1)（n=m）q(n,m-1)+q(n-m,m-1)（nm1）9、一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N-2个三角形，这称为凸N边形的一种三角剖分。例如N＝5时，共有以下5种三角剖分：5(1)(2)(3)(4)(5)当N＝8时，总共有B种三角剖分。多边形三角剖分公式D(n+1)\Dn=(4n-6)\n(Dn表示凸n边形的三角剖分数）D8=(D8\D7)*(D7\D6)*(D6\D5)=(22\7)*(3)*(14\5)=132（A）8（B）132（C）14（D）14010、给定6个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。这家医院应建在小区C，才能使距离医院最远的小区到医院的路程最短？（A）A（B）B（C）C（D）EABCDEF61322161036二、简答题（30分，每题6分）1、试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？不同点：求解目标，搜索方式，空间消耗。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。分支限界法适合解决大量离散最优化的问题。2、给定n件物品和一个背包，物品i的重量是wi，体积是vi（wi，vi均为整数），价值是pi；背包的容量为C，容积为D。一件物品只能整个放进背包中或不放进背包中，也不允许重复放入。0-1背包问题问应如何选择装入背包的物品，使得装入背包中的物品不超过背包容量容积限制，并且物品的总价值最大？设m(i，j，k)是背包容量为j，容积为k，可选择物品为1，2，…，i时0-1背包问题的最优值，请给出计算m(i，j，k)的递归关系式。Wixi=cVixi=dMax(pixi求和)3、如下图，图中的5个顶点为某乡的5个村，图的边代表公路，现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线，才能使所用的电线最少？请列出一种使用电线最少的架线方案（要求给出求解过程）。7A5-b9-c,b7-d,a5-e,a4-e.Total:304、请解释什么是P问题，NP问题以及NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题。下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。——“NP问题”，实际上是在探讨NP问题与P类问题的关系。很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。NPC8问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。5、有4个矩阵{A1，A2，A3，A4}，其中Ai与Ai＋1是可乘的，i=1，2，3，连乘积为A1A2A3A4。在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个，并请把所有的子问题列出来。5个（A1(A2(A3A4))）(A1((A2A3)A4))((A1A2)(A3A4))((A1(A2A3))A4)(((A1A2)A3)A4)三、算法设计题（50分，每题10分）1、【查找第k最小元】给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进9行分析说明。我们把这种算法叫做快速选择(quickselect)。令|Si|为Si中元素的个数，快速选择的步骤如下：1)如果|S|=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且|S|≤CUTOFF，则将S排序并返回第k个最小元。2)选取一个枢纽元v∈S。3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。4）如果k≤|S1|，那么第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)。具体分析类似快速排序的分析。快速排序的实现甚至比抽象描述还要简单，其程序如下。当算法终止时，第k个最小元就在位置k-1上(因为数组开始于下标0)。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。2、【最长单调上升子序列】给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂