《数据结构实验指导书》习题答案

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

1、习题一绪论1、数据的逻辑结构、数据的物理存储结构、数据的操作(或运算)及其实现。2、非线性结构3、数据元素、关系4、_A_5、(l)n2(2)n(n+l)/2(3)n*m6^(1)0(Vn)(3)O(log3n)习题二线性表1、第一个(或首元)、最后一个(或尾元)、位置(或序号)、直接前驱、直接后继2、n・i+l、nil3、A4、B5、随机存取、顺序存取6、C7、CD9、A10、B11>(1)s->next=p->next;p->next=s;(2)p->next=q->next(3)(a)s->next=L->next;L->next=s;(b)L->next==NU

2、LL(4)(a)s->next=L;L=s;(b)L==NULL12n(a)p、(b)p、(c)q->nextxq->next->p「e(d)p->pre=q->prex(e)p->pre->next>i»Di・e(f)s->pre>L・>next・>Die13>(1)p・>next=L・>next、L・>next=p(2)pa&&pb、pb=pb->next、pb(3)0、p&&jvi、p&&i=i(4)intSearch(LinkedListL){p=L->next;j=0;while(p){j++;p=p->next;}returnj;}14>intDeleteE

3、lem(inta[],intn,inti)//若删除成功,返冋1,否则返冋0{if(i>=nlli

4、j-lj=a

5、j]；//从笫i+1个元素到最后一个元素依次上移return1;15、voidSetUnion(List&La,ListLb)〃求La=LaULb{La_Len=ListLength(La);Lb_Len=ListLength(Lb);for(i=1;i<=Lb_Len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))//??e不在La中ListInsert(La,+

6、+La_Len,e)〃在La尾端插入evoidSetJiao(List&La,ListLb)//求La=LaGLb{La_Len=ListLength(La);i=l；while(i<=La_len){GetElem(La,i,e);if(!LocateElem(Lb,e))//若e不在Lb中{ListDelete(La,i,e);La_Len-・；}elsei++；习题三栈与队列1、后进先出(LIFO)表(或先进后出(FILO)表)、先进先出(FIFO)表(或后进后出(LILO)表)2、C3、C4、C5>B6、B7、C8、A9、(1)S.Tod==1、S.Elem[+

7、+S.ToD]二e：、e=S・Elem[S・Top・-l;(2)S・Top==0、S・Elem[S・Top++]=e;、e二S・Elem[—S.Top];10、对一带头结点的单链表实现逆置11、Max、S.TopO+l==S.Topl、S.Elem[—S.Topl]=e>S.Topl==Max>S.Elem[S.Topl++]13>(Q.rear+1)%MAX==Q.frontxQ.rear==Q.front、(Q.front+1)%MAX14>Q.front->next=NULL(或Q.rear->next=NULL)Q・rea「>next=p、Q.rear=p(或Q

8、・iea「=Q・iear・>next)、Q.front==Q.rear(或Q.f『ont->next==NULL)、Q.rear=Q.front15>Q、Q=q、Q==Q->nextsQ=Q->next习题四树与二叉树1>n・l、(n+l)/2、2d-l2^[Log2n」+l・5、k、2k-K2k'2k-l6、D.F7、B[j/2」、2i>2i+l3、564、n^2nj+1F9、EACBDGF.10、BCJDAIHGFE11、2n-l12、二叉树如右图1所示。先序序列为：ABDEGCF层次序列为：ABCDEFG13、D14、B15>C16、C17、完整的序列为:先序序

9、列：ABCDEEGHIJK屮序序列：CBEDFA旦JK1G后序序列:CEFDBKJIHGA218、图1所示的森林转换成的二叉树如图下图(a)，图2所示的树转换成的二义树如下图(b)所示。19、所得的二叉树如图19题(“)所示，对应的森林如图19题(b)所示。F20>(1)BitreeDepth(T->lchild)>BitreeDepth(T->rchild)>dr+1(2)PreOrder(T->lchild)>PreOrder(T->rchild)>InOrder(T->lchild)>InOrder(T->rchild)PostOr