算法复习材料1

1、福建师范大学学生门户 整理 更多课件题库答案尽在 算法复习练习题一计算题与简答题1. 用表示函数f与g之间的关系。(1) f(n)=10000n g(n)=n-10000(2) f(n)=2n g(n)=3n/n(3) f(n)=n3log2n g(n)=n2log3n(4) f(n)=log2n g(n)=log3n(5) f(n)=100n+n100 g(n)=n!2.估计下列算法的时间复杂性的阶。(1)算法A的时间复杂性为，(2)算法B的时间复杂性为3. 计算下面算法中count=count+1的执行次数算法1.10 COUNT3 输入：，k为正整数 输出：count=count+1的执

2、行次数 count=0 for i=1 to n j=2 while j<=n j=j2 count=count+1 end while end for return count end COUNT34. 下面是冒泡排序的算法，该算法的基本运算是什么？求该算法最坏情况下的时间复杂性。算法 BUBBLESORT输入：正整数n,n个元素的数组A1.n。输出：按升序排列的数组A1.n。i=n;sorted=falsewhile i>1 and not sorted sorted=true for j=2 to i if Aj<Aj-1 then Aj Aj-1 sorted=fal

3、se end if end for i=i-1end while end BUBBLESORT5. 用两种方法证明log n!= (n log n)。(1)用代数方法(2)用积分方法6. 求解递推关系式 f(n)=-6f(n-1)-9f(n-2)。 7. 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写出该方程的一般形式，并指出其中各参数的意义。8. 算法有哪五个特性？9. 什么是最优子结构？10. 贪心法与动态规划有何根本区别？11. 设计回溯算法通常包括哪些步骤？12. 随机算法分成那几类，各有什么特点？三算法填空1. 以下是计算xm的值的过程power ( x,

4、 m )/计算xm的值并返回。if m=0 then y=_else y=_ y=y*y if m为奇数 then y=x*yend if_end power2. 以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S1.n, 1.n。for i=1 to n Ci, i=0 /对角线d0置 for d=1 to n-1 /逐条计算对角线d0dn-1 for i=1 to n-d /

5、 计算对角线dd的n-d个元素。 _ Ci, j= for k=i+1 to j x= _ if _ then Ci, j=x; Si, j=k end if end for end for end for return C1, n, Send MATCHAIN1根据S中的信息递归确定最优乘法顺序。算法 MATCHAIN_PRODUCT输入：矩阵链长度n, n个矩阵M1, M2, , Mn , 最优乘法顺序的信息数组S1.n, 1.n。输出：按最优顺序计算的矩阵链乘积M=M1M2Mn 。 M=matchain_product( 1, n ) return Mend MATCHAIN_PRODU

6、CT 过程 matchain_product (i, j) / 求按最优顺序计算的矩阵链乘积MiMi+1Mj并返回。if _ then return Mi else A=matchain_product _ B=matchain_product _ C=multiply( A , B) /计算两个矩阵乘积C=AB。 return C end ifend matchain_product3. 以下是迷宫问题的算法算法 MAZE 输入：正整数m, n，表示迷宫的数组M0.m+1, 0.n+1 (迷宫数据存于M1.m, 1.n中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。 输出：迷

7、宫中入口至出口的一条通路，若无通路，则输出no solution。 M0, 0.n+1=Mm+1, 0.n+1=1 M0.m+1, 0=M0.m+1, n+1=1 /设置迷宫边界。 tag1.m, 1.n=0 为dx1.4, dy1.4置值 flag=false /flag表示是否存在通路。 x=ix; y=iy ; tagx, y=1 /进入入口, (x, y)表示当前位置。 i=1; ki=0 while _ and not flag while _ and not flag _ /试沿着下一个方向搜索。 x1= x+dxki; y1= y+dyki if Mx1, y1=0 and ta

8、gx1, y1=0 then /位置(x1,y1)可走 if x1=ox and y1=oy then _ /找到一条通路 else x=x1; y=y1; tagx, y=1 /进入新位置。 i=i+1 ； ki= _ /准备搜索下一个位置。 end if end if /否则，剪枝 end while_; x=x-dxki; y=y-dyki/回溯 end while if flag then outputroute(k, i) /输出由k1.i表示的通路。 else output “no solution”/输出无解end MAZE4. 下面是求一个序列的多数元素的递归算法算法 MAJO

9、RITY输入：n个元素的数组A1.n。输出：若A1.n存在多数元素，则输出；否则输出none。 c=candidate ( 1 ) / 求A1.n中的候选多数元素。count=0 /以下验证c是否为A1.n中的多数元素。 for j=1 to n if Aj=c then count=count+1 end for if _ then return c else return noneend MAJORITY过程 candidate ( m )/求Am.n中的候选多数元素并返回。j=m; c=Am; count=1while j<n and count>0 j=j+1 if _ t

10、hen _ else _ /除去两个不同的元素。end whileif j=n then return c /此时序列已扫描完毕。else return _ end candidate5. 下面是0-1背包问题的算法算法 KNAPSACKREC输入：物品数n, n种物品的体积数组s1.n和价值数组v1.n, 背包容量C。输出：装入背包物品的最大总价值，以及最优解的信息数组H0.n, 0.C。 for i=0 to n for j=0 to C Vi, j=-1 maxv=knapsack(n, C) return maxv , Hend KNAPSACKREC过程 knapsack(i, j)

11、 /从i种物品中选择物品装入容量为j的背包中，求背包中/物品所能达到的最大总价值并返回，同时将最优解的相应/信息存入数组H0.n, 0.C。 if Vi, j=-1 then /相应的子问题未解过。 if i=0 or j=0 then Vi,j=0 else if si>j then Vi, j= _ Hi, j= _ else a1=_ a2=knapsack(i-1, j) if a1>=a2 then Vi, j=a1; Hi, j= _ else Vi, j=a2; Hi, j=0 end if end if end if end if return _end knaps

12、ack算法 KNAPSACK_SOLUTION输入：物品数n , 背包容量C, n种物品的体积数组s1.n, 相应的0/1背包问题的最优解信息数组H0.n, 0.C。输出：相应的0/1背包问题的最优解X1.n。 y=C / y表示当前背包的剩余容量Xn=Hn, Cfor i=n to 2 if Xi=1 then y=_ Xi-1= _end forreturn Xend KNAPSACK_SOLUTION6. 以下是随机化的线性选择算法算法 RANDOMIZEDSELECT输入：整数n, k, 1<=k<=n, 以及n个元素的数组A1.n。输出：A中的第k小元素s。 s=rsel

13、ect ( A , 1, n, k )end RANDOMIZEDSELECT过程 rselect ( A , low, high, k ) /求Alow.high中的第k小元素并返回。 v=random(low, high) mm= _ 将Alow.high分成三个数组： A1=a|a<mm，A2=a|a=mm, A3=a|a>mm/以下选择一个子问题递归或直接解。 case|A1|>=k: return _ /求A1的第k小元素。|A1|+|A2|>=k: return mm /此时mm为Alow.high的第k小元素。 |A1|+|A2|<k: return

14、 rselect _ /求A3的第k-|A1|-|A2|小元素 end caseend rselect7. 以下是归并排序的分治算法MERGESORT 输入：n个元素的数组A1.n。 输出：按非降序排序的数组A1.n。 mergesort(A , 1, n) end MERGESORT 过程 mergersort( A , low, high ) /将Alow.high 按非降序归并排序。 if low<high then mid=_ /平均分解成两个子数组mergesort_ /分别对两个子数组递归mergesort_MERGE (A , low, mid, high) /合并两个有序

15、的子数组 end ifend mergesort8. 以下是分数背包问题的贪心算法算法 GREEDY_KANPSACK输入：表示背包容量的实数C, 物品数n, 表示n个物品的体积和价值的实数数组s1.n和v1.n。输出：装入背包物品的最大总价值maxv和相应的最优解x1.n。 for i=1 to n yi=vi/si /求n个物品的单位体积价值y1.n。 end for /对y1.n按降序地址排序，排序结果返回到数组d1.n /中, 使得yd1>=yd2>=>=ydn。 d=sort(y, n) for i=1 to n xi=0 /对x1.n初始化。 i=1; maxv=

16、0; rc=C /以下rc表示当前背包的剩余容量。while _ and i<=nj=di / uj为当前考虑选择的物品 if sj<=rc then xj= _; rc= _ /物品uj全部装入背包。 else xj= _ /选择物品uj的一部分将背包填满。 rc=0 end if maxv= _i= _ end while return maxv, x1.nend GREEDY_KNAPSACK9. 以下是子集合问题的回溯算法算法 SUBSETSUM 输入:正整数n,正实数b,表示含有n个正实数的集合S的数组a1.n。 输出:集合S的元素之和等于b的所有子集，若无解，则输出“n

17、o solution”。 for i=1 to n xi=0 /用x1.n表示子集，初始化为空集。 r=0 for i=1 to n r=r+ai flag=subset(0, 0, r)if not flag then output “no solution” end SUBSETSUM 过程：subset(k, sum, r) /在已经求出的部分解x1.k固定的情况下，求关于S, b的/子集和问题的所有解并输出，有解返回true, 否则返回/false。 / sum= 表示当前子集的元素之和，r= 表示剩/余元素之和。 if sum=b then /找到一个解。output x1.n; t

18、=true /输出当前解。 elseif k<n and sum<b and sum+r>=b then /可继续往下搜索。r=_ xk+1=0t1=subset_ /搜索左子树（对应xk+1=0）xk+1= _t2=setsub_ /搜索右子树t=t1 or t2else t=_end if end if _ return tend subset10. 下面是一个求n个元素全排列的算法算法 PERMUTATION 输入：正整数n和存储n个元素a1 , a2, an的数组P1.n。输出：a1 , a2, an的全排列。 perml ( 1 )end PERMUTATION过程

19、 perml ( m )/在P1.m-1中元素固定不变的情况下，求Pm.n中元素/的全排列，并输出P1.n中元素的相应排列。if _ then / 此时只求一个元素Pn的全排列。 output P1.n; / 输出P1.n中元素的一个新排列。else for j=m to n PmPj _ _ end for end if end perml11. 以下是求最长公共子序列的算法算法 LCS 输入：非负整数n、m, 长度分别为n和m的序列A= a1a2an和B=b1b2bn 。 输出：A和B的最长公共子序列长度Ln, m和存储最长公共子序列的有关信息的数组H1.n, 1.m。 for i=0 t

20、o n Li, 0=0 for j=0 to m L0, j=0 for i=1 to n for j=1 to m if ai=bj then Li, j= _ ; Hi, j=0 else if Li-1, j>=Li, j-1 then Li, j= _ ; Hi, j=1 else Li, j=Li, j-1 ; Hi, j= _ end if end if end for end for return Ln, m, H end LCS算法 LCSS输入：非负整数n、m, 长度分别为n和m的序列A和B的最长公共子序列的有关信息数组H1.n, 1.m, 序列A= a1a2an 。输

21、出: 序列A和B的最长公共子序列C 。 C= /表示空序列。 i=n; j=m while i>0 and j>0 if Hi, j=0 then 在C的前面插入ai i=_; j=_ else if Hi, j= _ then i=i-1 else j=j-1 end if end while return C end LCSS12. 以下是0-1背包问题的回溯算法算法 KNAPSACK01输入: 物品数n, n种物品的体积数组s1.n和价值数组v1.n,背包容量C。输出：装入背包物品的最大总价值maxv和最优解x01.n。 /用x1.n表示选择的物品子集，初始化为空集。 rv=

22、0; rs=0for i=1 to nrv=rv+vi ; rs=rs+si maxv=0; x01.n=x1.n=0 / x0表示当前最优解。knapsack01(0, C, 0, rv, rs)output maxv, x01.n end KNAPSACK01 过程：knapsack(k, r, cv, rv, rs) /在已知当前最优值为maxv且已经求出的部分解x1.k固/定的情况下，求 0/1背包问题的最优值和最优解，并更新/maxv和x0。 r表示当前背包的剩余容量, cv表示当前背/包中物品的总价值为，rv= , rs= 。 if r>=0 and cv>maxv t

23、hen /找到更优的解，更新当前最优值。 maxv=_; x0=x end if if rs<=r then if cv+rv>maxv then maxv=cv+rv; x01.k=x1.k; x0k+1.n=1; end if else if r>0 and cv+rv>maxv then /可继续往下搜索。 rv=_; rs=_ xk+1=0 knapsack_ /搜索左子树（对应xk+1=0） xk+1=1 knapsack_ /搜索右子树end if end if _end knapsack13. 下面是求第k小元素的算法算法 SELECT输入：整数n, k,

24、 1<=k<=n, 以及n个元素的数组A1.n。输出：A中的第k小元素s。 s=select ( A , 1, n, k )end SELECT过程 select ( A , low, high, k ) /求Alow.high中的第k小元素并返回。 p=high-low+1 /p为当前处理的元素个数。 if p<44 then / 当元素个数<44时，直接求解。 将Alow.high排序 return(Alow+k-1) end if / 以下分解子问题。 q=；/将Alow.high每5个分组，剩余的被排除。 将Alow.low+5q-1分为q组, 每组5个元素；

25、将q组中的每一组单独排序并找出中项，所有的中项存于数组M1.q中； mm=select(_) /求中项序列M的中项mm 将Alow.high分成三组： A1=a|a<mm, A2=a|a=mm, A3=a|a>mm/以下选择一个子问题递归或直接解。 case|A1|>=k: return select (_) |A1|+|A2|>=k: return mm |A1|+|A2|<k: return select (_) end caseend select14. 有期限的作业安排问题算法 JOB_ARRANGEMENT输入：作业数n, 表示n个作业的期限和收益的数组

26、d1.n和p1.n。输出：最优的作业安排序列J1.k和安排的作业数k。/对p1.n按降序地址排序，排序结果返回到数组a1.n /中,使得pa1>=pa2>=>=pan。 a=sort(p, n) d0=0; J0=0 /设一个虚拟作业编号为，期限为 J1=a1 /直接安排收益最高的作业jaik=1 /以下k总是表示当前已被安排的作业数。for t=2 to ni= _ / ji为当前考虑安排的作业。 r=k while _ and dJr>r _ end whileif dJr<=di and _ then /把i插入到J中的r+1位置上。 for s=k to

27、r+1 Js+1=Js Jr+1= _ k= _end if end for return k, J1.kend JOB_ARRANGEMENT15. 以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S1.n, 1.n。for i=1 to n Ci, i=0 /对角线d0置 for d=1 to n-1 /逐条计算对角线d0dn-1 for i=1 to n-d / 计算对角线dd的n-d个元素。 _ Ci, j= for k=i+1 to j x= _ if _ then