[理学]数据结构 习题 第二章 线性表 答案.doc

《[理学]数据结构 习题 第二章 线性表 答案.doc》由会员分享，可在线阅读，更多相关《[理学]数据结构 习题 第二章 线性表 答案.doc（35页珍藏版）》请在三一办公上搜索。

1、第2章 线性表一选择题 1.A2.B3.C4.A5.D6.D7.D8.C9.B10.B,C11.1I11.2I11.3E11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B22.D23.C24.B25.B26.A27.D二判断题1. 2.3. 4.5.6. 7. 8.9.10.11.12.13. 14. 15.16. 部分答案解释如下。1、 头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。4两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。7集合中元素无逻辑关系。9非空线性表第一个元素无前驱

2、，最后一个元素无后继。13线性表是逻辑结构，可以顺序存储，也可链式存储。三填空题1顺序 2（n-1）/2 3py-next=px-next; px-next=py4 n-i+15主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。6O(1)，O(n) 7单链表，多重链表，（动态）链表，静态链表8f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;9p.prior s.prior.next10 指针 11物理上相邻 指针 124 213从任一结点出发都可访问到链表中每一个元素。

3、14u=p-next; p-next=u-next; free(u); 15L-next-next=L 16p-next!=null17L-next=L & L-prior=L 18s-next=p-next;p-next=s;19(1) IF pa=NIL THEN return(true);(2) pbNIL AND pa.data=pb.data(3) return(inclusion(pa,pb);(4) pb:=pb.next;(5) return(false);非递归算法：(1)pre:=pb; (2) paNIL AND pbNIL AND pb.data=pa.data (3)

4、pa:=pa.next; pb:=pb-next;(4)pb:=pre.next;pre:=pb;pa:=pa.next;(5)IF pa=NIL THEN return(true) ELSE return(false);注：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。20AVAR head:pt

5、r B. new(p) C. p.data:=k D. q.next:=p E. q:=p(带头结点)21（1）new(h);生成头结点，以便于操作。 （2）r.next:=p; (3) r.next:=q; (4) IF (q=NIL) THEN r.next:=p;22A: r.link.datamax AND q.link.datamaxB: r:=r.link C: q.link D: q.link E: r.link F: r.linkG: r:=s（或r:= r.link） H: r:=r.link I: q.link:=s.link 23(1)la (2)0 (3)ji-1 (4

6、)p.next (5)i1 24.(1)head.left:=s head的前驱指针指向插入结点(2)j:=1;(3)p:=p.right 工作指针后移(4)s.left:=p(5)p.right.left:=s; p后继的前驱是s(6)s.left:=p;25.(1)ipre-next=q-next; q-next-pre=q-pre; 先将q结点从链表上摘下q.next:=p; q.pre:=p.pre; p.pre-next:=q; p.pre:=q; 结点q插入结点p前(4) q.freq=0 链表中无值为x的结点，将新建结点插入到链表最后（头结点前）。29(1)a.key:=a的头结

7、点用作监视哨，取不同于a链表中其它数据域的值 (2)b.key:=p.keyb的头结点起监视哨作用 (3)p:=p.next找到a,b表中共同字母，a表指针后移 (4)0(m*n)30. C 部分：(1)p!=null 链表未到尾就一直作(2)q 将当前结点作为头结点后的第一元素结点插入31. (1)L=L-next; 暂存后继 (2)q=L; 待逆置结点 (3)L=p; 头指针仍为L32. (1) p.nextp0 (2)r:= p.next (3) p.next:= q0; (4) q0:= p; (5) p:=r33. (1)r (2)NIL (3)xhead.data (4)p.dat

8、a=x; (7)r (8)p (9)r (10)NIL (11)NIL34(1)pa!=ha 或pa-exp!=-1 (2)pa-exp=0 若指数为0，即本项为常数项 (3)q-next=pa-next 删常数项 (4)q-next 取下一元素 (5)=pa-coef*pa-exp (6)- 指数项减1 (7)pa 前驱后移,或q-next (8)pa-next 取下一元素 35(1)q:=p; q是工作指针p的前驱(2)p.datam p是工作指针(3)r:=q; r 记最大值的前驱，(4)q:=p; 或q:=q.next;(5)r.next:=q.next; 或r.next:=r.nex

9、t.next 删最大值结点36(1)L-next=null 置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null 当链表尚未到尾，p为工作指针 (3)q!=null 查p结点在链表中的插入位置，这时q是工作指针。 (4)p-next=r-next 将p结点链入链表中 (5)r-next=p r是q的前驱，u是下个待插入结点的指针。37程序（a） PASCAL部分(编者略）程序（b） C部分(1)(A!=null & B!=null) 两均未空时循环(2)A-element=B-element 两表中相等元素不作结果元素(3)B=B-link 向后移动B表指针(4)A!=null

10、将A 表剩余部分放入结果表中(5)last-link=null 置链表尾四、 应用题 1（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。 2链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3采用链式存储结构，它根据实际需要申请内存空间，而当不需要

11、时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。4线性表 栈 队列 串 顺序存储结构和链式存储结构。 顺序存储结构的定义是： CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD elem:ARRAY1.maxlen OF ElemType; last:0.maxlen; END; 链式存储结构的定义是： TYPE pointer=nodetype; nodetype=RECORD data:ElemType; next:pointer; END; linklisttp=pointer;5.顺序映射时，ai与ai+1的物理

12、位置相邻；链表表示时ai与ai+1的物理位置不要求相邻。6在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。7见上题6。8(1)将next域变为两个域: pre和next，其值域均为0.maxsize。初始

13、化时，头结点（下标为0的元素）其next域值为1，其pre域值为n（设n是元素个数，且nnext; p-next=q-next; free(q); 13. 设单链表的头结点的头指针为head,且pre=head； while(pre-next!=p) pre=pre-next; s-next=p; pre-next=s; 14.设单链表带头结点，工作指针p初始化为p=H-next; (1) while(p!=null & p-data!=X) p=p-next; if(p= =null) return(null);查找失败else return(p);查找成功(2) while(p!=null

14、 & p-datanext; if(p=null | p-dataX) return(null);查找失败 else return(p);(3) while(p!=null & p-dataX) p=p-next; if(p=null | p-dataX) return(null); 查找失败 else return(p); 查找成功 15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中（pa中与pb中不同结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。S1记结果链表中结点个数（即pa与pb中相等的元素个数）。S2记原pa链表中删除的结点个数。 16设 q:=p.l

15、link; 则 q.rlink:=p.rlink; p.rlink.llink:=q; p.llink:=q.llink;q.llink.rlink:=p; p.rlink:=q; q.llink:=p 17.(1)前两个语句改为： p.llink.rlink- p.rlink; p.rlink.llink- p.llink;(2)后三个语句序列应改为：q.rlink- p.rlink;以下三句的顺序不能变 p.rlink.llink- q; p.rlinkpre=p-pre; s-next=p; p-pre-next=s; p-pre=s; 20(A) f1NIL并且f2NIL(B) f1.

16、data f2.data(C) f2.dataf1.data(D) f3.dataf1.data(E) f1prior=q-prior;将q结点摘下，以便插入到适当位置。(2)p-next-prior=q;（2）（3）将q结点插入(3)p-next=q;(4)r=r-next;或r=q-next;后移指针，再将新结点插入到适当位置。五、 算法设计题1题目分析因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。LinkedList Union(LinkedList

17、la,lb) la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。 pa=la-next; pb=lb-next;pa，pb分别是链表la和lb的工作指针 la-next=null; la作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null & pb!=null) 当两链表均不为空时作 if(pa-datadata) r=pa-next; 将pa 的后继结点暂存于r。 pa-next=la-next; 将pa结点链于结果表中，同时逆置。la-next=pa;pa=r; 恢复pa为当前待比较结点。

18、elser=pb-next; 将pb 的后继结点暂存于r。pb-next=la-next; 将pb结点链于结果表中，同时逆置。la-next=pb;pb=r; 恢复pb为当前待比较结点。 while(pa!=null) 将la表的剩余部分链入结果表，并逆置。 r=pa-next; pa-next=la-next; la-next=pa; pa=r; while(pb!=null) r=pb-next; pb-next=la-next; la-next=pb; pb=r; 算法Union结束。算法讨论上面两链表均不为空的表达式也可简写为while(pa&pb),两递增有序表合并成递减有序表时，上

19、述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 与本题类似的其它题解答如下：（）问题分析与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。LinkedList Union(LinkedList ha, hb) ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在

20、ha中的数据合并到ha中，合并中不能破坏hb链表。LinkedList la; la=(LinkedList)malloc(sizeof(LNode); la-next=ha;申请头结点，以便操作。 pa=ha; pa是ha链表的工作指针pb=hb; pb是hb链表的工作指针pre=la; pre指向当前待合并结点的前驱。while(pa&pb) if(pa-datadata)处理ha中数据 pre-next=pa;pre=pa;pa=pa-next; else if(pa-datapb-data)处理hb中数据。 r=(LinkedList)malloc(sizeof(LNode);申请空间

21、 r-data=pb-data; pre-next=r;pre=r;将新结点链入结果链表。 pb=pb-next;hb链表中工作指针后移。 else处理pa-data=pb-data; pre-next=pa; pre=pa; pa=pa-next;两结点数据相等时，只将ha的数据链入。 pb=pb-next;不要hb的相等数据 if(pa!=null)pre-next=pa;将两链表中剩余部分链入结果链表。else pre-next=pb;free(la);释放头结点.ha,hb指针未被破坏。算法nion结束。 (2)本题与上面两题类似，要求结果指针为lc，其核心语句段如下： pa=la-n

22、ext;pb=hb-next; lc=(LinkedList )malloc(sizeof(LNode); pc=lc;pc是结果链表中当前结点的前驱 while(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; if(pa)pc-next=pa; else pc-next=pb; free(la);free(lb);释放原来两链表的头结点。 算法时间复杂度为O（m+n），其中m和n分别为链表la和lb的长度。 2题目分析本组题有6个，本质上都是链表的合并操作，合并中有各种

23、条件。与前组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差（AB，AB，A-B）等。本题与上面1（2）基本相同，不同之处1（2）中链表是“非递减有序”，（可能包含相等元素），本题是元素“递增有序”（不准有相同元素）。因此两表中合并时，如有元素值相等元素，则应删掉一个。 LinkedList Union(LinkedList ha,hb) 线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B的并集AB，仍用线性表表示，结果链表元素也是递增有序。 pa=ha-next;pb=hb-next;设工作指针pa和pb。 pc=ha

24、;pc为结果链表当前结点的前驱指针。 while(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else if(pa-datapb-data) pc-next=pb;pc=pb;pb=pb-next; else处理pa-data=pb-data. pc-next=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next;free(u); if(pa) pc-next=pa; 若ha表未空，则链入结果表。 else pc-next=pb;若hb表未空，则链入结果表。 free(hb); 释放hb头结点 return(ha)

25、; 算法Union结束。 与本题类似的其它几个题解答如下：(1) 解答完全同上2。(2) 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：pa=la-next;pb=lb-next;设工作指针pa和pb；pc=la;结果表中当前合并结点的前驱的指针。while(pa&pb) if(pa-data=pb-data)交集并入结果表中。 pc-next=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next;free(u); else if(pa-datadata) u=pa;pa=pa-next;free(u);else u=pb; pb=pb-n

26、ext; free(u);while(pa) u=pa; pa=pa-next; free(u); 释放结点空间while(pb) u=pb; pb=pb-next; free(u);释放结点空间pc-next=null;置链表尾标记。free(lb); 注： 本算法中也可对B表不作释放空间的处理（3）本题基本与（2）相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并入链表。其核心语句段如下。 pa=L1-next;pb=L2-next;pa、pb是两链表的工作指针。 pc=L1;L1作结果链表的头指针。 while(pa&pb) if(pa-data

27、data) u=pa;pa=pa-next;free(u);删除L1表多余元素 else if (pa-datapb-data) pb=pb-next; pb指针后移 else 处理交集元素if(pc=L1) pc-next=pa;pc=pa;pa=pa-next; 处理第一个相等的元素。 else if(pc-data=pa-data) u=pa;pa=pa-next;free(u); 重复元素不进入L1表。 else pc-next=pa;pc=pa;pa=pa-next; 交集元素并入结果表。 while while(pa) u=pa;pa=pa-next;free(u); 删L1表剩余

28、元素 pc-next=null; 置结果链表尾。注： 本算法中对L2表未作释放空间的处理。（4） 本题与上面（3）算法相同，只是结果表要另辟空间。（5） 题目分析本题首先求B和C的交集，即求B和C中共有元素，再与A求并集，同时删除重复元素，以保持结果A递增。LinkedList union(LinkedList A,B,C)A,B和C均是带头结点的递增有序的单链表，本算法实现A= A（BC），使求解结构保持递增有序。pa=A-next;pb=B-next;pc=C-next;设置三个工作指针。 pre=A; pre指向结果链表中当前待合并结点的前驱。 if(pa-datadata|pa-dat

29、adata)A中第一个元素为结果表的第一元素。 pre-next=pa;pre=pa;pa=pa-next;elsewhile(pb&pc) 找B表和C表中第一个公共元素。 if(pb-datadata)pb=pb-next; else if(pb-datapc-data)pc=pc-next; else break; 找到B表和C表的共同元素就退出while循环。 if(pb&pc) 因共同元素而非B表或C表空而退出上面while循环。 if(pa-datapb-data)A表当前元素值大于B表和C表的公共元素，先将B表元素链入。 pre-next=pb;pre=pb;pb=pb-next;

30、pc=pc-next; B，C公共元素为结果表第一元素。 结束了结果表中第一元素的确定while(pa&pb&pc) while(pb&pc) if(pb-datadata) pb=pb-next; else if(pb-datapc-data) pc=pc-next; else break; B表和C表有公共元素。 if(pb&pc) while(pa&pa-datadata) 先将A中小于B，C公共元素部分链入。 pre-next=pa;pre=pa;pa=pa-next; if(pre-data!=pb-data)pre-next=pb;pre=pb;pb=pb-next;pc=pc-n

31、ext; elsepb=pb-next;pc=pc-next; 若A中已有B，C公共元素，则不再存入结果表。 while(pa&pb&pc) if(pa) pre-next=pa; 当B，C无公共元素（即一个表已空），将A中剩余链入。算法Union结束 算法讨论本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用

32、了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。 最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。 3题目分析循环单链表L1和L2数据结点个数分别为m和n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。 LinkedList Union(LinkedList

33、 L1,L2;int m,n) L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。本算法用最快速度将L1和L2合并成一个循环单链表。if(m0|n0) printf(“表长输入错误n”)；exit(0); if(mn) 若mnext!=L1) p=p-next;查最后一个元素结点。 p-next=L2-next;将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2-next=L1-next; free(L1);释放无用头结点。 处理完mnext!=L2) p=p-next;查最后元素结点。 p-next=L1-next;将L2的元素结点插入到L1循环单链表的第一

34、元素结点前。 L1-next=L2-next; free(L2);释放无用头结点。算法结束。类似本题叙述的其它题解答如下：（1）题目分析本题将线性表la和lb连接，要求时间复杂度为O（1），且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。 LinkedList Union(LinkedList la,lb) la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一个单循环链表。 q=la-next; q指向la的第一个元素结点。 la-next=lb-next; 将lb的最后元素结点接到lb的第一元素。 lb-next=q; 将lb指向la的第一元素结点，实现了lb接在la后。 return(lb); 返回结果单循环链表的尾指针lb。 算法结束。 算法讨论若循环单链表带有头结点，则相应算法片段如下： q=lb-next; q指向lb的头结点； lb-next=la-next; lb的后继结点为la的头结点。 la-next=q-next; la的后继结点为lb的第一元素结点。 free(q); 释放lb的头结点 return(lb); 返回结果单循环链表的尾指针lb。（2）题目分析本题要求