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

第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非空线性表第一个元素无前驱，最后一个元素无后继。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从任一结点出发都可访问到链表中每一个元素。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) pb<>NIL AND pa.data>=pb.data(3) return(inclusion(pa,pb);(4) pb:=pb.next;(5) return(false);非递归算法：(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb.data>=pa.data (3)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:ptr 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.data<>max AND q.link.data<>maxB: 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)j<i-1 (4)p.next (5)i<1 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)i<=L.last L.last 为元素个数 (2)j:=j+1 有值不相等的元素(3)L.elemj:=L.elemi 元素前移(4)L.last:=j 元素个数26.(A)p.link:=q;拉上链，前驱指向后继 (B)p:=q;新的前驱 (C)p.link:=head;形成循环链表 (D)j:=0; 计数器，记被删结点 (E)q:=p.link记下被删结点 (F)p.link=q.link 删除结点27. (1)p:=r;r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;q指向最小值结点，s是工作指针(3)s:=s.link工作指针后移(4)head:=head.next;第一个结点值最小；(5)plink:=q.link;跨过被删结点（即删除一结点）28(1) l.key:=x;头结点l这时起监视哨作用 (2) l.freq:=p.freq 头结点起监视哨作用(3) q->pre->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的头结点用作监视哨，取不同于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.next<>p0 (2)r:= p.next (3) p.next:= q0; (4) q0:= p; (5) p:=r33. (1)r (2)NIL (3)x<head.data (4)p.data<x (5)p:=p.next (6)p.data>=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.data>m p是工作指针(3)r:=q; r 记最大值的前驱，(4)q:=p; 或q:=q.next;(5)r.next:=q.next; 或r.next:=r.next.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 将A 表剩余部分放入结果表中(5)last->link=null 置链表尾四、 应用题 1（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。 2链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。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的物理位置相邻；链表表示时ai与ai+1的物理位置不要求相邻。6在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。7见上题6。8(1)将next域变为两个域: pre和next，其值域均为0.maxsize。初始化时，头结点（下标为0的元素）其next域值为1，其pre域值为n（设n是元素个数，且n<maxsize） (2) staliststalistp.pre.pre;(3) stalistp.next; 9. 在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 10本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 11该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false“。pre指向当前结点，p指向pre的后继。 12q=p->next; 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 && p->data<X ) p=p->next; if(p=null | p->data>X) return(null);查找失败 else return(p);(3) while(p!=null && p->data>X) p=p->next; if(p=null | p->data<X) return(null); 查找失败 else return(p); 查找成功 15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中（pa中与pb中不同结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。S1记结果链表中结点个数（即pa与pb中相等的元素个数）。S2记原pa链表中删除的结点个数。 16设 q:=p.llink; 则 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.rlink<- q; 18mp是一个过程，其内嵌套有过程subp。subp(s,q)的作用是构造从s到q的循环链表。subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环链表中）构造为循环链表。总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。 19在指针p所指结点前插入结点s的语句如下：s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s; 20(A) f1<>NIL并且f2<>NIL(B) f1.data < f2.data(C) f2.data<f1.data(D) f3.data<f1.data(E) f1<- f1.link 或f2=f2.link; 21. 1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向循环链表。 2）(1)r->prior=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 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->data<=pb->data) r=pa->next; 将pa 的后继结点暂存于r。 pa->next=la->next; 将pa结点链于结果表中，同时逆置。la->next=pa;pa=r; 恢复pa为当前待比较结点。 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),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 与本题类似的其它题解答如下：（）问题分析与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。LinkedList Union(LinkedList ha, hb) ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在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->data<pb->data)处理ha中数据 pre->next=pa;pre=pa;pa=pa->next; else if(pa->data>pb->data)处理hb中数据。 r=(LinkedList)malloc(sizeof(LNode);申请空间 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->next;pb=hb->next; lc=(LinkedList )malloc(sizeof(LNode); pc=lc;pc是结果链表中当前结点的前驱 while(pa&&pb) if(pa->data<pb->data) 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个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差（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;pc为结果链表当前结点的前驱指针。 while(pa&&pb) if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next; else if(pa->data>pb->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); 算法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->data<pb->data) u=pa;pa=pa->next;free(u);else u=pb; pb=pb->next; 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<pb->data) u=pa;pa=pa->next;free(u);删除L1表多余元素 else if (pa->data>pb->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表剩余元素 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->data<pb->data|pa->data<pc->data)A中第一个元素为结果表的第一元素。 pre->next=pa;pre=pa;pa=pa->next;elsewhile(pb&&pc) 找B表和C表中第一个公共元素。 if(pb->data<pc->data)pb=pb->next; else if(pb->data>pc->data)pc=pc->next; else break; 找到B表和C表的共同元素就退出while循环。 if(pb&&pc) 因共同元素而非B表或C表空而退出上面while循环。 if(pa->data>pb->data)A表当前元素值大于B表和C表的公共元素，先将B表元素链入。 pre->next=pb;pre=pb;pb=pb->next;pc=pc->next; B，C公共元素为结果表第一元素。 结束了结果表中第一元素的确定while(pa&&pb&&pc) while(pb&&pc) if(pb->data<pc->data) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; B表和C表有公共元素。 if(pb&&pc) while(pa&&pa->data<pb->data) 先将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->next; 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，这占用了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。 最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。 3题目分析循环单链表L1和L2数据结点个数分别为m和n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。 LinkedList Union(LinkedList L1,L2;int m,n) L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。本算法用最快速度将L1和L2合并成一个循环单链表。if(m<0|n<0) printf(“表长输入错误n”)；exit(0); if(m<n) 若m<n，则查L1循环单链表的最后一个结点。 if(m=0)return(L2);L1为空表。 elsep=L1; while(p->next!=L1) p=p->next;查最后一个元素结点。 p->next=L2->next;将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2->next=L1->next; free(L1);释放无用头结点。 处理完m<n情况else 下面处理L2长度小于等于L1的情况 if(n=0)return(L1);L2为空表。 elsep=L2; while(p->next!=L2) p=p->next;查最后元素结点。 p->next=L1->next;将L2的元素结点插入到L1循环单链表的第一元素结点前。 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）题目分析本题要求