数据结构考研分类复习真题 第一章 答案[9]

（）由斐波那契数列的定义可得

Fn=Fn+Fn

=Fn+Fn

=Fn+Fn

=Fn+Fn

=Fn+Fn

……

=pF+qF

设Fm的执行次数为Bm(m=…n)由以上等式可知Fn被执行一次即Bn=Fn被执行两次即Bn=直至F被执行p次F被执行q次即B=pB=qBm的执行次数为前两等式第一因式系数之和即Bm=Bm+Bm再有Bn=和Bn=这也是一个斐波那契数列可以解得

(m=…n)

（）时间复杂度为O(n)

．从小到大排列为logn n/+logn n nlogn n+lognn nn+n n/ (/)n n!

[] [] [] [] [] [] [] [] []