《东南大学算法设计与分析复习题》由会员分享，可在线阅读，更多相关《东南大学算法设计与分析复习题（22页珍藏版）》请在金锄头文库上搜索。
1、什么是基本运算？什么是基本运算？答：基本运算是解决问题时占支配地位的运算（一般 1 种，偶尔两种）；讨论一个算 法优劣时，只讨论基本运算的执行次数。劣时，只讨论基本运算的执行次数。什么是算法的时间复杂性（度）？什么是算法的时间复杂性（度）？答：算法的时间复杂性（度）是指用输入规模的某个函数来表示算法的基本运算量。T(n)=4n3什么是算法的渐近时间复杂性？什么是算法的渐近时间复杂性？答：当输入规模趋向于极限情形时（相当大）的时间复杂性。表示渐进时间复杂性的三个记号的具体定义是什么？表示渐进时间复杂性的三个记号的具体定义是什么？ 答：1. T(n)= O(f(n)：若存在 c 0，和正整数 n0
2、1，使得当 nn0 时， 总有 T(n)c*f(n)。 （给出了算法时间复杂度的上界，不可能比 c*f(n)更大）2. T(n)=(f(n)：若存在 c 0，和正整数 n01，使得当 nn0 时， 存在无 穷多个 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 的所有输入的算法时间复杂度的平均值 （一般 均假设每种输入情况以等概率出现）。一般认为什么是算法？什么是计算过程？一般认为什么是算法？什么是计算过程？答：一般认为，算法是由若干条指令组成的有穷序列，有五个特性 a.确定性（无二义） b.能行性（每条指令能够执行）c.输入 d.输出 e.有穷性（每条指令执行的次数有穷）只满足前 4 条而不满足第 5 条的有穷指令序列通常称
4、之为计算过程。算法研究有哪几个主要步骤？主要从哪几个方面评价算法？算法研究有哪几个主要步骤？主要从哪几个方面评价算法？答：算法研究的主要步骤是 1)设计 2）表示 3）确认，合法输入和不合法输入的处理 4）分析 5）测试评价算法的标准有 1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性关于多项式时间与指数时间有什么样的结论？关于多项式时间与指数时间有什么样的结论？答：1. 多项式时间的算法互相之间虽有差距，一般可以接受。 2. 指数量级时间的算法对于较大的 n 无实用价值。 什么是相互独立的函数序列？何时称函数项什么是相互独立的函数序列？何时称函数项 k(x)k(x)能被其它函数项线
5、性表出？能被其它函数项线性表出？答：设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) = 1i1(x) + 2i2 (x) + + pip (x) ，即任何一个函数项 k(x)不能被其它函数项线性表出。根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？答：1.若方程(*)恰有 r 个互不相同的特征根 1，2，r (即 ij 时有 ij)，
6、则齐次方程(*)的解为 anA1+ A2+ +Ar(齐通解，即齐次方程的通解) （A1Ar 为待定系数，可由 r 个连续的边界条件唯一确定） 2若 1，2 是(*)方程的一对共扼复数根 和 ， eiei.则这两个根对应 的解的部分为 Ancos(n)+Bnsin(n) (A,B 为实的待定系数)3若 是(*)方程的 k 重根，则 对应的解的部分为 C1n+ C2 nn+ C3 n2n+ +Ck nk-1n (C1Ck 为待定常数)4若(*)方程中的 f(n)0(非齐次)，且 q(n)是(*)的一个解， 则(*)方程的解为： (*)的齐通解（含有待定系数）+ q(n) （非齐特解）， （齐通解中
7、的待定系数由边界条件 唯一确定）求和中的通项与积分中的被积函数之间有什么样的关系？求和中的通项与积分中的被积函数之间有什么样的关系？答：求和中的通项的表达形式一般就是被积函数，一般用放缩的方法求得通项得上下 界。主定理的内容是什么？根据主定理的结论，可以获得哪些关于算法改进的启示？主定理的内容是什么？根据主定理的结论，可以获得哪些关于算法改进的启示？答：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) 若
8、f(n)= (), 则 T(n)=( )3) 若有 0, 使 f(n)=() +)(aLogbn(即 f(n)的量级多项式地大于的量级), 且 满足正规性条件： abLogn 存在常数 c2 时， 可以把 n 个数据元素分为大致相等的两半， 一半有n/2个数据元素，而另一半有 n/2个数据元素。 先分别找出各自组中的最大元和最小元，然后 将两个最大元进行比 较，就可得 n 个元素的最大元； 将两个最小元进行比较，就可得 n 个元素的最小元。求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下 可以达到下界？答：在规模为 n 的数据元素集合中找出最大元和最小元， 至少需要
9、3n/2-2 次比较， 即 3n/2-2 是找最大最小元算法的下界。当 n=2k,或当 n2k 时，若 n 是若干 2 的整数幂之 和，（e.g. 42=32+8+2）， 则算法的时间复杂度仍可达到 3n/2-2。如何用分治法求两个如何用分治法求两个 n n 位二进制数位二进制数 x x 和和 y 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+b
10、c)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
11、)，比 (n2)要好不少。用用 200200 字概括字概括 SelectSelect（求第（求第 k k 小元）算法的主要思路。小元）算法的主要思路。答：1.若 Sm 时将 si 放入数组 S3； 在得到的 3 个集合中，S1 中的数均小于 m； S2 中的数均等于 m；S3 中的数均大于 m。6. 按照 k 值大小，共可分成下列三种情况（注意 S2 至少有一个元素 m）： k|S1|；|S1|S1|+|S2|。 下面针对这三种情况分别进行讨论。 6.a：若 k|S1|，则第 k 小元素必定在 S1 中。 此时递归调用 Select（k,S1），就 可以获得第 k 小元素。 因大于等于 m 的
12、数据元素至少有 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|小的元素。 于是递归调用 Select（k-|S1|-|S2|, S3）， 就可 以获得 S 中的第 k 小元素。 因小于等于 m 的数据元素至少有 3n/10-6 个1 的情况下，T(n)分别为什么？1 及 p+q时间复杂度为 T(
13、n)=T(p*n)+T(q*n)+a*n 时， 在 p+q答：T(n)a*n*k=0(p+q)k矩阵相乘算法目前最好的时间复杂度是多少？矩阵相乘算法目前最好的时间复杂度是多少？答：目前矩阵乘法最好的时间复杂度是能做到 O（n2.376）叙述叙述 StrassenStrassen 矩阵相乘算法的主要思路和意义。矩阵相乘算法的主要思路和意义。答：把矩阵 A，B 分成 4 个规模为 n/2 的子矩阵快C11=A11B11+A12B21, C12=A11B12+A12C21=A21B11+A22B21, C22=A21B12+A22B22同时引入下列 Mi(i=1,2.7)则计算两个 n 阶矩阵的乘法
14、为 7 对 n/2 阶矩阵的乘法(时间为 7T(n/2),以及 18 对 n/2 阶矩阵的加减法则递归方程为 T(n)=7T(n/2)+ (n2),由主定理得 T(n)= (n2.81). Strassen 矩阵相乘算法意义在于打破了人们认为矩阵乘法得时间复杂度为 （n3）得固定 看法。试用试用 200200300300 字概述寻找最近点对算法的主要步骤。该算法中有哪几点最为关键？字概述寻找最近点对算法的主要步骤。该算法中有哪几点最为关键？ 该算法是否可改进？该算法是否可改进？答：主程序算法： 读入 n 个点的坐标，这 n 个点的 x 坐标和 y 坐标 分别放在 X，Y 两个数组中，然后进 行
15、预处理： 对 X 数组中的 n 个 x 坐标值按从小到大的次序进行排序， 排序过程中保持 x 坐标和 y 坐标的对应关系：若 Xi与 Xj对换位置，则 Yi与 Yj也做相同的对换。 另外，若两个点的 x 坐 标相同，则 y 坐标值小的排前。 X 数组排好之后就固定了，以后不再改变， 以便在 O(1) 时间对其实现分拆。（排序时间为 (n log n)） 将数组 IND 初始化为：INDi =i（i=1,2,n）。 数组 IND 即是用来保持 x 坐标和 y 坐标的对应关系的机制， INDi 记录的是 其 y 坐标值为 Yi的点所对应的 x 坐标在 X 数组中的下标。 对 Y 数组中的 n 个
16、y 坐标值按从小到大的次序进行排序， 排序过程中保持 y 坐标和 x 坐标的对应关系： 若 Yi与 Yj对换位置，则 IND i与 IND j也做相同的对换。 这样，当给了一个点的 y 坐标 Yi之后， 就可以在 O(1)时间找到其对应的 x 坐标： Yi与 XIND i就是该点 的 y 坐标和 x 坐标。调用子程序 FCPP(1,n,X,Y,IND,p,q) 就可求得 n 个点中的最近点对(p,q)和最小距 离 。 子程序 FCPP 的主要执行过程： 首先看当前处理的点数。若不超过 3 个点，就直 接进行相互比较。 若超过 3 个点，则把点的 y 坐标分为两部分：左边和右边。然后进行分治，求
