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

1�Q?/span>PROC ins__linklist(la:linkisttp; i:integer; b:elemtp);

　　{la为指向带头结点的单链表的头指针，本算法在表中�W?/span>i个元素之前插入元�?/span>b}

　　p:=(1) ; j:=(2) ;{指针初始化，j�����数器}

　　WHILE (p<>NIL) AND ((3) ) DO [p:=(4) ; j:=j+1�Q?/span>]

　　{��L���W?/span> i-1 个结�?/span>}

　　IF (p=NIL) OR ((5) )

　　THEN error (�?/span>No this position�?/span>)

　　ELSE [new(s) ; s�?/span>.data:=b; s�?/span>.next:=p�?/span>.next; p�?/span>.next:=s;]

　　ENDP;{ins-linklist}�?a target="_blank">燕山大学 1998 四�?/span>1�Q?/span>15分）�?/span>

　　【参考答案�?/span>

　　(1)la  (2)0 (3)j<i-1 (4)p�?/span>.next (5)i<1

　　2. 已知双链表中�l�点的类型定义�ؓ(f��)�Q?/span>

　　TYPE dpointer=^list;

　　list=RECORD

　　data:integer; left,right:dpointer;

　　END;

　　如下�q�程���在双链表第i个结点（i>=0�Q�之后插入一个元素�ؓ(f��)x的结点，请在�{�案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能�?/span>

　　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�l�点插入到表头后�q�回}

　　ELSE BEGIN p:=head; (2)_______�Q?/span>{在双链表中查扄���i个结�?/span>,�?/span>p所指向}

　　WHILE ((p<>NIL) AND (j<i)) DO BEGIN j:=j+1; (3) _ END;

　　IF p<>NIL THEN

　　IF �Q?/span>p^.right=NIL�Q?/span>

　　THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END

　　ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END

　　ELSE writeln(�?/span>can not find node!�?/span>)

　　END

　　END;�?a target="_blank">厦门大学 2002 �?/span> �Q?/span>12分）�?/span>

　　【参考答案�?/span>

　　(1)head^.left:=s �?/span>head的前驱指针指向插入结�?/span>

　　(2)j:=1;

　　(3)p:=p^.right ∥工作指针后�U?/span>

　　(4)s^.left:=p

　　(5)p^.right^.left:=s; �?/span>p后��的前驱是s

　　(6)s^.left:=p;