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

《数据结构第2章线性表答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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．两种存储结构各有优

2、缺点，应根据实际情况选用，不能笼统说哪一个好。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-

3、>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

4、);(2)pb<>NILANDpa^.data>=pb^.data(3)return(inclusion(pa,pb));(4)pb:=pb^.next;(5)return(false);非递归算法：(1)pre:=pb;(2)pa<>NILANDpb<>NILANDpb^.data>=pa^.data(3)pa:=pa^.next;pb:=pb->next;(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IFpa=NILTHENreturn(true)ELSEreturn(fal

5、se);[注]：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。20．A．VARhead:ptrB.new(p)C.p^.data:=kD.q^.next:=pE.q:=p(带头结点)21．（1）new(h);∥生成头结点

6、，以便于操作。（2）r^.next:=p;(3)r^.next:=q;(4)IF(q=NIL)THENr^.next:=p;22．A:r^.link^.data<>maxANDq^.link^.data<>maxB: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)j

7、ead的前驱指针指向插入结点(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:

8、=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^.li