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

绪论 习题一（第18页） 1.4 程序步：2(n+1)，因为每一层递归count 均增加2，共递归n+1层。 1.5 确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do { k=k+10*i; i++; 答： 划线语句的执行次数为 n-1 。 } while(i=n-1) 程序步：2+3(n-1)=3n-1; T(n)=O(n) (2)i=1; x=0; 分析： i k(循环次数) 2i do 1 1 21 { 2 2 22 x++; i=2*i; 2k-1 k 2k } while （in）; 设循环体共执行了k步，则2k≥n, 即 k≥log2n,故 k=(log2n( 答：划线语句的执行次数为 (log2n(。 程序步：2+3k=2+3(log2n( ; T(n)=O(log2n) (3) for(int i=1;i=n;i++) 分析：划线语句的执行次数为 for(int j=1;j=i;j++) for (int k=1;k=j;k++) x++; (4)x=n;y=0; 分析：设循环执行k次，则k2≥n ，，故 while(x=(y+1)*(y+1)) y++; k=((，所以划线语句执行了(( 次 程序步：2+2k+1=2((+3,时间复杂度： T(n)=O((() 线性表 2.1 利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。 #include iostream.h #include seqlist.h #include conio.h template class T //求LC=LA∩LB void InterSection(SeqListT LA,SeqListT LB) //求LC=LA∩LB { int m=LB.Length(),n=LA.Length( ); SeqListT LC(mn?m:n); T x; for (int i=1;i=m;i++) { LB.Find(i,x); if (!LA.Search(x)) LC.Insert(LC.Length(),x); } coutLC; } template class T //求LC=LA-LB void Difference(SeqListT LA,SeqListT LB) { int m=LA.Length(); SeqListT LC(m); T x; for (int i=1;i=m;i++) { LA.Find(i,x); if (LB.Search(x)==0) LC.Insert(LC.Length()+1,x); } coutLC; } void main() { SeqList int LA(10),LB(10); for (int i=1;i=8;i++) LA.Insert(i,i); for (i=1;i=3;i++) LB.Insert(i,i+3); InterSection(LA,LB); Difference(LA,LB); } 2.2 时间复杂度：T(n)=O(n) （1）利用类SeqList提供的其他操作实现。 template class T void SeqListT::Invert() { T x; for (int i=0;ilength-1;i++) { Find(length,x); Insert(i,x); } } 习题(2).2 在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。 template class T void SeqListT::Invert() { T e; for (int i=1;i=length/2;i++){ e=elements