第 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．非空线性表第一个元素无前驱，最后一个元素无后继。13．线性表是逻辑结构，可以顺序存储，也可链式存储。三．填空题1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py4 ．n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作推断。另外，不论链表是否为空，链表指针不变。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^.next10． 指针 11．物理上相邻 指针 12．4 213．从任一结点出发都可访问到链表中每一个元素。14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null17．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 后移；否则，主串工作指针从 pre 的下一结点开始（这时 pre 又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若 pa 为空，则匹配成功，返回true，否则，返回 false。20．A．VAR 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...
