数据结构习题答案汇总

《数据结构习题答案汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课后习题参考答案1.1.20（1）T(n)=n-1；渐近时间复杂度为O(n)。（2）T(n)=élog2nù；渐近时间复杂度为O(log2n)。（3）T(n)=n(n+1)(n+2)/6；渐近时间复杂度为O(n3)（4）T(n)=；渐近时间复杂度为O()2.2.3templateboolSeqList::Insert2(inti,Tx){if(i<-1

2、

3、i>n-1){cout<<"Outofbounds"<

4、Length*2;for(intj=0;j<=i;j++)elem[j]=elements[j];elem[i+1]=x;for(j=i+1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}算法的时间复杂度为O(n)2.4templateboolSeqList::Del(Tx){if(!n){cou

5、t<<"UnderFlow"<voidSingleList::Invert(){Node*p=first,*q;first=NULL;while(p){q=p->link;p->link=first;14first=p;p=q;}}算法的时间复

6、杂度为O(n)2.7templateboolSingleList::Del(constT&x){if(!n){cout<<"UnderFlow!!!"<*p=first,*q;if((first->data)==x){first=first->link;deletep;n--;returntrue;}while(p&&p->data!=x){q=p;p=p->link;}if(p){q->link=p->link;delete(p);n--;returntrue;}returnfalse;}算法的时间复杂度为O

7、(n)1.3.1答：(2)和(3)不能。对(2)中的E，B，D而言，E最先出栈则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理(3)也不能。14(1)能，操作序列:push(A),pop(),push(B),pop(),push(C),pop(),push(D),pop(),push(E),pop()(4)能，操作序列:push(A),push(B),push(C),push(D),push(E),pop(),pop(),pop(),pop(),pop()3.4(1)(a+b)/(c+d)ab+cd+/(2)b^2-4*a*cb2^4a*c*-(3)a*c-b/

8、c^2ac*-bc2^/-(4)(a+b)*c+d/(e+f)ab+c*def+/+(5)(a+b)*(c*d+e)-a*cab+cd*e+*ac*-3.13ttemplatevoidSeqStack::Invert(void){SeqQueuesq(maxTop+1);Ttemp;while(top!=-1){this->Top(temp);this->Pop();sq.EnQueue(temp);}while(!sq.IsEmpty()){sq.Front(temp);sq.DeQueue();this->Push(temp);}}1.4.2设三维数组

9、的维度分别是m,n,l；每个元素占k个存储单元。Loc(A[i][j][k])=Loc(A[0][0][0])+(i*n*l+j*l)*k4.6144.7col01234num10212k011341.5.2（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵5.4（1）2k-1（2）（3）k(i-1)+m+1（4）i+1≤5.5(1)空二叉树和所有结点均无左孩子的二叉树(2)空二叉树和只有一个根(3)空二叉树和所有结点均无右孩子5.65.7先：DE