《数据结构线性表答案》由会员分享，可在线阅读，更多相关《数据结构线性表答案（30页珍藏版）》请在金锄头文库上搜索。
1、第一章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个 元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表 中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个 结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要 是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操 作进行统一处理。2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与 元素在表中的位置有关。(2) 顺序表中逻辑上相邻的元素的物理位置 必定紧邻。单链表中 逻辑上相邻的元素的物理位置 不一定紧邻。(3) 在单链表中，除了
2、首元结点外，任一结点的存储位置由 其前 驱结点的链域的值指示。(4) 在单链表中设置头结点的作用是 插入和删除首元结点时不 用进行特殊处理。2.3在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺 序表比用链表好，其特点是可以进行随机存取。2.4对以下单链表分别执行下列各程序段，并画岀结果示意图解:(1)pPQRS2.5画岀执行下列各行语句后各指针及链表的示意图L=(LinkList)malloc(sizeof(LNode); P=L;for(i=1;inext=(LinkList)malloc(sizeof(LNode);P=P-next; P-data=
3、i*2-1;P-next=NULL;for(i=4;i=1;i-) lns_LinkList(L,i+1,i*2);for(i=1;inext=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;(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.(1)b. (7) (11) (8) (4) (1)c
4、. (5) (12)d. (9) (1) (6)2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a. 删除P结点的直接后继结点的语句序列是 。b. 删除P结点的直接前驱结点的语句序列是 。c. 删除P结点的语句序列是。d. 删除首元结点的语句序列是。 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(Q-next!=NULL) P=Q; Q=Q-next; (7) while
5、(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)(14)c. (10) (12)(14)d. (12) (11) (3) (14)e. (9) (11)(14)2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列a. 在P结点后插入 S结点的语句序
6、列是 。b. 在P结点前插入 S结点的语句序列是 。c. 删除P结点的直接后继结点的语句序列是 。d. 删除P结点的直接前驱结点的语句序列是 。e. 删除P结点的语句序列是 。(1) P-next=P-next-next;(2) P_priou=P_priou_priou;(3) P-next=S;(4) P-priou=S;(5) S-next=P;(6) S-priou=P;(7) S-next=P-next;(8) S_priou=P_priou;(9) P-priou-next=P-next;(10) P-priou-next=P;(11) P-next-priou=P;(12) P-
7、next-priou=S;(13) P-priou-next=S;(14) P-next-priou=P-priou;(15) Q=P-next;(16) Q=P-priou;(17) free(P);(18) free(Q);解：a. (7)(12)b. (8)(5) (13)c. (15) (1) (11) (18)d. (16) (2) (10) (18)e. (14) (9) (17)2.9简述以下算法的功能。(1) Status A(LinkedList L) L是无表头结点的单链表if(L & L-next) Q=L; L=L-next; P=L;while(P-next) P=P
8、-next;P-next=Q; Q-next=NULL;return OK;(2) void BB(LNode *s, LNode *q) p=s;while(p-next!=q) p=p-next;p-next =s;void AA(LNode *pa, LNode *pb) /pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);解：(1)如果L的长度不小于2，将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。Status DeleteK(SqList & a,int i,
9、int k)/本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(iv1|kaength) return INFEASIBLE;/参数不合法else for(count=1;count=i+1;j-) a.elemj-i=a.elemj;a.length-;return OK;解：Status DeleteK(SqList & a,int i,int k)/从顺序存储结构的线性表a中删除第i个元素起的k个元素/ 注意i的编号从0开始int j;if(ivO|ia.length-1|ka.length-i) return INFEASIBLE;for(j=0;jv=k;j+)a.el
10、emj+i=a.elem|j+i+k;a.l ength=a .l ength-k;return OK;2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解：Status InsertOrderList(SqList &va,ElemType x) / 在非递减的顺序表va中插入元素x并使其 仍成为顺序表的算法int i;if(va.le ngth=va.listsize)return(OVERFLOW);for(i=vaen gth;i0,xB.length?A.length:B.length;for(i=0;iB.elemi) j=1;
11、if(A.elemik) j=1;if(B.lengthk) j=-1;if(A.length=B.length) j=0;return j;2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);解：int LocateElem_L(LinkList & L,ElemType x)int i=0;LinkList p=L;while(p&p-data!=x)p=p-next;i+;if(!p) return 0;else return i;2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。解：/返回单链表的长度int ListLength_L
12、(LinkList &L)int i=0;LinkList p=L;if(p) p=p-next;while(p)p=p-next;i+;return i;2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解：void MergeList_L(LinkList &ha, LinkList & hb, LinkList & hc)LinkList pa,pb;pa=ha;pb=hb;while(pa-next&pb-next)pa=pa_next;pb=pb-next;if(!pa
