算法分析与设计模拟试题5

《算法分析与设计模拟试题5》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》复习题1.什么是算法？算法必须满足的五个特性是什么？算法：一组有穷的规则，规定了解决某一特定类型问题的一須蠶。（有限指令的集合，遵循它可以完成一个特定的任务）.必须满足的五个特性是（遵循以下五条准则）：1.有穷（限）性2.确定性3.可（能）行性4.输入（n>0）5.输出（nn1）2.对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么缙）？对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。事前分析求出该算法的一个时间界限数；事后测试搜集此算法的执行时间和实3.证明：若f«n)=0©(n))并且f2(n)=O(g2(n))

2、,男陆f«n)+f2(n)=O(max{gi(n),g2(n)}证明：根据fi(n)=O(gi(n))可知,存在正常数Ci,当心n。时,使W

3、fi(n)

4、

5、gi(n)

6、；同理，根据f2(n)=O(g2(n))可知，存在正常数C2,当2n。时，ft#

7、f2(n)

8、

9、g2(n)

10、当nnno时，

11、fi(n)+f2(n)

12、<

13、fi(n)

14、+

15、f2(n)

16、

17、gi(n)

18、+C2

19、g2(n)

20、

21、gk(n)

22、+C2

23、gk(n)

24、s(C1+C2)

25、gk(n)

26、,其中gk(n)=max{gi(n),g2(n)},k={1,2}当nnno时，無(C1+C2),据

27、定义命题得证。4.如果fi(n)=O(gi(n))并且f2(n)=O(g2(n)),下列说法是否正确？试说明之(a)fi(n)+f2(n)=O(gi(n)+g2(n))(b)fi(n)+f2(n)=O(min{gi(n),g2(n)})(c)fi(n)+f2(n)=0(max{gi(n),g2(n)})答：(a)和(c)均正确，(b)错误。(a)正确可以根据定义直接证得。2(b)错误可举反例例：f"n)=2n,f2(n)=2n下面证明(c)正确性.根据上题已養明fi(n)+f2(n)=O(max{gi(n),g2(n)}),下面只需证明fi(n)+f2(n)=Q(

28、max{gi(n),g2(n)}),即存在正常数C,使得

29、fi(n)+f2(n)

30、>C(max{gi(n),g2(n)})根据fi(n)=O(gi(n))并且f2(n)=O(g2(n))得到，当nnn。时，存在正常数G、Q、CkGG

31、gi(n)

32、<

33、fi(n)

34、

35、gi(n)

36、C2

37、g2(n)

38、<

39、f2(n)

40、

41、g2(n)

42、不妨rcfex{gi(n),g2(n)}=gi(n)由于

43、fi(n)+f2(n)

44、>

45、

46、fi(n)

47、-

48、f2(n)

49、

50、>

51、G

52、g“(n)卜C3

53、g2(n)

54、

55、=C

56、max{gi(n),g2(n)}

57、取Ql^-Cal的正常数，由定义得fi

58、(n)+f2(n)=Q(max{gi(n),g2(n)})命题得证。1.证明

59、rlog2n」

60、=0(n)证明：对于任意的正数n,

61、rlog2n」

62、s

63、log2(n+1)

64、<

65、n+1

66、<2

67、n

68、取n0=1,C=2,根据定义知命题成立。6.证明3nrlog2口」二0(n2)证明：对于任意的正鑿n,

69、3nriog2nj

70、<

71、3nrlog2n」3

72、n2I取C=3,根据定义知命题成立。7・用数学归纳法证明：当21时，乙=n(n+1)/2.§证明：当时，=1,n(n+1)/2=1,命题成立;假谁时，ZE=亍n(n■=1+1)/2成立；(k>2)n当n=k吋，n(nn1)/2=

73、k(k1)/2k=k(k+1)/2ir1综上可知，命题成立b在下列情况下求解递归关案T(n)=g(n)2T(n/2)g(n)=0(1)和f(n)=g(n)=0(1)和f(n)=f(n)0(n)；0(1)on足够小否则k勺+f(2k-1))+f(2k)k)二2T(2k-1)+f(2沪2(2T(2解：T(n)二T(2=2订⑵勺+2仃(2k・i)+f(2k)=2订⑴+2吋(2)+2商(22)+・・・+2叫29=2kg(n)+2八仃(2)+2喇(22)+・・・+2叫2k)①当g(n)=0(1)和f(n)=0(n)时，不妨吸n)=a,f(n)=bn,a,b为正常数。贝ijk

74、)=2ka+2k1*2b+2k-2*22b+■■-+2°*2kb=2ka+kb2kT(n)=T(2二an+bnlogzn二O(nlog2n)②当g(n)=0(1)和f(n)=0(1)吋,不妨^n)=c,f(n)=d,c,d为正吊数则k)=c2k+2k「d+2k・2d+…+2°d=c2k+d(2k-1)T(n)=T(2=(c+d)n-d=0(n)=19・求解递推关系式:h(1)=2h(n-1)+1h(n)构造生成函数=+H(x)h(1)xh(2)O0=()xkhkk+求解H(x)日(X)_2xH(x)+2——2hg…一=+(12x)H(x)-x—+.H(x)-X-=

75、('2x0