数据结构1800题（答案全）(8)

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

IF r^.link^.data>q^.link^.data

THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END

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<>NIL THEN

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

BEGIN

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 ；