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

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

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

2、>next=P->next;(5)S->next=L;(6)S->next=NULL;(7)Q=P;(8)while(P->next!=Q)P=P->next;(9)while(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结点的直接后继结点的

3、语句序列是____________________。b.删除P结点的直接前驱结点的语句序列是____________________。c.删除P结点的语句序列是____________________。d.删除首元结点的语句序列是____________________。e.删除尾元结点的语句序列是____________________。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(

4、Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next;(12)P=L;(13)L=L->next;(14)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)(

5、3)(14)2.9简述以下算法的功能。(1)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnOK;}(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(

6、pb,pa);}解：(1)如果L的长度不小于2，将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解：StatusInsertOrderList(SqList&va,ElemTypex){//在非递减的顺序表va中插入元素x并使其仍成为有序表的算法inti;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

7、m[i]=va.elem[i-1];va.elem[i]=x;va.length++;returnOK;}2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。算法1：//返回单链表的长度intListLength_L(LinkList&L){i=0;p=L;if(p)p=p-next;while(p){p=p->next;i++;}returni;}算法2：intLength(LinkListL)//求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);returnk;}//Length2.21

8、试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,,an)逆置为(an,,a1)算法1：Statusr