PP2 GR.B

1. Typ bazowy drzewa BST zawiera dwa wskaźniki left i right typu Pbst oraz pole data typu byte. Dany jest wskaźnik na korzeń drzewa. Napisz funkcję iteracyjną z parametrem, która zwróci największą wartość w drzewie.

2. W drzewie binarnym narysowanym niżej każdy węzeł posiada trzy wskaźniki: right - na prawego potomka, left - na lewego potomka, parent - na przodka. Informacja w węźle zapisana jest w polu data typu byte. Ustal wartości podanych wyrażeń i skróć je. Przyjmij że wskaźnik p wskazuje na węzeł zaznaczony strzałką.

p^.parent^.parent^.left^.right^.parent^.parent^.right^.right^.data

Wartość: .............. . Skrócone wyrażenie: .................................................................................. .

p^.parent^.left^.parent^.right^.parent^.left^.parent^.parent^.left^.parent^.data

Wartość: .............. . Skrócone wyrażenie: .................................................................................. .

3. Załóżmy, że w Pascalu "popsuł się" operator mod. Napisz funkcję rekurencyjną, która zastąpi ten operator. Przyjmijmy, że funkcja będzie operowała na liczbach typu byte.

4. Poniżej przedstawiono trzy drzewa binarne. Zdecyduj czy są one drzewami BST, a jeśli nie to podaj, które z wartości wierzchołków należy zamienić miejscami, aby drzewa stały się drzewami BST.

To jest / nie jest drzewo BST. To jest / nie jest drzewo BST. To jest / nie jest drzewo BST.

............................................... ............................................... ...............................................

............................................... ............................................... ...............................................

............................................... ............................................... ...............................................

5. Dana jest następująca funkcja rekurencyjna:

function test(a,b:word):word;

begin

if a+b<>2 then

test:=test(a+1,b)+test(a,b+1)

else

test:=1;

end;

Narysuj drzewo rekurencji dla tej funkcji dla a=0 i b=0 oraz podaj wynik tej funkcji dla tych argumentów: .............. .

6. Typ bazowy kolejki zawiera pole data typu real i wskaźnik wsk typu PQueue. Dany jest wskaźnik na pierwszy element kolejki. Napisz procedurę rekurencyjną z parametrem, która usunie wszystkie elementy kolejki.

7. Po klasie K6 dziedziczą klasy K5 i K4. Po klasie K4 dziedziczą klasy K2 i K1. W programie zdefiniowano wskaźniki

k1 klasy K1, k2 klasy K2 itd. Określ, czy można:

- wskazywać wskaźnikiem k6 obiekt klasy K1: ........... ,

- wskazywać wskaźnikiem k1 obiekt klasy K4: ........... ,

- wskazywać wskaźnikiem k5 obiekt klasy K2: ........... ,

- wskazywać wskaźnikiem k4 obiekt klasy K1: ........... .

Zakładamy, że w programie nie jest wykorzystywany operator @ ani wskaźniki typu pointer.

8. Po klasie K1 dziedziczą klasy K2 i K3. Po klasie K3 dziedziczą klasy K4 i K5, a po klasie K2 klasy K6 i K7. We wszystkich klasach jest zdefiniowana metoda o nazwie metoda1, przy czym w klasach K1 i K2 jest to metoda statyczna, a w pozostałych klasach wirtualna. Jakiej klasy metoda zostanie wywołana metoda jeśli:

- wskaźnikiem klasy K3 wskazywany jest obiekt klasy K4: ........... ,

- wskaźnikiem klasy K1 wskazywany jest obiekt klasy K4: ........... ,

- wskaźnikiem klasy K2 wskazywany jest obiekt klasy K6: ........... ,

- wskaźnikiem klasy K3 wskazywany jest obiekt klasy K5: ........... .

9. Poniżej przedstawiona jest tablica. Uporządkuj wartości elementów tej tablicy tak, aby tworzyły kopiec.

10. Poniżej przedstawione jest drzewo binarne. Wypisz wartości węzłów tego drzewa w porządku inoder, poczynając od korzenia i zmieniając kolejność odwiedzania poddrzew.

Inoder: ........................................................................................................ .

---