数据�l�构�W�二章填�I�题�?qi��ng)参考答案[6]_跨考网

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

1�Q�阅��M��下算法，填充�I�格�Q���其成为完整的���法。其功能是在一个非递减的顺序存储线性表中，删除所有值相�{�的多余元素�?/span>

 

　　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;�?a target="_blank">同济大学 2000 二�?/span>1 (10�?/span>)�?/span>

 

　　【参考答案�?/span>

 

　　(1)i<=L.last �?/span>L.last 为元素个�?/span>

 

　　(2)j:=j+1 ∥有��g��相等的元�?/span>

 

　　(3)L.elem[j]:=L.elem[i] ∥元素前�U?/span>

 

　　(4)L.last:=j ∥元素个�?/span>

　2�Q�在本题的程序中�Q�函数过�E?/span>Create_link_list(n)建立一个具�?/span>n个结点的环�Ş链表;�E�序�q�程 josephus(n,i,m)对由Create_link_list(n)所建立的具�?/span>n个结点的环�Ş链表按一定的�ơ序逐个输出�q�删除链表中的所有结点，参数 n(n>0)指明环�Ş链表的结点个敎ͼ�参数 i(1<=i<=n)指明起始�l�点�Q�参�?/span> m (m>0)是步长，指明从�v始结�Ҏ(gu��)��前次被删除�ƈ输出的结点之后的�W?/span>m个结点作为本�ơ被输出�q�删除的�l�点。例如，对于下图中具�?/span>6个结点的环�Ş链表�Q�在调用 josephus(6,3,2)后，���输�?/span> 5,1,3,6,4,2 请在横线处填上适当内容�Q�每�I�只填一个语句�?/span>

 

　　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�Q?/span>

 

　　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<n DO

 

　　BEGIN

 

　　FOR i:=1 TO m-1 DO p:=p^.link;

 

　　(E)___; write(q^.data:8); (F)__ ;

 

　　dispose(q); j:=j+1

 

　　END

 

　　END;�?a target="_blank">复旦大学 1997 四（12分）�?/span>

 

　　【参考答案�?/span>

 

　　(A)p^.link:=q;∥拉上链�Q�前驱指向后�l?/span>

 

　　(B)p:=q;∥新的前�?/span>

 

　　(C)p^.link:=head;∥�Ş成��@环链�?/span>

 

　　(D)j:=0; ∥计数器�Q�记被删�l�点

 

　　(E)q:=p^.link∥记下被删结�?/span>

 

　　(F)p^.link=q^.link ∥删除结�?/span>