数据结构第2章线性表答案

郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：13633846090第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）/23．py-next=px-next;px-next=py4．n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。6．O(1)，O(n)7．单链表，多重链表，（动态）链表，静态链表8．f-next=p-next;f-prior=p;p-next-prior=f;p-next=f;9．p^.priors^.prior^.next10．指针11．物理上相邻指针12．4213．从任一结点出发都可访问到链表中每一个元素。14．u=p-next;p-next=u-next;free(u);15．L-next-next==L16．p-next!=null17．L-next==L&&L-prior==L18．s-next=p-next;p-next=s;19．(1)IFpa=NILTHENreturn(true);(2)pbNILANDpa^.data=pb^.data(3)return(inclusion(pa,pb));(4)pb:=pb^.next;(5)return(false);非递归算法：(1)pre:=pb;(2)paNILANDpbNILANDpb^.data=pa^.data(3)pa:=pa^.next;pb:=pb-next;(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IFpa=NILTHENreturn(true)ELSEreturn(false);[注]：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：13633846090主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。20．A．VARhead:ptrB.new(p)C.p^.data:=kD.q^.next:=pE.q:=p(带头结点)21．（1）new(h);∥生成头结点，以便于操作。（2）r^.next:=p;(3)r^.next:=q;(4)IF(q=NIL)THENr^.next:=p;22．A:r^.link^.datamaxANDq^.link^.datamaxB:r:=r^.linkC:q^.linkD:q^.linkE:r^.linkF:r^.linkG:r:=s（或r:=r^.link）H:r:=r^.linkI:q^.link:=s^.link23．(1)la(2)0(3)ji-1(4)p↑.next(5)i124.(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.elem[j]:=L.elem[i]∥元素前移(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)p^link:=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^.key∥b的头结点起监视哨作用(3)p:=p^.next∥找到a,b表中共同字母，a表指针后移(4)0(m*n)30.C部分：(1)p!=null∥链表未到尾就一直作郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：13633846090(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^.datax(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^.datam∥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)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：136338460903．采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。4．线性表栈队列串顺序存储结构和链式存储结构。顺序存储结构的定义是：CONSTmaxlen=线性表可能达到的最大长度；TYPEsqlisttp=RECORDelem:ARRAY[1..maxlen]OFElemType;last:0..maxlen;END;链式存储结构的定义是：TYPEpointer=↑nodetype;nodetype=RECORDdata: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是元素个数，且nmaxsize）(2)stalist[stalist[p].pre].pre;(3)stalist[p].next;9.在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。10．本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。11．该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false“。pre指向当前结点，p指向pre的后继。12．q=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