25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
【北京工商大学 2001 一、5（3分）】
26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。
A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p;
C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;
【西安电子科技大学 1998 一、1（2分）】
27. 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）
A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。 【南京理工大学 1997 一、1（2分）】
二、判断
1. 链表中的头结点仅起到标识的作用。( )【南京航空航天大学 1997 一、1（1分）】 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2（1分）】
3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )
【北京邮电大学 1998 一、2（2分）】
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )
【北京邮电大学 2002 一、2（1分）】
5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3（1分）】
6．顺序存储方式只能用于存储线性结构。( )
【中科院软件所 1999 六、1-2（2分）】【上海海运学院 1997 一、1（1分）】
7．集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5 ( 1分)】
8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、1（1分）】 9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、1（1分）】
10. 取线性表的第i个元素的时间同i的大小有关. ( )【南京理工大学 1997 二、9（2分）】
11. 循环链表不是线性表. ( )【南京理工大学 1998 二、1（2分）】
12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、2（1分）】 13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、1（1分）】 14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )
【上海海运学院 1995 一、1（1分）】 【上海海运学院 1997 一、2（1分）】
15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 【上海海运学院 1996 一、1（1分）】 【上海海运学院 1999 一、1（1分）】 16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结
构中效率高。 ( ) 【上海海运学院 1998 一、2（1分）】
三、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。【北方交通大学 2001 二、4】
2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。【北方交通大学 2001 二、9】
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一、4（2分）】
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
【北京工商大学 2001 二、4（4分）】
5．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二、1（1分）】 6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一、1（2分）】
7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。【西安电子科技大学1998 二、4（3分）】
8． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一、1（3分）】 9. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s； 【福州大学 1998 二、7 (2分)】
10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。【中山大学 1998 一、1 （1分）】
11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七、2 （2分）】
12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。
【南京理工大学 2000 二、2 （3分）】
13. 循环单链表的最大优点是：________。【福州大学 1998 二、3 (2分)】
14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________
【合肥工业大学 1999 三、2 （2分）】
15. 带头结点的双循环链表L中只有一个元素结点的条件是：________
【合肥工业大学 1999 三、3 2000 三、2（2分）】
16. 在单链表L中，指针p所指结点有后继结点的条件是：__ 【合肥工业大学 2001 三、3 （2分）】
17.带头结点的双循环链表L为空表的条件是：________。 【北京理工大学 2000 二、1 （2分）】 【青岛大学 2002 三、1 （2分）】 18. 在单链表p结点之后插入s结点的操作是：_______。【青岛大学 2002 三、2（2分）】 19. 请在下列算法的横线上填入适当的语句。【清华大学 1994 五 （15分）】
FUNCTION inclusion(ha,hb:linklisttp):boolean;
{以ha和hb为头指针的单链表分别表示有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返回“false”}
BEGIN
pa:=ha^.next; pb:=hb^.next; （1） ; WHILE（2） DO
IF pa^.data=pb^.data THEN（3） ELSE（4） ; （5） END;
20．完善算法：已知单链表结点类型为：
TYPE ptr=^node； node=RECORD
data：integer； next：ptr
END；
过程create建立以head为头指针的单链表。 PROCEDURE create ( (1) )； VAR p,q：ptr； k：integer； BEGIN
new（head）； q:=head；read（k）；
WHILE k>0 DO BEGIN
(2); (3); (4); (5); read（k） END;
q^.next：=NIL;
END;【北京师范大学 1999 三】 21. 已给如下关于单链表的类型说明： TYPE
list=^node ;
node=RECORD
data: integer; next: list; END;
以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.
PROCEDURE mergelink(VAR p,q:list): VAR h,r: list; BEGIN
（1）______
h^.next:= NIL; r:=h;
WHILE((p<>NIL) AND (q<>NIL)) DO IF (p^.data<=q^.data)
THEN BEGIN （2）___； r:=p; p:=p^.next； END ELSE BEGIN （3）____； r:=q; q:=q^.next; END; IF (p=NIL) THEN r^.next:=q;
（4）__；
p:=h^.next; dispose(h);
END;【厦门大学 2000 三、2 （8分）】
22．假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max，在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）。下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下
TYPE nodeptr=^nodetype； nodetype=RECORD
data：integer； link：nodeptr;
END；
CONST max=9999;
PROCEDURE merge(VAR p:nodeptr;q:nodeptr); VAR r,s: nodeptr; BEGIN r:=p;
WHILE (A)___ DO BEGIN
WHILE r^.link^.data
ELSE BEGIN (H)__; s:=q^.link; (I)__; dispose(s) END END;
dispose(q)
END;【复旦大学 1997 五（18分）】
23．PROC ins__linklist(la:linkisttp; i:integer; b:elemtp);
{la为指向带头结点的单链表的头指针，本算法在表中第i个元素之前插入元素b} p:=(1) ; j:=(2) ;{指针初始化，j为计数器}
WHILE (p<>NIL) AND ((3) ) DO [p:=(4) ; j:=j+1；] {寻找第 i-1 个结点}
IF (p=NIL) OR ((5) )
THEN error (‘No this position’)
ELSE [new(s) ; s↑.data:=b; s↑.next:=p↑.next; p↑.next:=s;] ENDP;{ins-linklist}【燕山大学 1998 四、1（15分）】 24. 已知双链表中结点的类型定义为：
TYPE dpointer=^list;
list=RECORD
data:integer; left,right:dpointer; END;
如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。
PROCEDURE insert(VAR head:dpointer;i,x:integer); VAR s,p:dpointer; j: integer; BEGIN
new(s); s^.data:=x;
IF(i=0)THEN BEGIN s^.right:=head; (1)___ head:=s END{如果i=0,则将s结点插入到表头后返回}
ELSE BEGIN p:=head; (2)_______；{在双链表中查找第i个结点,由p所指向}
WHILE ((p<>NIL) AND (j
IF （p^.right=NIL）
THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END
ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END ELSE writeln(‘can not find node!’) END
END;【厦门大学 2002 二 （12分）】
25．阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。 CONST maxlen=30
TYPE sqlisttp=RECORD
elem:ARRAY[1..maxlen] OF integer; last:0..maxlen END;
PROC exam21(VAR L:sqlisttp); j:=1; i:=2;
WHILE (1)______ DO
[ IF L.elem[i]<>L.elem[j] THEN [ (2)_______; (3)______]; i:=i+1 ] (4) ________;
ENDP;【同济大学 2000 二、1 (10分)】
26．在本题的程序中，函数过程Create_link_list(n)建立一个具有n个结点的环形链表;程序过程 josephus(n,i,m)对由Create_link_list(n)所建立的具有n个结点的环形链表按一定的次序逐个输出并删除链表中的所有结点，参数 n(n>0)指明环形链表的结点个数，参数 i(1<=i<=n)指明起始结点，参数 m (m>0)是步长，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。例如，对于下图中具有6个结点的环形链表，在调用 josephus(6,3,2)后，将输出 5,1,3,6,4,2 请在横线处填上适当内容，
每空只填一个语句。