alg2

NAZWISKO:

IMIĘ:

DATA:

Sprawdzian nr 2 z algorytmów i struktur danych. Każde z poniższych zdań jest punktowane w skali 0-10.

1.    Podaj definicję drzewa o typie bazowym TB.

2.    Jaka jest różnica pomiędzy kolejką LLFO, a kolejką FIFO?

3.    Przeprowadź las złożony z dwóch drzew uporządkowanych w drzewo binarne:

4. Oblicz ile wynosi złożoność obliczeniowa następującego algorytmu. Wskazówka: załóz. że drzewo ma n węzłów.

Dune: zmienna drzewo wskazująca korzeń drzewa BDW. element poszukiwany x

Wynik: wskaźnik na węzeł zawierający x albo nil. jeśli nic znaleziono t

1: functlon Szukaj (drzewo: DrzewoBin; x : integer): DrzewoBin;

begin

(czy drzewo istnieje}

(jeśli x jest mniejsze}

(szukaj na lewo}

(jeśli x jest większe}

(szukaj na prawo}

(x znalezione. KONIEC}

(x nie ma w drzewie. KONIEC}

if drzewo <> nil then if x < drzewot.elem then Szukaj := Szukaj (drzewoT.lewy, x) else

If x > drzewotelem (hen Szukaj := Szukaj (drzewo?.prawy.x) else

Szukaj := drzewo

else

Szukaj := nil end;

5. Oblicz ile wynosi złożoność obliczeniowa następującej procedury:

procedurę Proc (n:integer) begin

if n > 0 then begin writeln (‘x’)

Proc (n-2) writeln ('*’):

Proc (n-2) end end