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 请在横线处填上适当内容，
每空只填一个语句。
TYPE nodeptr=^nodetype; nodetype=RECORD
data: intrger; link: nodeptr
END; VAR n,i,m: integer;
FUNCTION Create_link_list(n: integer): nodeptr; VAR head,p,q: nodeptr; i:integer; BEGIN head := NIL; IF n>0 THEN
BEGIN new(head); p: =head; FOR i:=1 TO n-1 DO
BEGIN p^.data:=i; new(q); (A)____; (B)____ END； p^.data:=n; (C)___; END;
Creat_link_list:=head
END;
PROCEDURE josephus(n,i,m:integer); VAR p,q:nodeptr; j:integer; BEGIN p:=Creat_link_list(n);
WHILE i>1 DO BEGIN p:=p^.link; i:=i-1 END; (D)___ ;
WHILE j FOR i:=1 TO m-1 DO p:=p^.link; (E)___; write(q^.data:8); (F)__ ; dispose(q); j:=j+1 END END;【复旦大学 1997 四（12分）】 27．对于给定的线性链表head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。 TYPE nodeptr =^ nodetype； nodetype = RECORD data : integer；link : nodeptr END; VAR head : nodeptr； PROCEDURE sort_output_delete (head : nodeptr); VAR p,q,r,s: nodeptr; BEGIN WHILE head <> NIL DO BEGIN p:= NIL ；q:= head；r:= q ；s:=q^.link ； WHILE s <> NIL DO BEGIN IF s^.data < q^.data THEN BEGIN (1)__; (2)___ END ； r:= s ； (3)___ END； write(q^.data : 5) ； IF p=NIL THEN (4)___ ELSE (5)____ ； dispose (q) ； END； writeln END；【复旦大学 1996 七（20分） 1995 一（12分）与本题相似】 28．下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为x的结点，对该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。 TYPE link=^node node=RECORD key:char; freq:integer; pre,next:link; END; VAR l:link;