(已公布!)算法设计与分析-期末试卷-A卷(完整含答案)2010.12

1装订线华南农业大学期末考试试卷（A卷）2010学年第一学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1、以下有关NP完全性理论的相关描述，正确的是（）。（A）P问题都是NP问题（B）NP问题指的是不能够在多项式时间内求解的问题（C）P=NP（D）0-1背包问题属于P问题2、voidhanoi(intn,inta,intb,intc){if(n0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的时间复杂度为（）。（A）O（2n）（B）O（nlogn）（C）Θ（n！）（D）Θ（nn）3、在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。（A）回溯法得分2装订线（B）分支限界法（C）回溯法和分支限界法（D）回溯法求解子集树问题4、下列算法中通常以自底向上的方式求解最优解的是（）。（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法5、蒙特卡罗算法是（）的一种。（A）概率算法（B）分支界限算法（C）贪心算法（D）回溯算法6、有n个独立的作业{1,2,..,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（nm）。对于多级调度问题，使用以下哪种贪心策略比较合适（）。（A）作业从小到大依次分配给空闲的机器（B）作业从大到小依次分配给空闲的机器（C）每个机器分配一样的作业数（D）使用以上几种贪心策略都能找到最优解，所以都合适7、考虑背包问题：n=6，物品重量W=(1,5,2,3,6,1），价值P=(15,59,21,30,60,5)，背包载重量C＝10。能放进背包的物品价值最大为（）。（A）101（B）110（C）115（D）1208、分派问题一般陈述如下：给n个人分派n件工作，把工作j分派给第i个人的成本为cost（i，j），1≤i，j≤n，要求在给每个人分派一件工作的情况下使得总成本最小。此问题的解可表示成n元组（X1，⋯，Xn），其中Xi是给第i个人分配的工作号，且Xi≠Xj（i≠j）。此解空间的状态空间树被称为（）。（A）排列树（B）子集树3装订线（C）宽度优先生成树（D）深度优先生成树9、当输入规模为n时，算法增长率最快的是（）。（A）n!（B）10log2n（C）2n（D）3n510、有9个村庄，其坐标位置如下表所示：i123456789x（i）123456789y（i）123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在（）才能使到邮局到这9个村庄的总距离和最短。（A）（4.5，0）（B）（4.5，4.5）（C）（5，5）（D）（5，0）二、应用题（本大题共5小题，每小题6分，共30分）1、对于以下程序段，分析其最坏时间复杂度。intBinary(intn){intcount=1;while(n1){count=count+1;n=n/2;}returncount;}2、请分析使用分治法求解最接近点对问题其最坏时间复杂度如何为O（nlogn）。得分4装订线3、有n个集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi，集装箱不可分割。最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。请写出使用贪心算法求解最优装载问题所用的贪心策略。4、请列举3个会影响回溯搜索算法时间效率的因素。5、使用动态规划算法求解矩阵连乘问题，令m[i][j]为计算矩阵A[i:j]所需的最少乘法次数，请写出m[i][j]的递归式子，并说明计算过程中求解所有m[i][j]的先后次序。说明：A[i:j]表示从第i个矩阵开始连续到第j个矩阵结束。三、程序填空题（本大题共10空格，每空2分，共20分。注意：每个空格只填一个语句）1、使用回溯法求解n皇后问题，x[t]用于存储第t个皇后放置的列号，可直接使用求绝对值函数intabs(intx)。boolPlace(intk){for(intj=1;jk;j++)if(1)returnfalse;returntrue;}voidBacktrack(intt){if(tn)sum++;elsefor(inti=1;i=n;i++){x[t]=i;if(Place(t)==true)2}}得分1.5CM5装订线2、计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}作为输入，计算得到数组c，其中c[i][j]存储序列Xi={x1,x2,…,xi}和序列Yj={y1,y2,…,yj}的最长公共子序列长度。voidLCSLength(intm,intn,char*x,char*y,int**c){inti,j;for(i=1;i=m;i++)c[i][0]=0;for(i=1;i=n;i++)3for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j])4elseif(5)c[i][j]=c[i-1][j];else6}}3、使用分治法求解棋盘覆盖问题，用一个二维整型数组Board表示棋盘。Board[0][0]是棋盘的左上角方格。全局整型变量tile用来表示L型骨牌的编号，其初始值为0。算法的输入参数是：tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号；dr：特殊方格所在的行号；dc：特殊方格所在的列号；size：size=2k，棋盘规格为2k*2k。voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++;ints=76装订线if(drtr+s&&dctc+s)8else{910}if(drtr+s&&dc=tc+s)ChessBoard(tr,tc+s,dr,dc,s);else{Board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr=tr+s&&dctc+s)ChessBoard(tr+s,tc,dr,dc,s);else{Board[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr=tr+s&&dc=tc+s)ChessBoard(tr+s,tc+s,dr,dc,s);else{Board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}7装订线四、算法设计题（本大题共2小题，每小题15分，共30分。请先说明算法设计思路，然后用C语言实现）1、图的m着色问题给定有n个顶点的无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。输入：第一行：图的顶点数n和颜色数m接下来输入n行，每行有n个数组成，每个数可以是0或1，其中第i行第j列的数表示顶点i与顶点j是否有边相连，是1表示有边相连，是0表示无输出：能用m种不同颜色对图根据规则进行着色则输出Y，否则输出N。2、数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的结点总和最大。输入：第一行数塔的层数n接下来输入n行，分别为数塔的n层，其中第i行输入i个数输出：路径的最大和。得分8装订线华南农业大学期末考试答案（A卷）2010学年第一学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1A2A3B4B5A6B7C8A9A10C二、应用题（本大题共5小题，每小题6分，共30分）1、由于n每次缩小为原来的1/2，因此其最坏时间复杂度为O（logn）。2、T（n）＝2T（n/2）+O(n)T（1）＝O（1）有T（n）属于O（nlogn）其中2T（n/2）表示求n个点的最接近点对问题可以把点平均分成两部分，每一部分的点数目为n/2，对每部分递归地求最接近点。除此之外，还要计算一个点在左半部分，一个点在右半部分的情况，此时对于左边的每个点，在右边最多只需考虑6个点，因此可以在O（n）时间内完成此类情况。3、贪心策略为：重量轻的集装箱先装上轮船，依次循环直到不能再把剩余的集装箱装上去为止。4、(1)产生x[k]的时间；(2)满足显约束的x[k]值的个数；(3)计算约束函数constraint的时间；(4)计算上界函数bound的时间；得分得分9装订线(5)满足约束函数和上界函数约束的所有x[k]的个数。5、计算次序为：先算m[1][1],m[2][2]….m[n][n]1个矩阵连乘的情况，再算两个矩阵连乘的情况，依次类推，最后算n个矩阵连乘。三、程序填空题（本大题共10空格，每空2分，共20分。注意：每个空格只填一个语句）1、(abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])2、Backtrack(t+1)3、c[0][i]=0;4、c[i][j]=c[i-1][j-1]+1;5、c[i-1][j]=c[i][j-1]6、c[i][j]=c[i][j-1];7、size/2;8、ChessBoard(tr,tc,dr,dc,s);9、Board[tr+s-1][tc+s-1]=t;10、ChessBoard(tr,tc,tr+s-1,tc+s-1,s);四、算法设计题（本大题共2小题，每小题15分，共30分。请先说明算法设计思路，然后用C语言实现）1、可以通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。返回真即可：1.//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息2.boolisok(intstep)3.{4.vectorint::iteratoriter;5.for(iter=input[step].begin();iter!=input[step].end();iter++)6.{得分得分1.5CM10装订线7.if(Color[step]==Color[*iter])returnfalse;8.}9.returntrue;10.}11.//step表示0-n的节点，color_num是指给color_num的颜色的个数可用12.//判断如果给color_num的颜色的个数是否可行，如果可行返回true,否则false13.boolDFS(intstep,intcolor_num)14.{15.if(step=n)returntrue;16.else17.{18.inti;19.for(i=1;i=color_num;i++)20.{21.Color[step]=i;22.if(isok(step))23.{24.if(DFS(step+1,color_num))25.returntrue;26.}27.Color[step]=0;28.}29.}30.returnfalse;31.}2、在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从