9988996101

type

drzewo=“wezel; wezel=record

klucz:integer; lewy,prawy:drzewo end;

Napisać w języku Pascal funkcję ścieżka(d: drzewo)ńntehger, która oblicza sumę kluczy na ścieżce o maksymalnej długości w tym drzewie; np. dla drzewa

3

/ \

1    4

/ \ \

15    9

/

2

funkcja powinna zwrócić wartość 9.

Egzamin ze Wstępu do Informatyki. 21 maja 1998

Zadanie 1

Węzeł drzewa binarnego zdefiniowany jest deklaracją type

wsk=''elem;

elem=record

klucz:integer; ldow.pdow:wsk; end;

Napisać w języku Pascal funkcję: function bst(t:wsk):boolean, której wartością jest true, jeśli t jest binarnym drzewem poszukiwań, a false w przeciwnym przypadku.

Zadanie 2

Węzeł drzewa binarnego zdefiniowany jest jak w zadaniu 1. Napisać w języku Pascal procedurę: procedurę dołącz(tl,t2:wsk), gdzie 11 jest binarnym drzewem poszukiwań, a t2 jest dowolnym drzewem binarnym. W wyniku wykonania dołącztl jest korzeniem drzewa binarnych poszukiwań uzyskanym w wyniku dołączenia elementów drzewa t2 do drzewa t\.

Zadanie 3

Lista jednokierunkowa zbudowana jest z elementów zadeklarowanych jako: type

wsk='^,elem;

elem=record

id:integer; nastwsk end;

15