算法复习材料1.doc

《算法复习材料1.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法复习练习题一．计算题与简答题1.用表示函数f与g之间的关系。(1)f(n)=10000ng(n)=n-10000(2)f(n)=2ng(n)=3n/n(3)f(n)=n3log2ng(n)=n2log3n(4)f(n)=log2ng(n)=log3n(5)f(n)=100n+n100g(n)=n!2.估计下列算法的时间复杂性的阶。(1)算法A的时间复杂性为，(2)算法B的时间复杂性为3.计算下面算法中count=count+1的执行次数算法1.10COUNT3输入：，k为正整数输出：count=count+1的执行次数count=0fori=1tonj=2whilej<=nj

2、=j2count=count+1endwhileendforreturncountendCOUNT34.下面是冒泡排序的算法，该算法的基本运算是什么？求该算法最坏情况下的时间复杂性。算法BUBBLESORT输入：正整数n,n个元素的数组A[1..n]。输出：按升序排列的数组A[1..n]。i=n;sorted=falsewhilei>1andnotsortedsorted=trueforj=2toiifA[j]

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

4、=x*yendif____________endpower2.以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法MATCHAIN1输入：矩阵链长度n,n个矩阵的阶r[1..n+1],其中r[1..n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数。输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S[1..n,1..n]。　　　fori=1tonC[i,i]=0//对角线d0置０　　ford=1ton-1//逐条计算对角线d0~dn-1fori=1ton-d//计算对角线dd的n-d个元素。　　　　____________C[i,j]=∞f

5、ork=i+1tojx=____________if____________thenC[i,j]=x;S[i,j]=kendifendforendforendforreturnC[1,n],SendMATCHAIN1　　　　根据S中的信息递归确定最优乘法顺序。算法MATCHAIN_PRODUCT输入：矩阵链长度n,n个矩阵M1,M2,…,Mn,最优乘法顺序的信息数组S[1..n,1..n]。输出：按最优顺序计算的矩阵链乘积M=M1M2…Mn。M=matchain_product(1,n)returnMendMATCHAIN_PRODUCT过程matchain_product(i,

6、j)//求按最优顺序计算的矩阵链乘积MiMi+1…Mj并返回。　　if____________thenreturnMielseA=matchain_product____________B=matchain_product____________C=multiply(A,B)//计算两个矩阵乘积C=AB。returnCendifendmatchain_product3.以下是迷宫问题的算法算法MAZE输入：正整数m,n，表示迷宫的数组M[0..m+1,0..n+1](迷宫数据存于M[1..m,1..n]中)，迷宫的入口位置(ix,iy),出口位置(ox,oy)。输出：迷宫中入口至

7、出口的一条通路，若无通路，则输出nosolution。M[0,0..n+1]=M[m+1,0..n+1]=1M[0..m+1,0]=M[0..m+1,n+1]=1//设置迷宫边界。tag[1..m,1..n]=0为dx[1..4],dy[1..4]置值flag=false//flag表示是否存在通路。x=ix;y=iy;tag[x,y]=1//进入入口,(x,y)表示当前位置。i=1;k[i]=0while____________andnotflagwhile__________