《算法分析与设计模拟试题5(DOC 22页)》由会员分享，可在线阅读，更多相关《算法分析与设计模拟试题5(DOC 22页)（27页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析复习题参考答案1什么是算法？算法必须满足的五个特性是什么？算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.必须满足的五个特性是(遵循以下五条准则)：1 有穷（限）性2 确定性3 可（能）行性4 输入（n0）5 输出（n1）2对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。事前分析求出该算法的一个时间界限函数；事后测试搜集此算法的执行时间和实际占用空间的统计资料。3证明：若f1(n)=O(g1(n)并且f2(n)= O(g2(n)，
2、那么f1(n) +f2(n)= O(maxg1(n), g2(n)证明：根据f1(n)=O(g1(n)可知，存在正常数C1，当nn0时，使得|f1(n)|C1|g1(n)|；同理，根据f2(n)= O(g2(n)可知，存在正常数C2，当nn0时，使得|f2(n)|C2|g2(n)| 当nn0时，|f1(n)+f2(n)|f1(n)|+|f2(n)|C1|g1(n)|+C2|g2(n)| C1|gk(n)|+C2|gk(n)|（C1+C2）|gk(n)|， 其中gk(n)=maxg1(n),g2(n)，k=1,2当nn0时，取C=（C1+C2），据定义命题得证。4如果f1(n)= (g1(n)并
3、且f2(n)= (g2(n)，下列说法是否正确？试说明之。（a） f1(n) +f2(n)= (g1(n)+ g2(n)（b） f1(n) +f2(n)= (ming1(n), g2(n)（c） f1(n) +f2(n)= (maxg1(n), g2(n)答：（a）和（c）均正确，（b）错误。（a）正确可以根据定义直接证得。（b）错误可举反例。例：f1(n)= 2n，f2(n)=2 n2下面证明（c）正确性.根据上题已经证明f1(n)+f2(n)= O(maxg1(n),g2(n)，下面只需证明f1(n)+f2(n)= (maxg1(n), g2(n)，即存在正常数C，使得|f1(n)+f2(
4、n)|C(maxg1(n), g2(n) 根据f1(n)= (g1(n)并且f2(n)= (g2(n) 得到，当nn0时，存在正常数C1、C2 、C3、C4C1|g1(n)|f1(n)|C3|g1(n)| C2|g2(n)|f2(n)|C4|g2(n)|不妨设maxg1(n), g2(n)= g1(n)由于|f1(n)+f2(n)|f1(n)|-|f2(n)|C1|g1(n)|-C3|g2(n)|=C|maxg1(n), g2(n)|取C|C1-C3|的正常数，由定义得f1(n)+f2(n) = (maxg1(n), g2(n)命题得证。5证明 |log2n|= O(n)证明：对于任意的正整数
5、n，|log2n|log2（n+1）|n+1|2|n|取n0=1，C=2，根据定义知命题成立。6证明 3nlog2n= O(n2)证明：对于任意的正整数n，|3nlog2n|3nlog2n|3|n2|取n0=1，C=3，根据定义知命题成立。7用数学归纳法证明：当n1时，.证明：当n=1时，n(n+1)/2=1，命题成立； 假设n=k-1时，成立;（k2） 当n=k时，=k(k+1)/2综上可知，命题成立。8在下列情况下求解递归关系式 T(n)= 当n=2k g(n)= O(1)和f(n)= O(n)； n=2k g(n)= O(1)和f(n)= O(1)。解: T(n)=T(2k)=2 T(2
6、k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) = =2kT(1)+2k-1f(2)+2k-2f(22)+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k) 当g(n)= O(1)和f(n)= O(n)时，不妨设g(n)=a，f(n)=bn，a，b为正常数。则 T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+20*2kb =2ka+kb2k =an+bnlog2n= O(nlog2n) 当g(n)= O(1)和f(n)= O(1)时，不妨设g(n)=c，
7、f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+20d=c2k+d(2k-1)=(c+d)n-d= O(n)9求解递推关系式： 解：构造生成函数求解 分解成幂级数令 则A=-1 B=1 所以10求解递推关系式：解：11求解递推关系式： 解：以为系数，构成生成函数 其中 12分治法的三个步骤是什么？给出使用SPARKS语言描述的分治策略抽象化控制。答:分治法的三个步骤是: 分解 解决 合并用SPARKS语言描述的分治策略抽象化控制为:Procedure DANDC(p,q)Global n,A(1:n);integer m,p,q;If SMALL(p,
8、q)Then return(G(p,q)Else mDIVIDE(p,q)Return(COMBINE(DANDC(p,m), DANDC(m+1,q) Endif End DANDC13根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh then mid if x=A(mid) then jmid; endifif xA(mid) then BINSRCH(A, mid+1, high, x, j); endifif xA(mid) then BINSRCH(A, lo
9、w, mid-1, x, j); endifelse j0; endifend BINSRCH14作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhigh do p1 ; p2 case :x=A(p1): jp1; return :x=A(p2): jp2; return :xA(p2): lowp2+1:el
10、se: lowp1+1; highp2-1 end caserepeatj0end ThriSearchT(n)= g(n)= O(1) f(n)= O(1)成功:O(1),O(log3(n),O(log3(n)最好，平均， 最坏失败: O(log3(n),O(log3(n),O(log3(n)最好，平均， 最坏15对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设nk(k0)时，E=I+2n成立；则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展树的定义，一定存在这样的
11、结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=Ik+2k，考察原树的外部路径长度为Ek+1= Ek-（h-1）+2h，内部路径长度为Ik+1=Ik+（h-1），所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1)，综合知命题成立。16以比较为基础（基本操作）的分类算法最坏情况的时间下界是什么？答： 17对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是什么？简要说明理由。答： 对线性存储的有序表中元素的以比较为基础的检索算法的执行过程都可以用二元判定树来描述
12、。该树的每个内结点表示一次元素比较，因此对检索的最坏情况而言，该树最少含有n个不同的内结点。检索算法最坏时间不大于该树中由根到一个叶子的最长路径长（树高）。对有n个结点的二元树其最小树高为，所以对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是。18简要说明选择问题算法中二次取中值规则的作用。答：通过选择划分元素V使其尽量靠近元素集合的中间可以得到一个最坏情况时间复杂度是O（n）的选择算法。使用二次取中值规则可以选出满足要求的划分元素V。19给出斯特拉森矩阵乘法算法执行时间的递归关系式，并对其求解计算时间复杂度。答：斯特拉森矩阵乘法算法执行时间的递归关系式为： T(n)= 其中a
13、和b是常数。求解这个递归式，得20通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。P=(A11+A22)(B11+B22) T=(A11+A12)B22Q=(A21+A22)B11 U=(A21-A11)(B11+B12)R=A11(B12-B22) V=(A12-A22)(B21+B22)S=A22(B21-B11)C11=P+S-T+V=(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21-A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22=A11B11 +A12B21C12=R+T= A11B12-A11B22 +A1
