第二章线性表作业

《第二章线性表作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素的结点)。2.2填空题(1)在顺序表中插入或删除一个元素，需要平均移动—元素，具体移动的元素个数与有关。(2)顺序表中逻辑上相邻的元素的物理位置—紧邻。单链表中逻辑上相邻的元素物理位置紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由—指Zjso(4)在单链表中设置头结点的作用是。2.3在什么情况下用顺序表比链表好？2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。8•在P结点后插入S结

2、点的语句序列是ob•在P结点前插入S结点的语句序列是。C・在表首插入S结点的语句序列是od•在表尾插入S结点的语句序列是o(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;(1)S->next=P->next;(2)S->next=L;(3)S->next=NULL;(4)Q=P;(5)while(P->next!=Q)P=P->next;(6)while(P->next!=NULL)P=P->next;(7)P=Q;(8)P=L;(9)L=S;(⑶L二P;2.7已知L是带

3、表头结点的非空单链表，且P结点既不是首元结点,也不是尾元结点，试从下列提供的答案中选择合适的语句序列。乩删除P结点的直接后继结点的语句序列是ob删除P结点的直接前驱结点的语句序列是oc.删除P结点的语句序列是od.删除首元结点的语句序列是oe.删除尾元结点的语句序列是o(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(1)P=P->next->next;(2)whi.le(P!=NULL)P=P->next;(3)while(Q->next匸NULL){P二Q;Q=Q->next;}

4、(4)while(P->next!=Q)P=P->next;(5)while(P->next~>next!=Q)P二P->next;(6)while(P-〉next-〉next!二NULL)P二P-〉next;(7)Q=P;(8)Q=P->next;(9)P=L;(10)L=L~>next;(11)free(Q);2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。比在P结点后插入S结点的语句序列是Ob.在P结点前插入S结点的语句序列是。c.删除P结点的直接后继结点的语句序列是。d.删除P结点的直接前驱结点的

5、语句序列是oe.删除P结点的语句序列是o(1)P->next=P->next->next;(1)P->priou=P->priou->priou;(2)P-〉next二S;(3)P->priou=S;(4)S->next=P;(5)S->priou=P;(6)S->next=P->next(7)S->priou=P->priou(8)P->priou->next=P->next(9)P->priou~>next=P(10)P->next->priou=P(11)P->next->priou=S(12)P->priou->ncxt=S(1

6、3)P->next->priou=P->priou(14)Q=P->next(15)Q=P->priou(16)free(P(17)free(Q)2.10指出以下算法中的错误和低效(即费时)之处，并将它改写为一个既正确又高效的算法。StatusDeleteK(SqListinti,intk){〃木过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(ia.length)returnINFEASIBLE;//参数不合法else{for(count=l;count

7、r(j二a.length;j〉二i+1;j一一)a.elem[j-l]二a・elem[j];a.length-一;}ReturnOK;}//DeleteK思考题（可不做）2.11设顺序表眩中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.31假设某个单项循环链表的长度大于1,且表中既无头结点也无头指针。已知S为指向链表中某个结点的指针，试编写算法在链表中删除指针S所指结点的前驱结点。