数据�l�构�W�六章填�I�题及答案[15]_跨考网

1. 判断带头�l�点的双向��@环链�?/span>L是否对称相等的算法如下所�C�，请在划线处填上正���的语句

　　FUNCTION equal(l:pointer) :boolean;

　　VAR p,q:pointer; result: Boolean;

　　BEGIN result =true ; p:= l^.link; q:=l^.pre ;

　　WHILE (p<>q) AND ((1)_______)DO

　　IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END�Q?/span>

　　ELSE result=false ;

　　return(result);

　　END; �?a target="_blank">华南师范大学 2000�q?/span> 五�?/span>1 ( 9�?/span>)�?/span>

　　【参考答案�?/span>

(1)     result; (2)p:=p^.link; (3) q:=q^.pre �Q�（�Q�）�Q�３�Q�顺序可变）

2�Q�下�q�是一个由二叉树的前序序列和中序序列构造该二叉树的���法�Q�其中，数组A[1..n]存放前序序列�Q�数�l?/span>B[1..n]存放中序序列�Q?/span>s为根�l�点指针�Q?/span>i,j为树s的前序序列在A[1..n]中的开始位�|�和�l�束位置�Q?/span>x,y为树s的中序序列在B[1..n]中的开始位�|�和�l�束位置。所生成的二叉树采用二叉链表存储�l�构�Q�其�l�点的�Ş式�ؓ�Q?/span>lchild,data,rchild�Q�。请在算法的�I�框中填入适当语句�Q���其成��Z��个完整的���法�?/span>

　　PROCEDURE creatBT(i,j,x,y: integer; VAR s: link);

　　VAR k,L: integer;

　　BEGIN s:= NIL;

　　IF(1)__THEN

　　BEGIN new (s); s^.data:=a[i]; k:=x;

　　WHILE(2)_______DO k:=k+1;

　　L:= (3)____;

　　IF k=x THEN s^.lchild:=NIL; ELSE(4)_______;

　　IF k=y THEN s^.rchild:=NIL; ELSE(5)_______�Q?/span>

　　END

　　END; �?a target="_blank">西安交通大�?/a> 1996 五�?/span>1 (9�?/span>)�?/span>

　　【参考答案�?/span>

　　(1)(i<=j) AND (x<=y) (2)A[i]<>B[k] (3)k-x

　　(4)creatBT(i+1,i+L,x,k-1,s^.lchild) (5) creatBT(i+L+1,j,k+1,y,s^.rchild)