数据�l�构�W�二章填�I�题及参考答案[4]_跨考网

复习(f��n)紧张�Q�焦头烂额？逆风轻袭�Q�来跨考秋季集训营�Q�帮你寻�Ҏ(gu��)���Q�定�Ҏ(gu��)���Q?/span> 了解一�?>

1. 已给如下关于单链表的�c�d��说明�Q?/span>

 

　　TYPE

 

　　list=^node ;

 

　　node=RECORD

 

　　data: integer; next: list;

 

　　END;

 

　　以下�E�序采用链表合�ƈ的方法，���两个已排序的单链表合�ƈ成一个链表而不改变其排序性（升序�Q�，�q�里两链表的头指针分别�ؓ(f��)p�?/span>q.

 

　　PROCEDURE mergelink(VAR p,q:list):

 

　　VAR h,r: list;

 

　　BEGIN

 

　　�Q?/span>1�Q?/span>______

 

　　h^.next:= NIL; r:=h;

 

　　WHILE((p<>NIL) AND (q<>NIL)) DO

 

　　IF (p^.data<=q^.data)

 

　　THEN BEGIN �Q?/span>2�Q?/span>___�Q?/span> r:=p; p:=p^.next�Q?/span> END

 

　　ELSE BEGIN �Q?/span>3�Q?/span>____�Q?/span> r:=q; q:=q^.next; END;

 

　　IF (p=NIL) THEN r^.next:=q;

 

　　�Q?/span>4�Q?/span>__�Q?/span>

 

　　p:=h^.next; dispose(h);

 

　　END;�?a target="_blank">厦门大学 2000 三�?/span>2 �Q?/span>8分）�?/span>

【参考答案�?/span>

 

　　�Q?/span>1�Q?/span>new(h);∥生成头�l�点�Q�以便于操作�?/span>

 

　　�Q?/span>2�Q?/span>r^.next:=p;

 

　　�Q?/span>3�Q?/span>r^.next:=q;

 

　　�Q?/span>4�Q?/span>IF (q=NIL) THEN r^.next:=p;

 

　　2�Q�假��N���?/span>p和链�?/span>q中的�l�点值都是整�?/span>,且按�l�点值的递增�ơ序链接��h��的带表头�l�点的环形链表。各链表的表头结点的��gؓ(f��)max,且链表中其他�l�点的值都���于max�Q�在�E�序中取max�?/span>9999。在各个链表中，每个�l�点的值各不相同，但链�?/span>p和链�?/span>q可能有值相同的�l�点�Q�表头结炚w��外）。下面的�E�序���链�?/span>q合�ƈ到链�?/span>p中，使得合�ƈ后的链表是按�l�点值递增�ơ序链接��h��的带表头�l�点的环形链表，且链表中各个�l�点的值各不相同。请在划�U�处填上适当内容�Q�每个框只填一个语句或一个表辑ּ��Q�链表的�l�点�c�d��如下

 

　　TYPE nodeptr=^nodetype�Q?/span>

 

　　nodetype=RECORD

 

　　data�Q?/span>integer�Q?/span> link�Q?/span>nodeptr;

 

　　END�Q?/span>

 

　　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<q^.link^.data DO (B)___;

 

　　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;�?a target="_blank">复旦大学 1997 五（18分）�?/span>

 

　　【参考答案�?/span>

 

　　A: r^.link^.data<>max AND q^.link^.data<>max

 

　　B: r:=r^.link

 

　　C: q^.link

 

　　D: q^.link

 

　　E: r^.link

 

　　F: r^.link

 

　　G: r:=s�Q�或r:= r^.link�Q?/span>

 

　　H: r:=r^.link

 

　　I: q^.link:=s^.link