ASD ew( 06 2005 2

3. (2+1+2) Trójkąt Sierpińskiego.

Dla dowolnego n i k , n > k, współczynnik dwumianowy Newtona (n//k) wyraża się wzorem (n//k) = n!/(k!(n-k)!). Wiedząc, że (n//k) = (n-l//k) + (n-l//k-l), możemy zdefiniować następującą funkcję rekurencyjną P(ij) pozwalającą obliczyć dowolny współczynnik Newtona:

P(n.n) = 1, P(n,0) = 1. dla dowolnego n naturalnego, P(n, k) = P(n-l,k) + P(n-1, k-1) dla n>k. Zadanie właściwe:    \

(a)    Napisz algorytm, który dla dowolnie danych n i k odpowiada na pytanie, czy liczba P(n,k) jest parzysta czy nieparzysta.

(b)    Wyjaśnij ideę działania Twojego algorytmu.

(c)    Oszacuj jego koszt.

4. (2+1+2+1)

(a)    Przedstaw kolejne etapy tworzenia drzewa BST w wyniku kolejnego wstawienia elementów': 4,6.1,5,7,8 do początkowo pustego drzewa BST (zakładamy, że zastosowano algorytm insert).

(b)    Czy jest to drzewo wyważone? Odpowiedź uzasadnij.

(c)    Przedstaw kolejne etapy tworzenia drzewa AVL przez kolejne wstawianie (algorytm insert dla AVL) elementów 6, 4, 1, 5, 7, 8 do początkowo pustego drzewa.

(d)    Porównaj koszt wstawienia jednego elementu do drzewa BST o n elementach i koszt wstawienia jednego elementu do drzewa AVL o n elementach.