第二部分习题习题一绪论1、数据的逻辑结构、数据的物理存储结构、数据的操作（或运算）及其实现。2、非线性结构3、数据元素、关系4、A5、(1)n2(2)n(n+1)/2(3)n*m6、（1）O()（3）O(log3n)习题二线性表1、第一个（或首元）、最后一个（或尾元）、位置（或序号）、直接前驱、直接后继2、n-i+1、n-i3、A4、B5、随机存取、顺序存取6、C7、C8、D9、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==NULL（4）(a)s->next=L;L=s;(b)L==NULL12、（a）p、p->next->pre（b）p、p->pre->next（c）q->next、q->next->pre（d）p->pre=q->pre、q->pre->next（e）p->pre->next、p->pre（f）s->pre、L->next->pre13、(1)p->next=L->next、L->next=p(2)pa&&pb、pb=pb->next、pb(3)0、p&&j<i、p&&j==i(4)intSearch(LinkedListL){p=L->next;j=0;while(p){j++;p=p->next;}returnj;}14、intDeleteElem(inta[],intn,inti)//若删除成功，返回1，否则返回0{if(i>=n||i<1)return0;for(j=i;j<n;j++)a[j-1]=a[j];//从第i+1个元素到最后一个元素依次上移return1;}15、voidSetUnion(List&La,ListLb)//求La=La∪Lb{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,++La_Len,e)//在La尾端插入e}}voidSetJiao(List&La,ListLb)//求La=La∩Lb{La_Len=ListLength(La);i=1;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.Top==-1、S.Elem[++S.Top]=e;、e=S.Elem[S.Top--];(2)S.Top==0、S.Elem[S.Top++]=e;、e=S.Elem[--S.Top];10、对一带头结点的单链表实现逆置11、Max、S.Top0+1==S.Top1、S.Elem[--S.Top1]=e、S.Top1==Max、S.Elem[S.Top1++]13、(Q.rear+1)%MAX==Q.front、Q.rear==Q.front、(Q.front+1)%MAX14、Q.front->next=NULL(或Q.rear->next=NULL)、Q.rear->next=p、Q.rear=p(或Q.rear=Q.rear->next)、Q.front==Q.rear(或Q.front->next==NULL)、Q.rear=Q.front15、Q、Q=q、Q==Q->next、Q=Q->next习题四树与二叉树1、n-1、(n+1)/2、2d-12、Log2n+1、i/2、2i、2i+13、564、n、Log2n+15、k、2k-1、2k-1、2k-16、D、F7、B8、I、F9、EACBDGF、2ABCDE12题FG10、BCJDAIHGFE11、2n-112、二叉树如右图1所示。先序序列为：ABDEGCF层次序列为：ABCDEFG13、D14、B15、C16、C17、完整的序列为：先序序列：ABCDEFGHIJK中序序列：CBEDFAHJKIG后序序列：CEFDBKJIHGAABCDE18题（b)GH18、图1所示的森林转换成的二叉树如图下图（a)，图2所示的树转换成的二叉树如下图（b）所示。ABCDFGHI