《《數(shù)據(jù)結(jié)構(gòu)》數(shù)據(jù)結(jié)構(gòu)習(xí)題答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、答：劃線語(yǔ)句的執(zhí)行次數(shù)為n-l。程序步：2+3(n-l)二3n-1;T(n)=0(n)分析：■1k(循環(huán)次數(shù))21112122222k"1k2k(2)i=l;x=0;do{x++；i二2*i;}while(i

2、while(i<=n-l)設(shè)循環(huán)體共執(zhí)行了k步，則2k^n,即k^log2n,故kH~log2nl答：劃線語(yǔ)句的執(zhí)行次數(shù)為「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時(shí)間復(fù)雜度：T(n)=O(n3)(4)x二n;y二0;while(x>=(y+1)*(y+1))y++;分析：設(shè)循環(huán)執(zhí)行k次，則kGn,￡>=奶，故k=rv^i所以劃線語(yǔ)句執(zhí)行了「麗1次程序步：2+2k+l=2「石］+3,時(shí)間復(fù)雜度：T(n)=O(rV^l)第二章線性表2.1利用線性表^LinearList提供的操作，涉及實(shí)現(xiàn)兩個(gè)集合的交和差運(yùn)算。#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時(shí)間復(fù)雜度：T(n)=0(n)(1)利用類SeqList提供的其他操作實(shí)現(xiàn)。templatevoidSeqList::Invert(){Tx;for(inti=0;i

8、復(fù)雜度。不利用類SeqList提供的操作直接實(shí)現(xiàn)。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中增加一個(gè)成員函數(shù)，刪除表中指定元素，直接實(shí)現(xiàn)該算法并分析時(shí)間復(fù)雜度。T(n)=O(n)tempiateboolSeqList::Delete(con

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