《数据结构教学资料》数据结构习题答案_太原理工大学软件学院修改

《《数据结构教学资料》数据结构习题答案_太原理工大学软件学院修改》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构习题答案第二章线性表2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a・在P结点后插入S结点的语句序列是。b・在P结点前插入S结点的语句序列是oc.在表首插入S结点的语句序列是od.在表尾插入S结点的语句序列是o(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;(4)S->next=P->next;(5)S->next=L;(6)S->next二NULL;⑺Q二P；(8)whi.1e(P->nex

2、t!=Q)P=P->next;(9)whi.le(P~>next!=NULL)P=P->next;(10)P=Q;(11)P二L;(12)L二S;(13)L二P;解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)或(9)(6)(1)2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是。b.删除P结点的直接前驱结点的语句序列是。c.删除P结点的语句序列是od.删除首元结点的语句序列是o

3、e.删除尾元结点的语句序列是o(1)P二P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(1)wh订e(P!=NULL)P=P->next;(1)whi.1e(Q->next!=NULL){P=Q;Q=Q->next;}(2)whi.1e(P~>next!=Q)P=P->next:(3)whi.le(P->next->next!=Q)P=P->next;(4)wh订e(P->next-〉next!二NULL)P=P->next;(5)Q二P;(6)Q=

4、P->next;(7)P=L;(8)L=L->next:(9)free(Q);解：a.(11)(3)(14)b.(10)(12)(8)(11)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)2.9简述以下算法的功能。(1)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L->next){Q二L;L=L->next;P=L;wh订e(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnOK

5、;}(2)voidBB(LNode*s,LNode*q){P=s;while(p->next!=q)p=p->next;p->next二s;voidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);解：(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解:StatusInsertOrderList(SqList

6、&va,ElemTypex)〃在非递减的顺序表va中插入元素x并使其仍成为有序表的算法inti;if(va.length==va.listsize)return(OVERFLOW);for(i=va・length;i>0,x

7、;P二L;if(p)p=p-next;wh订e(p){p=p->next;i卄；}returni;}算法2：intLength(LinkListL)〃求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);returnk;}//Length2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置算法1：Statusreverse(SqList&L)//顺序表的就地逆置for(i=l,j=L・length;i〈j;i++,j—){x=L.elem[i];L.elem[i]=L.elem[j

8、];L.elem[j]=x;returnOK;}//reverse算法2：StatusListOppose_Sq(SqList&L)for(i=0;i