《数据结构线性表答案》由会员分享，可在线阅读，更多相关《数据结构线性表答案（34页珍藏版）》请在金锄头文库上搜索。
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采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。4线性表 栈 队列 串 顺序存储结构和链式存储结构。 顺序存储结构的定义是： CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD elem:ARRAY1.maxlen OF ElemType; last:0.maxlen; END; 链式存储结构的定义是： TYPE pointer=nodetype; nodetype=RECORD data:ElemType; next:pointer;
