《review points参考答案.docx》由会员分享，可在线阅读，更多相关《review points参考答案.docx（10页珍藏版）》请在金锄头文库上搜索。
1、1、什么是基本运算？ 什么是算法的时间复杂性（度）？什么是算法的渐近时间复杂性？答：基本运算是解决问题时占支配地位的运算（一般1种，偶尔两种） 算法的时间复杂性（度）是指用输入规模的某个函数来表示算法的基本运算量。算法的渐进时间复杂性是指当输入规模趋向于极限情形时（相当大）的时间复杂性。2、表示渐进时间复杂性的三个记号的具体定义是什么？答：（1）. T(n)= O(f(n)：若存在c 0，和正整数n01，使得当nn0时， 总有 T(n)c*f(n)。 （给出了算法时间复杂度的上界，不可能比c*f(n)更大） （2）. T(n)=(f(n)：若存在c 0，和正整数n01，使得当nn0时， 存在无
2、穷多个n ，使得T(n)c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小） （3）.T(n)= (f(n)：若存在c1,c20，和正整数n01，使得当nn0时， 总有 T(n)c1*f(n)， 且有无穷多个n，使得T(n)c2*f(n)成立， 即：T(n)= O(f(n)与T(n)=(f(n)都成立。（既给出了算法时间复杂度的上界，也给出了下界）3、什么是最坏情况时间复杂性？什么是平均情况时间复杂性？答：最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。 平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 （一般均假设每种输
3、入情况以等概率出现）。4、一般认为什么是算法？什么是计算过程？算法研究有哪几个主要步骤？主要从哪几个方面评价算法？答：一般认为，算法是由若干条指令组成的有穷序列，有五个特性a.确定性（无二义）b.能行性（每条指令能够执行）c.输入 d.输出 e.有穷性（每条指令执行的次数有穷）只满足前4条而不满足第5条的有穷指令序列通常称之为计算过程。算法研究的主要步骤是1)设计2）表示 3）确认，合法输入和不合法输入的处理 4）分析 5）测试。评价算法的标准有1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性。5、关于多项式时间与指数时间有什么样的结论？答：1. 多项式时间的算法互相之间虽有差距，一
4、般可以接受。 2. 指数量级时间的算法对于较大的n无实用价值。6、什么是常系数线性递归方程(差分方程)？c0an+c1an-1+cran-r=f(n) (*) (这里c0*cr0) ，所有ai都是一次的。7、主定理的内容是什么？根据主定理的结论，可以获得哪些关于算法改进的启示？答：T(n)=a*T(n/b)+f(n)若有 0, 使f(n)=O( ) (即f(n)的量级多项式地小于 的量级), 则T(n)= Q ( )。若f(n)= Q( ) (即f(n)的量级等于 的量级), 则T(n) =Q( )。若f(n)= Q( ), 则T(n)=Q( )。若有0, 使f(n)=W( ) (即f(n)的
5、量级多项式地大于 的量级), 且满足正规性条件： 存在常数c2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元进行比较，就可得n个元素的最小元。10、叙述Strassen矩阵相乘算法的主要思路和意义。答：把矩阵A，B分成4个规模为n/2的子矩阵块如下。由于 = ，所以，C11=A11B11+A12B21，C12= A11B12+ A12B22，C21=A21B11+A22B21，C22= A21B12+ A22B22。同时引入下列Mi(i=1,2.7)
6、 M1=(A12-A22) (B21+B22)，M2=(A11+A22) (B11+B12)M3=(A11-A21) (B11+B12)，M4=(A11+A12) B22，M5=A11(B12-B22)，M6=A22(B21-B11)M7=(A21+A22)B11 则计算两个n阶矩阵的乘法为7对n/2阶矩阵的乘法(时间为7T(n/2), 18对n/2阶的矩阵的加减法（时间为18*(n/2)2=Q(n2)）。因此得时间复杂度的递归方程：T(n)=7T(n/2)+Q(n2),由主定理得T(n)= Q ( ). Strassen矩阵相乘算法意义在于打破了人们认为矩阵乘法的时间复杂度为Q(n3)的固有
7、看法。11.用200字概括Select（求第k小元）算法的主要思路。答：1.若S50，则采用堆排序的方法找出第k小的元素。若|S=50，则采用下述的方法。 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)。当sim时将si放入数组S3；在得到的3个集合中，S1中的数均小于m；S2中的数均等于m；S3中的数均大于m。 6. 按照k值大小，共可分成下列三种
8、情况（注意S2至少有一个元素m）： k|S1|；|S1|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|S1|+|S2|，则第k小元素必定大于m，因此在S3中。 而且此时该元素在S3中应为第k-|S1|-|S2|小的元素。 于是递归调用Selec
9、t（k-|S1|-|S2|, S3）， 就可以获得S中的第k小元素。 因小于等于m的数据元素至少有3n/10-6个12. 试用200300字概述寻找最近点对算法的主要步骤。该算法中有哪几点最为关键？答：主程序算法： 读入n个点的坐标，这n个点的x坐标和y坐标 分别放在X，Y两个数组中，然后进行预处理： 对X数组中的n个x坐标值按从小到大的次序进行排序， 排序过程中保持x坐标和y坐标的对应关系：若X与Xj对换位置，则Y与Yj也做相同的对换。 另外，若两个点的x坐标相同，则y坐标值小的排前。 X数组排好之后就固定了，以后不再改变， 以便在O(1)时间对其实现分拆。（排序时间为(n log n)）
10、将数组IND初始化为：IND=i（i=1,2,n）。 数组IND即是用来保持x坐标和y坐标的对应关系的机制， IND记录的是 其y坐标值为Y的点所对应的x坐标在X数组中的下标。 对Y数组中的n个y坐标值按从小到大的次序进行排序， 排序过程中保持y坐标和x坐标的对应关系： 若Y与Yj对换位置，则IND 与IND j也做相同的对换。 这样，当给了一个点的y坐标Y之后， 就可以在O(1)时间找到其对应的x坐标： Y与XIND 就是该点的y坐标和x坐标。调用子程序FCPP(1,n,X,Y,IND,p,q) 就可求得n个点中的最近点对(p,q)和最小距离。 子程序FCPP的主要执行过程： 首先看当前处理
11、的点数。若不超过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数组存放当
12、前处理的k-j+1个点的y坐标 （已按从小到大的次序排好）。 INDpres数组的长度也是k-j+1，INDpres记录了其y坐标值 为Ypres 的点的x坐标在X数组中的下标值。 ,p,q均为返回值， 给出当前处理的k-j+1个点中的最小距离和最近点对(p,q)。算法中的几个关键点：分割线的寻找和最小距离相关的比较次数的判定13. 什么是离散傅立叶变换（DFT）？其使用的矩阵有什么特点？答：是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效计算DFT。14. 什么是快速傅立叶变换（F
