通信数据结构第一章绪论习题(3)

F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。

(1) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?, Fl, F0精确计算多少次? (2) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少? 【解答】

（1）由斐波那契数列的定义可得： 1. Fn=Fn-1+Fn-2 =2Fn-2+Fn-3 =3Fn-3+2Fn-4 =5Fn-4+3Fn-5 ?? =pF1+qF0

设Fm的执行次数为Bm(m=0、1、2、?、n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行两次，即Bn-2=2；直至F1被执行p次、F0被执行q次，即B1=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得：

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

六、程序填空题（或算法阅读题） 1．void DD ( ) {

ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9);

for ( int i=0; i<10; i++) cout<

调用该算法后，输出结果为：

【解答】1 2 3 4 5 6 7 8 9 10 七、算法设计题

1. 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。 【解答】 void Best()

{//按序输出三个整数的优化算法 int a,b,c,t;

scanf(“%d%d%d”,&a,&b,&c); if(a>b)

11

{t=a; a=b; b=t:} //a和b已正序 if(b>c)

{t=c; c=b; //c已到位

if(a>t) {b=a; a=t;} //a和b已正序 else b=t; }

printf(“%d,%d,%d\\n”,a,b,c);

//最佳2次比较，无移动；最差3次比较，7个赋值 }

2. 在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。 【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。

【解答】

int Search(ElemType A[n+1], ElemType k) {i=n;

while(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; }

当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。

在学过第 9 章 “查找”后，可优化以上算法:设“监视哨”。算法如下： int Search(ElemType A[n+1], ElemType k) {i=n; A[0]=k;

while(A[i]!=k) i--; return i; }

研究表明，当n>=1000时，算法效率提高50%。

12

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库通信数据结构第一章绪论习题(3)在线全文阅读。