《数据结构》数据结构习题答案

《《数据结构》数据结构习题答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、答：划线语句的执行次数为n-l。程序步：2+3(n-l)二3n-1;T(n)=0(n)分析：■1k(循环次数)21112122222k"1k2k(2)i=l;x=0;do{x++；i二2*i;}while(i

2、while(i<=n-l)设循环体共执行了k步，则2k^n,即k^log2n,故kH~log2nl答：划线语句的执行次数为「10也n］。程序步：2+3k=2+3「log2if

3、;T(n)=0(log2n)for(intj二1;j〈二i;j++)for(intk=l;k<=j;k++)x++;£££]=££/=丈i(i+1)_n(n+1)(/?+2)/=!j=k=/=!j=l/=!2程序步：吕ninijZZ(J+i)+j11121J=11=1J=1*=1n(n+l)(n+2)65+1)+工(/+1)+=(卄1)+也型&g2

4、/=i2n(n+2)(h+4)3zI1X1n(n+3)fh(/:+1)(h+5)(n(/:+l)(n+2)=(n+1)411=(n+l)+266时间复杂度：T(n)=O(n3)(4)x二n;y二0;while(x>=(y+1)*(y+1))y++;分析：设循环执行k次，则kGn,£>=奶，故k=rv^i所以划线语句执行了「丽1次程序步：2+2k+l=2「石］+3,时间复杂度：T(n)=O(rV^l)第二章线性表2.1利用线性表^LinearList提供的操作，涉及实现两个集合的交和差运算。#inelude

5、h>#inelude"seqlist.h"★include"conio.h〃template//求LC=LAALBvoidInterSection(SeqList&LA,SeqList&LB)//求LC二LAQLBintm=LB.Length(),n=LA.Length();SeqListLC(m

6、emplate//求LC=LA-LBvoidDifference(SeqUst&LA,SeqIJst&LB){intm=LA.Length();SeqListLC(m);Tx;for(inti=l;i<=m;i++){LA.Find(i,x);if(LB.Search(x)==0)LC.Insert(LC.Length()+1,x);}cout«LC;}voidmain(){ScqListLA(10),LB(10);for(inti二1;i〈二8;i++)LA.Insert(i,i

7、);for(i=l;i<=3;i++)LB.Insert(i,i+3);InterSection(LA,LB);Difference(LA,LB);}2.2时间复杂度：T(n)=0(n)(1)利用类SeqList提供的其他操作实现。templatevoidSeqList::Invert(){Tx;for(inti=0;i

8、复杂度。不利用类SeqList提供的操作直接实现。templatevoidSeqList::Invert()To；for(inti=l;i<=length/2;i++){o=elcmcnts[iT];elemcnts[i-l]=elements[length-i];elements[length-i]=e;}}2.4在类SeqList中增加一个成员函数，删除表中指定元素，直接实现该算法并分析时间复杂度。T(n)=O(n)tempiateboolSeqList::Delete(con

9、stT&x){for(inti=0;i