算法分析与设计复习

考试试卷第1页共4页一、选择题（本题共5小题，每小题3分，共15分）1.关于算法2.关于NP问题3.关于查找的效率4.关于排序的时间复杂度和空间复杂度5.简单程序段的时间复杂度分析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];}s=0;for(i=1;i=n2;i++)for(j=1;j=i;j++)s=s+i*j;以下不是算法所必须具备的特征（）。A有穷性B确切性C高效性D可行性（）不是衡量算法的标准。A时间效率B空间效率C问题的难度D适应能力算法分析是（）。A．将算法用某种程序设计语言恰当地表示出来B．在抽象数据集合上执行程序，以确定是否会产生错误的结果C．对算法需要多少计算时间和存储空间作定量分析D．证明算法对所有可能的合法输入都能算出正确的答案下面问题（）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小生成树问题D连续背包问题下列算法中不能解决0-1背包问题的是（）A贪心法B动态规划C回溯法D分支限界法若L是一个NP完全问题，L经过多项式时间变换后得到问题L’，则L’是一个AP类问题BNP类问题CNP完全问题D不可解问题下面关于NP问题说法正确的是（）ANP问题都是不可能解决的问题BP类问题包含在NP类问题中CNP完全问题是P类问题的子集DNP类问题包含在P类问题中以下关于判定问题难易处理的叙述中正确的是（）。A．可以由多项式时间算法求解的问题是难处理的考试试卷第2页共4页B．需要超过多项式时间算法求解的问题是易处理的C．可以由多项式时间算法求解的问题是易处理的D．需要超过多项式时间算法求解的问题是不能处理的Prim算法求最小生成树采用的是（）算法思想。A贪心算法B动态规划法C回溯法D蛮力法归并排序算法的时间复杂度和空间复杂度是（）快速排序算法最差情况下的时间复杂度是（）实现大整数的乘法的分治算法的时间复杂度是（）有序表(12,24,36,48,60,72,84)中顺序、⼆分查找关键字72时所需进⾏的关键字⽐较次数是（）⽤某种排序⽅法对关键字序列（25,84,21,47,15,27,68,35,20）进⾏排序，序列的变化情况如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84请问采⽤的是哪种排序算法（）设某算法的时间复杂度为O(n3)。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模多大的问题？1、一个算法的优劣可以用空间复杂度与时间复杂度来衡量。2、这种不断回头寻找目标的方法称为回溯法。3、直接或间接地调用自身的算法称为递归算法。二、求解或证明下面各式：（本题共4小题，共30分）1.求和式的计算或证明niii13)1(F(n)=bF(n-1)+G(n),F(0)=c证明：F(n)=cbn+niiniGb1)(。由此，推导Hanoi塔问题的通项公式。2.二阶常系数齐次线性递推关系求解x(n)=4x(n-1)-3x(n-2),x(1)=1,x(2)=3x(n)=6x(n-1)-9x(n-2)+n,x(0)=0，x(1)=1a0=0，a1=1，an=5an-1−6an-2考试试卷第3页共4页3.利用主定理，求T(n)增长的阶T(n)=25T(n/5)+n^2的时间复杂度T(n)=2T(n/3)+n^2的时间复杂度4.函数按照增长的速度从低到高排序4n2，logn，3n，n!，n2/32+3n+4n2，2logn，2n+3n，2^2^n，2^n^2，sqrt（n）5.证明：函数的复杂度f(n)=n3+n2log100n6.已知函数x(intn){if(n=3)return1;elsereturnx(n-2)+x(n-4)+1;}求x(x(8))三、算法理解题（本题共4小题，共35分）1.运用分治法算法计算m*n。2.运用俄罗斯农夫算法计算m*n。59*473.运用两种不同的算法求2348和1776的最大公因子。4.利用减治法计算pn除以q的余数。31000%55.利用Dijkstra算法对下图结点a，求a到所有其他结点的最短路径。bcfead4hg32146213266.按照Johnson-Trotter算法和字典序生成全排列的算法给出下面排列的后面10个排列。42351考试试卷第4页共4页7.已知背包承重L，待放入背包的物品如下所示，用分支限界法求其最优解。n=4个物品，大小分别为W={1,2,4,6}，价值分别为P={5,5,6,9}，背包容量为M=10。8.已知矩阵M1（25*10）、M2（10*5）、M3（5*30）、M4（30*20）、M5（20*15），利用矩阵链相乘的动态规划算法，计算所需的最少乘法次数，并根据计算填写下表。四、算法设计与分析题：（本题共2小题，第1小题15分，第2小题5分，共20分）1.对下面算法，分析该算法的复杂度。请改进该算法，使之更高效。2.利用分治法或动态规划法设计算法。利用动态规划设计算法，实现最大子段和的求解。如(-2,11,-4,13,-5,-2)Sum(A[1..n])//Input：整型数组Amax=0fori=1ton–1doS[i，i]=A[i]ifmaxS[i，i]max=S[i，i]forj=i+1tondoS[i，j]=S[i，j–1]+A[j]ifmaxS[i，j]max=S[i，j]returnmax利用分治法求给定数列的最大值。Max(A[m..n])//Input：整型数组Aifm==nreturnA[m]elseS=Max(A[m..m+(n-m)/2])T=Max(A[m+(n-m)/2+1..n])ifSTreturnTelsereturnS思考：任意自然数n都可以分为若干组自然数的和，比如4=1+1+1+1=2+1+1=3+1=2+2共4种分解方法。设计算法，求n的不同分解方式。