《数据结构考研试题精选及答案第2章 线性表答案》由会员分享，可在线阅读，更多相关《数据结构考研试题精选及答案第2章 线性表答案（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集合中元素无逻辑关系。
2、 9非空线性表第一个元素无前驱，最后一个元素无后继。 13线性表是逻辑结构，可以顺序存储，也可链式存储。三填空题 1顺序 2 （n-1）/2 3py-next=px-next; px-next=py 4 n-i+1 5主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必 另作判断。另外，不论链表是否为空，链表指针不变。 6O(1)，O(n) 7单链表，多重链表， （动态）链表，静态链表 8f-next=p-next; f-prior=p; p-next-prior=f; p-next=f; 9p.prior s.prior.next 10 指针 11物理上相邻 指针 12
3、4 2 13从任一结点出发都可访问到链表中每一个元素。 14u=p-next; p-next=u-next; free(u); 15L-next-next=L 16p-next!=null 17L-next=L p-next=s; 19(1) IFIF pa=NIL THENTHEN returnreturn(true);(2) pb=pb.data (3) returnreturn(inclusion(pa,pb); (4) pb:=pb.next; (5) returnreturn(false); 非递归算法：(1)pre:=pb; (2) paNIL AND pb.data=pa.dat
4、a (3)pa:=pa.next; pb:=pb-next; (4)pb:=pre.next;pre:=pb;pa:=pa.next;(5)IFIF pa=NIL THENTHEN returnreturn(true) ELSEELSE returnreturn(false); 注：本题是在链表上求模式匹配问题。非递归算法中用指针 pre 指向主串中开始结点 （初始时为第一元素结点） 。若主串与子串对应数据相等，两串工作指针 pa 和 pb 后移；否则，主串工作指针从 pre 的下一结点开始（这时 pre 又指向新的开始结点） ，子串工作指针 从子串第一元素开始，比较一直继续到循环条件失败。若
5、 pa 为空，则匹配成功，返回 true，否则，返回 false。 20AVARVAR 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) IFIF (q=NIL) THENTHEN r.next:=p; 22A: r.link.datamaxB: r:=r.link C: q.link D: q.link E: r.link F: r.link G: r:=s（或 r:= r.link） H: r:=r.lin
6、k I: q.link:=s.link23(1)la (2)0 (3)jpre-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 表指针后移
7、(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.nextexp!=-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
8、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 部分
9、(1)(A!=null last:0.maxlen;ENDEND;链式存储结构的定义是：TYPETYPE pointer=nodetype;nodetype=RECORDRECORDdata:ElemType;next:pointer;ENDEND;linklisttp=pointer;5.顺序映射时，ai与 ai+1的物理位置相邻；链表表示时 ai与 ai+1的物理位置不要求 相邻。 6在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头 结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的 统一、方便而设立的，放在第一元素结点之前，其数据域一般
10、无意义（当然有些情况下也 可存放链表的长度、用做监视哨等等） ，有头结点后，对在第一元素结点前插入结点和删除 第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。 首元结点也就是第一元素结点，它是头结点后边的第一个结点。 7见上题 6。 8(1)将 next 域变为两个域: pre 和 next，其值域均为 0.maxsize。初始化时，头 结点（下标为 0 的元素）其 next 域值为 1，其 pre 域值为 n（设 n 是元素个数，且 nnext; p-next=q-next; free(q);13. 设单链表的头结点的头指针为 head,且 pre=head；
11、whilewhile(pre-next!=p) pre=pre-next;s-next=p; pre-next=s; 14.设单链表带头结点，工作指针 p 初始化为 p=H-next; (1) whilewhile(p!=null ifif(p= =null) returnreturn(null);查找失败 elseelse returnreturn(p);查找成功(2) whilewhile(p!=null ifif(p=null | p-dataX) returnreturn(null);查找失败elseelse returnreturn(p); (3) whilewhile(p!=nul
12、l ifif(p=null | p-datapre=p-pre; s-next=p; p-pre-next=s; p-pre=s;20(A) f1NIL(B) f1.data prior=q-prior;将 q 结点摘下，以便插入到适当位置。 (2)p-next-prior=q;（2） （3）将 q 结点插入(3)p-next=q; (4)r=r-next;或 r=q-next;后移指针，再将新结点插入到适当位置。五、算法设计题 1题目分析因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起 进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递 减次序排列。
13、故在合并的同时，将链表结点逆置。LinkedList Union(LinkedList la,lb)la,lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算 法将两链表合并成一个按元素值递减次序排列的单链表。 pa=la-next; pb=lb-next;pa，pb 分别是链表 la 和 lb 的工作指针la-next=null; la 作结果链表的头指针，先将结果链表初始化为 空。whilewhile(pa!=null 将 pa 的后继结点暂存于 r。pa-next=la-next; 将 pa 结点链于结果表中，同时逆置。la-next=pa; pa=r; 恢复 pa
14、 为当前待比较结点。elseelse r=pb-next; 将 pb 的后继结点暂存于 r。 pb-next=la-next; 将 pb 结点链于结果表中，同时逆置。la-next=pb; pb=r; 恢复 pb 为当前待比较结点。whilewhile(pa!=null) 将 la 表的剩余部分链入结果表，并逆置。r=pa-next; pa-next=la-next; la-next=pa; pa=r; whilewhile(pb!=null)r=pb-next; pb-next=la-next; la-next=pb; pb=r; 算法 Union 结束。 算法讨论上面两链表均不为空的表达式也可简写为 whilewhile(pala=(LinkedList)malloc(sizeofsizeof(LNode);la-next=ha;申请头结点，以便操作。pa=ha; pa 是 ha 链表的工作指针pb=hb; pb 是 hb 链表的工作指针 pre=la; pre 指向当前待合并结点的前驱。whilewhile(papre=pa;pa=pa-next;elseelse ifif(p
