第2章线性表 选择题 1.A|2.B3.C4.A C9.B|10.B,C|11 11.4B1.5c12.B13.c14.C15.C .A17.A18.A19.D20.C21.B 22.D23.C|24.B25.B26.A27.D 判断题 14. 16 部分答案解释如下 1、头结点并不“仅起”标识作用,并且使操作统一。另外,头结点数据域可写入链表长度, 或作监视哨。 4.两种存储结构各有优缺点,应根据实际情况选用,不能笼统说哪一个好。 7.集合中元素无逻辑关系 9.非空线性表第一个元素无前驱,最后一个元素无后继 13.线性表是逻辑结构,可以顺序存储,也可链式存储。 三.填空题 1.顺序 2.(n-1)/2 3. py->next=px->next: px->next=p 4 5.主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必 另作判断。另外,不论链表是否为空,链表指针不变 6.0(1),0(n 7.单链表,多重链表,(动态)链表,静态链表 8. f->next=p->next: f->prior=p: p->next->prior=f: p->next=f s, prior next 10.指针 11.物理上相邻指针 13.从任一结点出发都可访问到链表中每一个元素 14. u=p->next; p->next=u->next: free(u) 15. L->next->next==L 16. p->next! =null 7. L->next==l & L->prior==L 18. s->next=p->next: p->next=s 19.(1)IF pa=NIL THEN return(true) (2) pboNIL AND pa. data>=pb. data (3)return(inclusion(pa, pb)) (4)pb:=pb.next (5 return(false) 非递归算法 (1)pre: pb;(2)paONIL AND pb<>NIL AND pb. data)=pa. data (3)pa: =pa. nex nex (4)pb: =pre. next: pre: =pb pa: =pa. next: (5)IF pa=NIL THEN return (true) ELSE return(false) [注]:本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点(初 始时为第一元素结点)。若主串与子串对应数据相等,两串工作指针pa和pb后移;否则,第 2 章 线性表 一．选择题 1.A 2.B 3.C 4.A 5.D 6.D 7.D 8.C 9.B 10.B,C 11.1I 11.2I 11.3E 11.4B 11.5C 12.B 13.C 14.C 15.C 16.A 17.A 18.A 19.D 20.C 21.B 22.D 23.C 24.B 25.B 26.A 27.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）/2 3．py->next=px->next; px->next=py 4 ．n-i+1 5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必 另作判断。另外，不论链表是否为空，链表指针不变。 6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表 8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; 9．p^.prior s^.prior^.next 10． 指针 11．物理上相邻 指针 12．4 2 13．从任一结点出发都可访问到链表中每一个元素。 14 ． u=p->next; p->next=u->next; free(u); 15 ． L->next->next==L 16．p->next!=null 17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s; 19．(1) IF pa=NIL THEN return(true); (2) pb<>NIL AND pa^.data>=pb^.data (3) return(inclusion(pa,pb)); (4) pb:=pb^.next; (5) return(false); 非递归算法： (1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)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 后移；否则