算法设计与分析试卷

算法设计与分析试卷一、选择题（每题2分，共20分）（1）计算机算法的正确描述是()A．一个算法是求特定问题的运算序列B．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列C．算法是一个对任一有效输入能够停机的图灵机D．一个算法，它是满足5个特性的程序，这5个特性是：有限性、确定性、可行性、有0个或多个输入且有1个或多个输出（2）Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）Hanoi塔A.voidhanoi(intn,intA,intC,intB){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}B.voidhanoi(intn,intA,intB,intC){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}C.voidhanoi(intn,intC,intB,intA){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}（3）最长公共子序列利用的算法是（）A、分治法B、动态规划法C、贪心法D、回溯法（4）最大效益优先是（）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法（5）实现合并排序利用的算法是（）A、分治法B、动态规划法C、贪心法D、回溯法（6）分治法的适用条件是，所解决的问题一般具有这些特征（）A．该问题的规模缩小到一定的程度就可以容易地解决；B．该问题可以分解为若干个规模较小的相同问题；C．利用该问题分解出的子问题的解可以合并为该问题的解D．该问题所分解出的各个子问题是相互独立的。（7）分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先（8）分支限界法解旅行售货员问题时，活结点表的组织形式是（）A、最小堆B、最大堆C、栈D、数组（9）回溯法解旅行售货员问题时的解空间树是（）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树D.预排序与递归调用（10）以深度优先方式系统搜索问题解的算法称为()A、分支界限算法B、概率算法C、贪心算法D、回溯法答案：1.D2.B3.B4.A5.A6.B7.A8.A9.A10.DD.voidhanoi(intn,intC,intA,intB){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}二、填空题（每空2分，共30分）1、一个算法是对特定问题求解的一种描述，它是。2、矩阵乘法如下：for(int=0;in;i++)for(j=0;jn;j++){C[i][j]=0;for(k=0;kn;k++)C[i][j]+=a[i][k]*b[k][j];}程序中所有语句的执行次数为T（n）=，它的渐进时间复杂度为3、一个无向连通图不是双向连通图的充要条件是图中存在。4、二分搜索过程的算法行为可以用一颗来描述。5、用贪心法求解背包问题时，为了使收益最大化要选择_________的物品装入背包。6、多段图问题中，结点S是起点，结点T是终点，则cost(i,j)的含义是。7、使用的深度优先生成状态空间树中结点的求解方法称为回溯法。8、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是，只使用约束条件进行裁剪的是9、用分支限界法求解最优化问题的三种形式：、、。10、在15谜问题中，对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中，i和j分别是空格在棋盘上的行和列下标。二、答案：1、（答案：指令的有限序列）。2、（答案是：T(n)=2n3+3n2+2n+1,O(n3)）3、（答案：关节点）4、（答案：二叉判定树）5、（答案：单位重量收益最大）6、第i阶段结点j到T的最短距离的成本。7、剪枝函数8、0/1背包问题、N皇后问题9、（答案：FIFO分支限界法、LIFO分支限界法、LC分支限界法）。10、∑Less（k）+i+j三、算法设计题（每题10分，共20分）1、用分治法求最大元、最小元templateclassTypevoidSortableListType::MaxMin(inti,intj,Type&max,Type&min)const{Typemin1,max1;if(i==j)max=min=l[i];elseif(i==j-1)if(l[i]l[j]){max=l[i];min=l[j];}else{max=l[i];min=l[j];}else{intm=(i+j)/2;MaxMin(i,m,max,min);MaxMin(m+1,j,max1,min1);if(maxmax1)max=max1;if(minmin1)min=min1;}}2、用动态规划法编写最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序的长度。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i=m;i++)c[i][0]=0;for(i=1;i=n;i++)c[0][i]=0;for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}四、应用题（每题10分，共30分）1、识别下面的图（a）(b)的图的关节点，画出它们的双连通分图。图（a）图（b）答案：图（a）的深度优先生成树为：12345678DFN12364578L12364566(1)根结点1只有一个孩子，故不是关节点(2)DFN（2）=L(3)DFN（3）=L(4)DFN(4)=L(7)故此图的关节点为2、3、4；图（b）的深度优先生成树为：1287435612345678DFN12356748L11111515（1）根结点1只有一个孩子，不是关节点；（2）除根以外的任何一个结点u和他的孩子w都不存在DFN（u）=L(w)故无关节点图（a）的双连通分图为：图（b）的双连通分图为：12233344735682、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。（1）对各个物品进行排序时，依据的标准都有哪些？（2）使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。（3）上述解中哪个是最优的？物品ABCDEFG重量35306050401025价值10403050354030答：（1）标准：重量、价值和单位价值。（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，32746815得到价值为190.625。（3）显然使用单位价值作为标准得到的是最优解。3、设有子集和数问题的实力W=（W0,W1,W2,W3,W4)=(2,5,6,9,12)和M=35。求W中元素之和等于M的所有子集。画出对于这一实例由SumOfSub算法实际生成的那部分状态空间树。答案：对于上面的实力执行SumOfSub函数，将实际生成如下图所示的状态空间树上的结点，图中A、B为三个答案状态，它们分别代表可行点（1,0,1,1），（0,1,0,0,1）。1010010101010,0,342,1,320,1,327,2,272,2,275,2,270,2,277,3,217,4,128,3,21A5,3,215,4,12B6,3,21