东南大学算法复习题Word格式文档下载.docx

东南大学算法复习题Word格式文档下载.docx

《东南大学算法复习题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《东南大学算法复习题Word格式文档下载.docx（27页珍藏版）》请在冰点文库上搜索。

什么是计算过程？

一般认为，算法是由若干条指令组成的有穷序列，有五个特性a.确定性（无二义）b.能行性（每条指令能够执行）c.输入d.输出e.有穷性（每条指令执行的次数有穷）

只满足前4条而不满足第5条的有穷指令序列通常称之为计算过程。

算法研究有哪几个主要步骤？

主要从哪几个方面评价算法？

算法研究的主要步骤是1）设计2）表示3）确认，合法输入和不合法输入的处理4）分

析5）测试

评价算法的标准有1）正确性2）健壮性3）简单性4）高效性5）最优性

关于多项式时间与指数时间有什么样的结论？

1.多项式时间的算法互相之间虽有差距，一般可以接受。

2.指数量级时间的算法对于较大的n无实用价值。

什么是相互独立的函数序列？

何时称函数项μk（x）能被其它函数项线性表出？

设{μ0（x）,μ1（x）,μ2（x）,...,μn（x）,...}是某一数域上的函数序列，（x的值以及μk（x）（k=0,1,2,⋯）的值都在同一个数域中）任取μk（x）（k=0,1,2,⋯），不存在数域中的数α1，α2，⋯，αp，使得μk（x）=α1μi1（x）+α2μi2（x）+⋯+αpμip（x），即任何一个函数项μk（x）不能被其它函数项线性表出。

根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？

1.若方程（**）恰有r个互不相同的特征根α1，α2，⋯，αr（即i≠j时有αi≠αj），则齐次方程（*）的解为an＝A1+A2+⋯+Ar（齐通解，即齐次方程的通解）（A1～Ar为待定系数，可由r个连续的边界条件唯一确定）

2．若α1，α2是（**）方程的一对共扼复数根ρ和ρ，eiθeiθ.则这两个根对应的解的部分为Aρncos（nθ）+Bρnsin（nθ）（A,B为实的待定系数）

3．若α是（**）方程的k重根，则α对应的解的部分为C1αn+C2nαn+C3n2αn+⋯+Cknk-1αn（C1～Ck为待定常数）

4．若（*）方程中的f（n）≠0（非齐次），且q（n）是（*）的一个解，则（*）方程的解为：

（*）的齐通解（含有待定系数）+q（n）（非齐特解），（齐通解中的待定系数由边界条件唯一确定）

求和中的通项与积分中的被积函数之间有什么样的关系？

求和中的通项的表达形式一般就是被积函数，一般用放缩的方法求得通项得上下界。

主定理的内容是什么？

根据主定理的结论，可以获得哪些关于算法改进的启示？

T（n）=a*T（n/b）+f（n）

1） 

若有ε>

0,使f（n）=O（）（即f（n）的量级多项式地小于的量级）,则T（n）=Θ（）。

2） 

若f（n）=Θ（）（即f（n）的量级等于的量级）,则T（n）=Θ（）。

3） 

若f（n）=Θ（）,则T（n）=Θ（）

3）若有ε>

0,使f（n）=Ω（）ε+）（aLogbn（即f（n）的量级多项式地大于的量级）,且满足正规性条件：

abLogn存在常数c<

1,使得对所有足够大的n，有a*f（n/b）≤c*f（n）,则T（n）=Θ（f（n））。

正规性条件的直观含义:

对所有足够大的n，a个子问题的分解准备与再综合所需要的时间总和，严格小于原问题的分解准备和综合所需要的时间。

因此一般来说，对于时间复杂度满足递归关系T（n）=a*T（n/b）+f（n）的算法，只需比较f（n）与的量级大小，aLogbn算法的时间复杂度总是与量级大的那个相同（即小的那个可以忽略）；

若f（n）与的量级相同（或只差），aLogbnnLogk则算法的时间复杂度为f（n）*。

主定理对于算法改进得启示在于：

1）当T（n）=Θ（）时，即当的量级高于f（n）的量级时，n的量级在算法的时间复杂度中起主导作用。

因而此时首先应当考虑使aLogbnaLogbnaLogblogba的值变小，而暂时无须考虑如何改善f（n），即此时要考虑减小a（子问题个数）且使b不变（n/b为子问题规模），或增大b（减小子问题规模）而使a不变。

也就是说，此时的重点应考虑改进子问题的分解方法，暂不必考虑改进子问题组合时的处理。

2）当f（n）的量级高于或等于的量级时，则f（n）的量级在算法的时间复杂度中起主导作用。

因而此时首先应当考虑把f（n）的量级往下降，即此时应着重改善子问题组合时的处理方法，减少该部分工作的处理时间f（n）。

分治法的要领是什么？

（分治法可分为哪三个主要步骤？

）

分治法的要领

分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；

首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。

由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。

因此分治法分三步：

1将原问题分解为子问题（Divide）

2求解子问题（Conquer）

3组合子问题的解得到原问题的解（Combine）

分治法求最大、最小元算法的主要思想？

当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。

当n>

2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。

先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；

将两个最小元进行比较，就可得n个元素的最小元。

求最大、最小元算法的时间复杂度（比较次数）下界是多少？

分治算法在什么情况下可以达到下界？

在规模为n的数据元素集合中找出最大元和最小元，至少需要3n/2-2次比较，即3n/2-2是找最大最小元算法的下界。

当n=2k,或当n≠2k时，若n是若干2的整数幂之和，（e.g.42=32+8+2），

则算法的时间复杂度仍可达到3n/2-2。

如何用分治法求两个n位二进制数x和y的乘积？

算法的时间复杂度是多少？

若n=2k，则x可表为a2n/2+b，y可表为c2n/2+d（如图）,其中a,b,c,d均为n/2位二进制数。

于是x*y=（a2n/2+b）（c2n/2+d）=ac2n+（ad+bc）2n/2+bd，计算式ac2n+（ad+bc）2n/2+bd中的ad+bc可写为：

而（ad+bc）=（a+b）（d+c）-ac-bd,因此在ac和bd计算出之后，只要再做4次加减法，一次（n/2位数的）乘法就可以计算出ad+bc。

而原来计算（ad+bc）需要做2次乘法、一次加法；

新的计算公式比原方法少做了一次乘法。

T（n）=3T（n/2）+Θ（n），即a=3,b=2,f（n）=Θ（n）。

此时有：

==naLogbn32Logn1.59，并仍有f（n）=O（），ε−）（aLogbn于是有T（n）=Θ（n1.59），比Θ（n2）要好不少。

用200字概括Select（求第k小元）算法的主要思路。

1.若S<

50，则采用堆排序的方法找出第k小的元素

2.将n个元素分成[n/5]组，每组5个元素

3.对每个5元组进行排序，全部5元组排序后，从每组中取出第3个元素（中间元）得到一个长为[n/5]的数组M

4.递归调用Select（[|M|/2],M），即在M数组中找到第[|M|/2]小的数（中位数），记为m

5.依次扫描整个数组S，此项工作所需时间为O（n）。

当si<

m时将si放入数组S1；

当si=m时将si放入数组S2；

当si>

m时将si放入数组S3；

在得到的3个集合中，S1中的数均小于m；

S2中的数均等于m；

S3中的数均大于m。

6.按照k值大小，共可分成下列三种情况（注意S2至少有一个元素m）：

k≤|S1|；

|S1|<

k≤|S1|+|S2|；

以及k>

|S1|+|S2|。

下面针对这三种情况分别进行讨论。

6.a：

若k≤|S1|，则第k小元素必定在S1中。

此时递归调用Select（k,S1），就可以获得第k小元素。

因大于等于m的数据元素至少有3n/10-6个，而S1中的数均小于m，故S1中的数据元素至多有7n/10+6个，即|S1|≤7n/10+6。

因此，调用Select（k,S1）的时间复杂度不超过T（7n/10+6）。

6.b：

若|S1|<

k≤|S1|+|S2|，则第k小元素必定在S2中。

因为S2中的元素的值均等于m，故第k小元素就是m。

由于答案已经得到，此时立刻返回第k小元素m。

这部分工作的时间复杂度为O

（1）。

6.c：

若k>

|S1|+|S2|，则第k小元素必定大于m，因此在S3中。

而且此时该元素在S3中应为第k-|S1|-|S2|小的元素。

于是递归调用Select（k-|S1|-|S2|,S3），就可以获得S中的第k小元素。

因小于等于m的数据元素至少有3n/10-6个

1的情况下，T（n）分别为什么？

1及p+q时间复杂度为T（n）=T（p*n）+T（q*n）+a*n时，在p+q

T（n）≤a*n*∑k=0∞（p+q）k

矩阵相乘算法目前最好的时间复杂度是多少？

目前矩阵乘法最好的时间复杂度是能做到O（n2.376）

叙述Strassen矩阵相乘算法的主要思路和意义。

把矩阵A，B分成4个规模为n/2的子矩阵快

C11=A11B11+A12B21,C12=A11B12+A12

C21=A21B11+A22B21,C22=A21B12+A22B22

同时引入下列Mi（i=1,2...7）

则计算两个n阶矩阵的乘法为7对n/2阶矩阵的乘法（时间为7T（n/2））,以及18对n/2阶矩阵的加减法则递归方程为T（n）=7T（n/2）+Θ（n2）,由主定理得T（n）=Θ（n2.81）.Strassen矩阵相乘算法意义在于打破了人们认为矩阵乘法得时间复杂度为Θ（n3）得固定看法。

试用200～300字概述寻找最近点对算法的主要步骤。

该算法中有哪几点最为关键？

该算法是否可改进？

主程序算法：

读入n个点的坐标，这n个点的x坐标和y坐标分别放在X，Y两个数组中，然后进行预处理：

对X数组中的n个x坐标值按从小到大的次序进行排序，排序过程中保持x坐标和y坐标的对应关系：

若X[i]与X[j]对换位置，则Y[i]与Y[j]也做相同的对换。

另外，若两个点的x坐标相同，则y坐标值小的排前。

X数组排好之后就固定了，以后不再改变，以便在O

（1）时间对其实现分拆。

（排序时间为Θ（nlogn））将数组IND初始化为：

IND[i]=i（i=1,2,┉,n）。

数组IND即是用来保持x坐标和y坐标的对应关系的机制，IND[i]记录的是其y坐标值为Y[i]的点所对应的x坐标在X数组中的下标。

对Y数组中的n个y坐标值按从小到大的次序进行排序，排序过程中保持y坐标和x坐标的对应关系：

若Y[i]与Y[j]对换位置，则IND[i]与IND[j]也做相同的对换。

这样，当给了一个点的y坐标Y[i]之后，就可以在O

（1）时间找到其对应的x坐标：

Y[i]与X[IND[i]]就是该点的y坐标和x坐标。

调用子程序FCPP（1,n,X,Y,IND,δ,p,q）就可求得n个点中的最近点对（p,q）和最小距离δ。

子程序FCPP的主要执行过程：

首先看当前处理的点数。

若不超过3个点，就直接进行相互比较。

若超过3个点，则把点的y坐标分为两部分：

左边和右边。

然后进行分治，求得两边的δL和δR，从而求得δ。

求出分割线，扫描当前的所有点，把落到2δ带状区域内的点找出来，并使这些点的y坐标仍然保持从小到大的次序。

对落到2δ带状区域内的每一个点检查其后面的7个点，若有距离更近的点对，则把最小距离δ（及最近点对（p,q））更新，执行完毕时，最小距离δ及最近点对（p,q）就得到了。

子程序FCPP（j,k,X,Ypres,INDpres,δ,p,q）中的参数说明：

X数组存放已排好序的n个点的x坐标。

j,k为当前处理的X数组一段中的最小和最大下标。

Ypres数组存放当前处理的k-j+1个点的y坐标（已按从小到大的次序排好）。

INDpres数组的长度也是k-j+1，INDpres[i]记录了其y坐标值为Ypres[i]的点的x坐标在X数组中的下标值。

δ,p,q均为返回值，给出当前处理的k-j+1个点中的最小距离δ和最近点对（p,q）。

算法中的几个关键点：

分割线的寻找和最小距离相关的比较次数的判定

算法可以优化：

比如对p点之后的7个点检查时未考虑两点均属同一侧的情况可以考虑减小比较次数。

做DFT时，是否总假定有n=2m？

是个，总有n=2m

什么是快速傅立叶变换（FFT）？

如何用FFT来计算2个多项式的乘积？

答:

能在Θ（nlogn）时间里完成DFT的算法就称为FFT.

给了2个多项式的系数向量a和b之后，若其系数不是2的幂次，则将a和b的规模扩大（向量最后加若干个0）使得n=2m..然后把这两个向量维数再扩大一倍，得到两个维数为2n的向量。

分别对2个向量做DFT，所得到两个向量进行点乘，再对结果做2n阶的DFT-1,即可求得2多项式相乘后的多项式系数c

什么是平衡？

分治法与平衡有着什么样的关系？

在使用分治法和递归时，要尽量把问题分成规模相等，或至少是规模相近的子问题，这样才能提高算法的效率。

使子问题规模尽量接近的做法，就是所谓的平衡。

分治法与动态规划法之间的相同点是什么？

不同之处在哪些方面？

与分治法类似，动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。

动态规划法与分治法的一个重要的不同点在于，用分治法分解后得到的子问题通常都是相互独立的，而用动态规划法分解后得到的子问题很多都是重复的。

因此，对重复出现的子问题，只是在第一次遇到时才进行计算，然后把计算所得的结果保存起来；

当再次遇到该子问题时，就直接引用已保存的结果，而不再重新求解。

简述求矩阵连乘最少乘法次数的动态规划算法（不超过300字）

按照做最后一次乘法的位置进行划分，

该矩阵连乘一共可分为j-i种情况即有（j-i）种断开方式：

Mi（Mi+1┅Mj），（MiMi+1）（Mi+2┅Mj），┅，（MiMi+1┅Mj-1）Mj。

其中任一对括号内的矩阵个数（即规模）不超过j-i。

由于在此之前我们已知任一个规模不超过j-i的矩阵连乘所需的最少乘法次数，故（Mi┅Mk）和（Mk+1┅Mj）所需的最少乘法次数已知，将它们分别记之为mik和mk+1,j。

于是，形为（Mi⋯Mk）（Mk+1⋯Mj）的矩阵连乘所需的最少乘法次数为：

mik+mk+1,j+ri-1×

rk×

rj。

此式中的所有参加运算的数均已知，故此式在O

（1）时间里即可完成计算。

对满足i≤k<

j的共j-i种情况逐一进行比较，我们就可以得到矩阵连乘MiMi+1┅Mj-1Mj（i<

j）所需的最少乘法次数mij为：

mij=min（i≤k<

j）{mik+mk+1,j+ri-1×

rj}，（*）其计算可在O（j-i）时间里完成。

于是在初始时我们定义mii=0（相当于单个矩阵的情况），然后首先求出计算M1M2,M2M3,┅,Mn-1Mn所需的乘法次数mi,i+1（i=1,2,┅,n-1）,具体数值为ri-1×

ri×

ri+1,因mii=mi+1,i+1=0；

再利用这些结果和（*）式，就可以求出计算M1M2M3,M2M3M4,┅,Mn-2Mn-1Mn所需的最少乘法次数mi,i+2（i=1,2,┅,n-2）。

同理，可依次算出mi,i+3（i=1,2,┅,n-3），mi,i+4（i=1,2,┅,n-4），┅，直至算出m1,n即M1M2┅Mn-1Mn矩阵连乘所需的最少乘法次数。

能够用动态规划法求解的问题通常具有什么样的特征？

若一个问题可以分解为若干个高度重复的子问题，且问题也具有最优子结构性质，就可以用动态规划法求解：

以递推的方式逐层计算最优值并记录必要的信息，最后根据记录的信息构造最优解。

什么是最长公共子序列问题？

在求LCS的算法中，C[i,j]是如何计算的？

为什么需要这样计算？

若Z<

X，Z<

Y，且不存在比Z更长的X和Y的公共子序列，

则称Z是X和Y的最长公共子序列，记为Z∈LCS（X,Y）。

如何在低于指数级的时间复杂度内找到LCS称为最长公共子序列问题

C[i,j]=0,若i=0或j=0

C[I,j]=C[i-1,j-1]+1若i,j>

0且xi=yi

C[I,j]=max{C[i-1,j],C[i,j-1]}若i,j>

0且xi!

=yi

二维数组C，用C[i,j]记录Xi与Yj的LCS的长度如果我们是自底向上进行递推计算，那么在计算C[i,j]之前，C[i-1,j-1],C[i-1,j]与C[i,j-1]均已计算出来。

此时我们根据X[i]=Y[j]还是X[i]≠Y[j]，就可以计算出C[i,j]。

计算的理由：

求LCS（Xm-1，Y）的长度与LCS（X，Yn-1）的长度这两个问题不是相互独立的：

∵两者都要求LCS（Xm-1，Yn-1）的长度,因而具有重叠性。

另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。

用200～300字概述求最优二分搜索树算法的主要步骤。

算法中有哪几点最为关键？

记cij是最优子树Tij的耗费，则ci,k-1是最优子树Ti,k-1的耗费，ck,j是最优子树Tk,j的耗费。

考察以ak（i+1≤k≤j）为根、由结点bi，ai+1，bi+1，⋯，aj，bj构成的、耗费最小的树的总耗费：

该树的左子树必然是Ti,k-1，右子树必然是Tk,j。

这棵树的总耗费可分为三部分：

左子树、右子树和根。

由于Ti,k-1作为左子树接到结点ak之下时，其耗费增加wi,k-1，故左子树的耗费为：

ci,k-1+wi,k-1，同理，右子树的耗费为：

ck,j+wk,j，由于根ak的深度为0，按定义，根的耗费为pk。

因此，以ak为根、耗费最小的树的总耗费为：

ci,k-1+wi,k-1+ckj+wk,j+pk。

注意到，wi,k-1=qi+pi+1+qi+1+⋯+pk-1+qk-1，wk,j=qk+pk+1+qk+1+⋯+pj+qj，从而有wi,k-1+wkj+pk=qi+pi+1+qi+1+⋯+pk-1+qk-1+pk+qk+pk+1+qk+1+⋯+pj+qj=wij。

由此得到以ak为根、耗费最小的树的总耗费为：

ci,k-1+ckj+wi,j

由于pi（i=1,2,⋯,n）,qj（j=0,1,2,⋯,n）在初始时已经知道，若wi,j-1已知，则根据wi,j=wi,j-1+pj+qj可以计算出wij。

故当ci,k-1与ckj已知时，以ak为根的树的最小总耗费在O

（1）时间就可以计算出来。

分别计算以ai+1，ai+2，⋯，aj为根、含有结点bi，ai+1，bi+1，⋯，aj，bj的树的最小总耗费，从中选出耗费最小的树，此即最优子树Tij。

因此，最优子树Tij的耗费cij={cminjki≤<

jki≤<

i,k-1+ckj+wij}。

递推求cij及记录Tij的根的算法

本算法的关键点：

分析出最优二分搜索树具有最优子结构；

在计算中规模较小的最优子树在计算中要被多次用到。

Cij和Wij都是可以通过前面的计算递推得出的。

有了Tij的根的序号后，如何构造出最优二分搜索树？

设Tij的根为ak（rij记录到的值是k），则从根开始建结点。

Build-tree（i,j,r,A）/*建立最优子树Tij*/

{Ifi≥jreturn"

nill"

;

pointer←newnode（nodetype）;

k←rij;

/*必有i<

m≤j*/

pointer→value←A[k];

/*A[k]即ak*/

pointer→leftson←Buildtree（i,k-1,r,A）;

/*建立最优左子树Ti,k-1*/

pointer→rightson←Buildertree（k,j,r,A）;

/*建立最优右子树Tk,j*/

returnpointer;

}

FrancisYao的办法为什么会把算法时间复杂度从O（n3）降到O（n2）？

Th:

如果最小耗费树Ti,j-1和Ti+1,j的根分别为ap和aq，则必有

⑴p≤q⑵最小耗费树Tij的根ak满足p≤k≤q。

（证明略。

有了上述定理，我们无需在ai+1～aj之间去一一尝试，使得找到的ak为根时，{ci,k-1+ckj+wij}为最小，而只要从ap～aq之间去找一个根即可。

算法时间复杂度为Θ（n2）的证明：

首先注意Ti,j-1和Ti+1,j的规模恰好比Ti,j小1。

由于算法是按树中结点的个数（即规模）从小到大计算的，故在计算rij时，ri,j-1（即定理中的p）和ri+1,j（即定理中的q）

都已经计算出来了。

一般地，设含有k个连续结点的最优二分搜索子树的根

r0k，r1（k+1），⋯，r（n-k）,n已经计算出来。

由Th知，含有k+1个连续结点的最优二分搜索子树Ti,i+k+1的根必在ri,i+k与ri+1,i+k+1之间。

故r0,k+1在r0,k与r1,k+1之间,求出r0,k+1的搜索区间长度为r1,k+1-r0,k；

r1,k+2在r1,k+1与r2,k+2之间，求出r1,k+2的搜索区间长度r2,k+2-r1,k+1；

r2,k+3在r2,k+2与r3,k+3之间，求出r2,k+3的搜索区间长度r3,k+3-r2,k+2；

⋯⋯r（n-k-1）,n在r（n-k-1）,n-1与r（n-k）,n之间，

求出r（n-k-1）,n的搜索区间长度为r（n-k）