《北航计算机考研材料第2章线性表答案》由会员分享，可在线阅读，更多相关《北航计算机考研材料第2章线性表答案（46页珍藏版）》请在金锄头文库上搜索。
1、第2章线性表选择题1. A2.B3. C4. A5.D6.D7.D8.C9.B10. B, C11. 1111.2111.3E11.4B11. 5C12. B13. C14. C15. C16. A17. A18. A19. D20. C21. B22. D23. C24. B25. B26. A27. D判断题1. X2. V3.V4. X5.X6.X7.X8.X9.X10.X11.X12.X13.X14.15.X16.V部分答案解释如下。1、头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度或作监视哨。4. 两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪
2、一个好。7.集合中元素无逻辑关系。9.非空线性表第一个元素无前驱，最后一个元素无后继。13.线性表是逻辑结构，可以顺序存储，也可链式存储。三.填空题1.顺序2. (nT) /23. py-n ext=px-n ext: px-n ext=py4 . n-i+15.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第-个结点不必另作判断。另外，不论链表是否为空，链表指针不变6.0(1), 0(n)7.单链表，多重链表，(动态)链表，静态链表8. f-n ext=p-n ext; f-prior=p; p-n ext-prior=f; p-n ext=f;9. p prior s pri
3、or , n ext10. 指针11.物理上相邻 指针12. 413.从任一结点出发都可访问到链表中每一个元素。14 . u=p-n ext; p-n ext=u-n ext; free(u);16.p next!=null17. L- next=L & L- prior=L19. (1) IF pa 二 NIL THEN return(true);(2) pbONIL AND pa, data 二 pb. data(3) retur n(i nclusi on( pa, pb);(4) pb:=pb n ext;(5) return (false);非递归算法：15 . L-n ext- n
4、 ext=L18. s-n ext=p-n ext;p-n ext=s;(l) pre:=pb; paONIL AND pbONIL AND pb data二 pa, data (3)pa:二 pa, next;pb:=pb n ext;(4)pb: 二 pre, next;pre:二 pb;pa: 二 pa, next;(5) IF paNIL THEN retur n( true)ELSE return(false);注:本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点(初始时为第一元素结点)。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，20.结点)
5、A. VAR head:ptr B. new(p) C. p data:=k D. qA. n ext:=pE. q:=p(带头21.(1)n ew(h) ; /生成头结点，以便于操作。IF(q=NIL) THEN22.nrAljnlextlatpOmax AND(q liriknedataOnq;xAr:=r. link C: q. link D: q. link r:=s (或E: rL linkF:linkBr:二 r. link) H: r:=A. link (2)0(3)I: q link:二 s . link23. lajvi-l(4)p t . next(5)il开始，比较一直继
6、续到循环条件失败。若pa为空，则匹配成功，返回 true,否贝0，返回false。24. head, left:=s/head的前驱指针指向插入结点 j：=l；(3) p:=p right工作指针后移(4) s. left:=p(5) p” . right. left:=s; p 后继的前驱是 s(6) s. left:=p;25. (1) iprenext=q_next;q_next-pre=q-pre; 先将 q 结点从链表上摘下qnext:=p; q pre:=p . pre; p prenext:=q; p . pre: =q;结点 q 插入结点P前(4) q freq=0链表中无值为
7、 x的结点，将新建结点插入到链表最后(头结点 前)29. (l)aLkey:伊 &的头结点用作监视哨，取不同于a链表中其它数据域的值(2) b key:二p. key b的头结点起监视哨作用(3) p:=p next找到a, b表中共同字母，a表指针后移(4) 0 (m* n)30. C部分：(l)p!=null链表未到尾就一直作31. (l)L=L- next;暂存后继(2)q=L;待逆置结点(3) L=p;头指针仍为L32. p . nextOpo(2)r:= p*. next(3) p next：=qo； qo : = p；(5) p :=r33. (l)r(2)NIL(3)xhead
8、.data(4)p . dataexp!=-l(2)pa-exp=0若指数为0,即本项为常数项(3) q- next=pa- next /删常数项(4)q _n ext取卜兀素(5)=pa-coef*pa-exp一/指数项减1pa前驱后移，或q- next(8)pa-n ext.nW-取卜兀素35. (l)q:=p; q是工作指针P的前驱(2) p datamP是工作指针(3)r:二 q;/r记最大值的前驱，(4)q:=p;或 q:=q. next;(5)n ext:=q.n ext;或 r. n ext:=rA.n ext .n ext删最大值结点四、36.37.(l)L- next=nul
9、l(5)p!=n ullq!=n ull p-n ext=r- n ext r-n ext=p置空链表，然后将原链表结点逐个插入到有序表中当链表尚未到尾，P为工作指针查p结点在链表中的插入位置，这时q是工作指针。将p结点链入链表中 1是4的前驱，u是下个待插入结点的指针。程序(b) C部分(1)(A!=n ull & B匸n ull)两均未空时循环(2)A-eleme nt=B-eleme nt两表中相等兀素不作结果兀素(3)B=B-li nk向后移动B表指针(4)A!=null将A表剩余部分放入结果表中(5)last-li nk=n ull置链表尾应用题程序PASCAL部分(编者略)1. (
10、1)选链式存储结构。它可动态申请内存空间，不受表长度影响，插入、删 除时间复杂度为 0(1)。(2)选顺序存储结构。顺序表可以随机存取，时间复杂度为(即表中元素个数)的0 (1)。2. 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为0(1);其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。空间返还3. 采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点 给系统。在链式存储结构中插入和删除操作不需要移动元素。
11、4. 线性表栈队列串顺序存储结构和链式存储结构。顺序存储结构的定义是：CONST maxle门=线性表可能达到的最大长度；TYPE sqlisttp=RECORDelem: ARRAY1. . maxle n OF ElemType;last:0. maxle n;END;链式存储结构的定义是：TYPE poin ter= f no detype;nodetype=RECORDdata:ElemType; n ext:po in ter;END;lin klisttp=po in ter;5. 顺序映射时，ai与ai+i的物理位置相邻；链表表示时ai与ai+i的物理位置不要求相邻。6. 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。7. 见上题6。8. (1)将next域变为两个域：pre和next,其值域均为O.maxsize。初始化时，头结 点(下标为 0的元素)其ne
