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

1. 下面是用c语言�~�写的对不带头结点的单链表进行就地逆置的算法，该算法用L�q�回逆置后的链表的头指针�Q�试在空�~�处填入适当的语句�?/span>

　　void reverse�Q?/span>linklist &L�Q?/span>{

　　p=null�Q?/span>q=L�Q?/span>

　　while�Q?/span>q�Q?/span>=null�Q?/span>

　　{ (1) ; q->next=p�Q?/span>p=q�Q?/span>(2)___ ; }

　　(3)_____;

　　}�?a target="_blank">北京理工大学 2001 �?ji��)�?/span>1 �Q?/span>6分）�?/span>

　　【参考答案�?/span>

　　(1)L=L->next; ∥暂存后�l��?/span>

　　(2)q=L; ∥待逆置�l�点�?/span>

　　(3)L=p; ∥头指针仍�ؓL�?/span>

　　2�Q�下面程序段是逆�{单向循环链表的方法，p0 是原链表头指针，逆�{后链表头指针仍�ؓp0�?/span>

　　�Q�可以根据需要增加标识符�Q?/span>

　　p:= p0; q0:=NIL;

　　WHILE �Q?/span>1�Q?/span>________ DO

　　BEGIN �Q?/span>2�Q?/span>________; �Q?/span>3�Q?/span>________;�Q?/span>4�Q?/span>______;�Q?/span>5�Q?/span>________ END;

　　p^.next:= q0; p0 ^.next:=p; p0:=p;�?a target="_blank">中国人民大学 2000 二�?/span>1�Q?/span>4分）�?/span>

　　【参考答案�?/span>

　　(1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0; (4) q0:= p; (5) p:=r

33�Q�一个无头结点的�U�性链�?/span>(不��@�?/span>)有两个域。数据域data�Q�指针域 next�Q�链�?/span>head�Q�下面算法用read(num)��d��数据�Q�当num���于0�Ӟ��输入�l�束。徏立一个数据以递增序组成的链表�?/span>

　　PROC insert( head, x);

　　{ 在链首�ؓhead的表中按递增序插�?/span>x }

　　new(r);r�Q?/span>.data:=x;

　　IF head=NIL

　　THEN{ head:=(1) _____; r�Q?/span>.next:= (2)________ }

　　ELSE IF (3)___ THEN {r�Q?/span> .next:=head; head:=r]

　　ELSE {p:=head;

　　WHILE (4)___ AND (p�Q?/span>.next�?/span>NIL ) DO[q:=p; (5)___ };

　　IF (6)___ THEN { q�Q?/span> .next:=(7)___; r�Q?/span>.next:= (8)____; }

　　ELSE [p�Q?/span>.next:=(9)____; r�Q?/span>.next:= (10)___; } }

　　ENDP;

　　PROC creat(head);

　　head:= (11)______; read(num);

　　WHILE num>0 DO

　　{ insert(head,num); read(num) }

　　ENDP;�?a target="_blank">南京理工大学 1999 三�?/span>4�Q?/span>11分）�?/span>

　　【参考答案�?/span>

　　(1)r (2)NIL (3)x<head^.data (4)p^.data<x (5)p:=p^.next (6)p^.data>=x; (7)r (8)p (9)r (10)NIL (11)NIL