21 maja 1998

Zadanie 1 W_{}ezeł drzewa binarnego zdefiniowany jest deklaracj _{}a

 type
   wsk=^elem;
   elem =record
          klucz: integer;
          ldow,pdow: wsk
         end;

Napisać w pascalu funkcj_{}e: function bst(t:wsk):boolean, której wartości _{}a jest true, jeśli t jest binarnym drzewem poszukiwań, a false w przeciwnym przypadku.

Zadanie 2 W_{}ezeł drzewa binarnego zdefiniowany jest jak w zadaniu 1. Napisać w pascalu procedur_{}e: procedure doł _{}acz(t1,t2:wsk), gdzie t1 jest binarnym drzewem poszukiwań, a t2 jest dowolnym drzewem binarnym. W wyniku wykonania doł _{}acz t1 jest binarnym drzewem poszukiwań uzyskanym w wyniku doł _{}aczenia elementów drzewa t2 do drzewa t1.

Zadanie 3 Lista jednokierunkowa zbudowana jest z elementów zadeklarownych jako:

 type
   wsk=^elem;
   elem =record
          id: integer;
          nast: wsk
         end;

Napisać w pascalu funkcj_{}e: function znajdz(l1,l2,l3:wsk):integer. Listy l1,l2,l3 s _{}a listami osób, których unikalne identyfikatory s _{}a umieszczone w polu id. Listy s _{}a posortowane rosn _{}aco wzgl_{}edem pola id. Wartości _{}a funkcji znajdz jest identyfikator osoby, która wyst_{}epuje na wszystkich trzech listach lub 0, jeśli takiej osoby nie ma.

Zadanie 4 Typ graf jest tablic _{}a list jednokierunkowych.

type
   wsk=^elem;
   elem =record
          id: integer;
          nast: wsk
         end;
   graf=array[1..N] of wsk;

N jest stał _{}a zadeklarowan _{}a w programie głównym. Napisać funkcj_{}e: function rl(A:graf):boolean. A[i] jest list _{}a w_{}ezłów, do których wychodzi strzałka z w_{}ezła i. Wartości _{}a funkcji jest true, jeśli zbiór w_{}ezłów [1..N] można podzielić na dwa rozł _{}aczne podzbiory P_{1} i P_{2} takie, że

1. jeśli x ∈ P_{1}, to z x wychodzi strzałka co najwyżej do w_{}ezła y ∈ P_{2};

2. jeśli x ∈ P_{2}, to z x nie wychodzi żadna strzałka.

W przeciwnym przypadku wartości _{}a funkcji jest false.