主题:PASCAL提高组模拟试题-完善程序
求出一棵树的深度和宽度。例如有如下的一棵树:
其树的深度为从根结点开始到叶结点结束的最大深度,树的宽度为同一层上结点数的最大值。在上图中树的深度为4,宽度为3。
用邻接表来表示树,上图中的树的邻接表示如下:
1 2 3 4 0 0
2 0 0 0 0 0
3 5 0 0 0 0
4 6 0 0 0 0
5 0 0 0 0 0
6 7 0 0 0 0
7 0 0 0 0 0
程序清单
PROGRAM NOI00_6;
VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY[1..20,1..6]OF INTEGER;
Q:ARRAY[1..100,0..6] OF INTEGER; D:ARRAY[0..20]OF INTEGER;
BEGIN
FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=O;
FOR J:=1 TO 14 DO TREE[J,1]:=J;
TREE[1,2]:=2; TREE [1,3]:=3; TREE[1,4]:=4; TREE[2,2]:=5;
TREE[2,3]:=6; TREE [3,2]:=7; TREE[3,3]:=8; TREE[4,2]:=9;
TREE[4,3]:=10; TREE[4,4]:=11; TREE[7,2]:=12;
TREE[7,3]:=13; TREE[13,2]:=14;
SP1:=1; SP2:=1;
FOR I:=1 TO 6 DO Q[1,I]:=TREE[1,I];
Q[1,0]:=1;
WHILE( ① ) DO
BEGIN
L:=( ② ); J:=2;
WHILE( ③ )DO
BEGIN
SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J];
FOR I:=2 TO 6 DO
Q[SP2,I]:=TREE[Q[SP1,J],I];
J:=J+1
END;
SP1:=SP1+1
END;
WRITELN( ④ )
FOR I:=0 TO 20 DO D[I]:=0;
FOR I:=1 TO SP2 DO
D[Q[I,0]]:=( ⑤ )
MAX:=D[1];
FOR I:=2 TO 20 DO
IF D[I]>MAX THEN MAX:=D[I];
WRITELN(MAX);
READLN;
END.
其树的深度为从根结点开始到叶结点结束的最大深度,树的宽度为同一层上结点数的最大值。在上图中树的深度为4,宽度为3。
用邻接表来表示树,上图中的树的邻接表示如下:
1 2 3 4 0 0
2 0 0 0 0 0
3 5 0 0 0 0
4 6 0 0 0 0
5 0 0 0 0 0
6 7 0 0 0 0
7 0 0 0 0 0
程序清单
PROGRAM NOI00_6;
VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY[1..20,1..6]OF INTEGER;
Q:ARRAY[1..100,0..6] OF INTEGER; D:ARRAY[0..20]OF INTEGER;
BEGIN
FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=O;
FOR J:=1 TO 14 DO TREE[J,1]:=J;
TREE[1,2]:=2; TREE [1,3]:=3; TREE[1,4]:=4; TREE[2,2]:=5;
TREE[2,3]:=6; TREE [3,2]:=7; TREE[3,3]:=8; TREE[4,2]:=9;
TREE[4,3]:=10; TREE[4,4]:=11; TREE[7,2]:=12;
TREE[7,3]:=13; TREE[13,2]:=14;
SP1:=1; SP2:=1;
FOR I:=1 TO 6 DO Q[1,I]:=TREE[1,I];
Q[1,0]:=1;
WHILE( ① ) DO
BEGIN
L:=( ② ); J:=2;
WHILE( ③ )DO
BEGIN
SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J];
FOR I:=2 TO 6 DO
Q[SP2,I]:=TREE[Q[SP1,J],I];
J:=J+1
END;
SP1:=SP1+1
END;
WRITELN( ④ )
FOR I:=0 TO 20 DO D[I]:=0;
FOR I:=1 TO SP2 DO
D[Q[I,0]]:=( ⑤ )
MAX:=D[1];
FOR I:=2 TO 20 DO
IF D[I]>MAX THEN MAX:=D[I];
WRITELN(MAX);
READLN;
END.