算法复习题(2)

Fn?

n??15(?n??n)

Fn?11?5n()25

12．分治法的三个步骤是什么？给出使用SPARKS语言描述的分治策略抽象化控制。

答:分治法的三个步骤是: ① 分解 ②解决 ③合并 用SPARKS语言描述的分治策略抽象化控制为:

Procedure DANDC(p,q)

Global n,A(1:n);integer m,p,q; If SMALL(p,q)

Then return(G(p,q)) Else m←DIVIDE(p,q)

Return(COMBINE(DANDC(p,m), DANDC(m+1,q)))

Endif End DANDC

13．根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid←?(low?high)/2?

if x=A(mid) then j←mid; endif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

else j←0; endif end BINSRCH

14．作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。

Procedure ThriSearch(A, x, n, j) integer low, high, p1, p2 low←1; high←n while low≤high do

p1←?(2low?high)/3? ; p2←?(low?2high)/3? case

:x=A(p1): j←p1; return :x=A(p2): j←p2; return :xA(p2): low←p2+1

:else: low←p1+1; high←p2-1

end case

repeat j←0 end ThriSearch

?g(n)n足够小T(n)= ?

T(n/3)?f(n)否则?g(n)= O(1) f(n)= O(1)

成功:

O(1), 最好，

失败:

O(log3(n)), 最好，

15．对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。 证明：数学归纳法

①当n=1时，易知E=2，I=0，所以E=I+2n成立； ②假设n≤k(k>0)时，E=I+2n成立；

③则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展

树的定义，一定存在这样的结点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．以比较为基础（基本操作）的分类算法最坏情况的时间下界是什么？ 答： ?（nlogn）

17对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是什么？简要说明理由。 答： ?log(n?1)?

O(log3(n)), O(log3(n)) 平均，

最坏

O(log3(n)), O(log3(n)) 平均，

最坏

对线性存储的有序表中元素的以比较为基础的检索算法的执行过程都可以用二元判定树来描述。该树的每个内结点表示一次元素比较，因此对检索的最坏情况而言，该树最少含有n个不同的内结点。检索算法最坏时间不大于该树中由根到一个叶子的最长路径长（树高）。对有n个结点的二元树其最小树高为?log(n?1)?，所以对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是?log(n?1)?。

18．简要说明选择问题算法中二次取中值规则的作用。

答：通过选择划分元素V使其尽量靠近元素集合的中间可以得到一个最坏情况时间复杂度是O（n）的选择算法。使用二次取中值规则可以选出满足要求的划分元素V。

19．给出斯特拉森矩阵乘法算法执行时间的递归关系式，并对其求解计算时间复杂度。

答：斯特拉森矩阵乘法算法执行时间的递归关系式为：

?bn?2 T(n)= ? 27T(n/2)?ann?2?其中a和b是常数。

求解这个递归式，得

T(n)?7[7T(n/4)?a(n/2)2]?an2

?72T(n/4)?an2(1?7/4)

?72[7T(n/8)?a(n/4)2]?an2(1?7/4) ?7kT(1)?an2[1?7/4?(7/4)2?...?(7/4)k?1] ?7k?an2[(7/4)k?1]/(7/4?1)

?(c?1)7k ?(c?1)nlog7

?O(nlog7)

?O(n2.81)

20．通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。

P=(A11+A22)(B11+B22) T=(A11+A12)B22 Q=(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 +A12B21 C12=R+T

= A11B12-A11B22 +A11B22+A12B22 = A11B12 +A12B22 C21=Q+S

= A21B11+A22B11 +A22B21-A22B11 = A21B11 +A22B21 C22=P+R-Q+U

=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12) =A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12 -A11B11-A11B12 =A22B22+A21B12

21．过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？

最好情况：是对有序文件进行排序。

分析：在此情况下归并的次数不会发生变化----log(n)次

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法复习题(2)在线全文阅读。