Zestaw I

1. Napisz funkcję Wsk usun(Wsk &poc, Wsk x) usuwającą z prostej dwukierunkowej listy o początku poc element występujący po elemencie x (x albo jest równe NULL - co oznacza usuwanie z początku listy, albo jest adresem istniejącego elementu listy) i zwracającą jego adres.

2. Dane są następujące definicje:
   const int MDL=....; //maksymalna długość klucza
   const int MW=.....; // pozycja klucza ma wartość od 0 do MW
   struct Wez
   {bool jest; //True jeśli taka wartość występuje w drzewie
   Wez *adre[MW+1];} //tablica adresów potomków
   typedef Wez *Wsk;
   
   Napisz funkcję obliczającą liczbę kluczy umieszczonych w drzewie pozycyjnym o korzeniu t.

3. Co robi następująca funkcja (jaki jest efekt jej działania i co jest wynikiem - nie opisywać jak działa) jeśli t jest adresem drzewa BST?
   int f(Wsk t) {if(t) {if(t->l) return f(t->l) + f(t->p); return (t->p ? f(t->p):1);} return 0;}

4. Do podanego poniżej drzewa AVL wstaw węzeł o kluczu 15. Zaznacz wykonywane rotacje:
   

	8
2			20
		10		40

5. Z podanego poniżej B-drzewa usuń węzeł o kluczu 1. Skomentuj krótko wykonywane działania.
   

									14	30
		6								22								34
1				8	10	12		16	18			24				32				36

Zestaw II

1. Narysuj drzewo AVL (BST zrównoważone względem wysokości poddrzew) uzyskane przez kolejne wstawianie kluczy: 30, 10, 60, 5, 50, 80, 54, 56, 58. Wystarczy pokazać te sytuacje, w których odbywało się wyważanie drzewa. Jak będzie wyglądało to drzewo po usunięciu klucza 10?

2. Scharakteryzuj (tzn. podaj zasady budowy stogu zupełnego, opis algorytmu, przydatność do sortowania tablic i list, złożoności: obliczeniowe (optymistyczną, średnią i pesymistyczną - dla jakich ciągów zachodzą) i pamięciową oraz stabilność) algorytmu sortowania przez kopcowanie HeapSort.

3. Napisz funkcję obliczającą liczbę liści (węzłów, które nie mają potomków) w drzewie BST o podanym korzeniu t.

4. Dane są następujące deklaracje: struct Elem {int kl; Elem *pop; Elem *nast.}; typedef Elem *Wsk; Napisz funkcję void usun_przed(Wsk &a, Wsk &x, Wsk przed) usuwającą z listy o początku a element bezpośrednio poprzedzający element o adresie przed (na pewno jest na liście) i umieszczającą jego adres w zmiennej x. Uwaga: usun przed NULL oznacza usuwanie z końca listy.

5. Dane są następujące definicje: struct Elem {int kl; Elem * nast.}; typedef Elem *Wsk; void f(Wsk &a, int k, Wsk &x) {if(k) f(a->nast, --k,x); else {x=a; a=a->nast; x->nast=NULL;}}; Jaki będzie efekt działania tej funkcji po jej wywołaniu f(poc, k, x), gdzie poc - początek jednokierunkowej listy, k - liczba całkowita, x - wskaźnik o nieistotnej wartości? Jakie warunki musi spełniać k, aby funkcja działała prawidłowo?

Zestaw III

1. Dany jest adres początku prostej jednokierunkowej listy studentów (nazwisko i ocena). Napisz funkcję, której wynikiem jest liczba kolejnych studentów z początku listy mających ocenę <3.0.

2. Dany jest adres początku prostej jednokierunkowej listy studentów: nazwisko (do 30 znaków), imię (do 20 znaków) i ocena (liczba rzeczywista). Napisz funkcję zwracającą adres początku nowej listy zawierającej nazwiska tych studentów, którzy mają ocenę >-3.0. Nie wolno zniszczyć listy pierwotnej.

3. Napisz, co oblicza podana funkcja (t jest adresem korzenia drzewa BST).
   int f(Wsk t, float x) {int pom=0; if(t) {if(t->wart==x) pom++; else if(t->wart<x) pom+=f(t->prawe,x); pom+=f(t->lewe,x); return pom;}}

4. a) Do podanego poniżej drzewa AVL wstaw klucz 26,
   b) Z podanego poniżej drzewa AVL usuń klucz 40.
   

				15
	4							30
2			8			22				60
		6			20		28		40
						25

5. a) Do podanego poniżej B-drzewa wstaw klucz 9,
b) Z podanego poniżej B-drzewa usuń klucz 60.

				30
10	14	18	23					50	60

Zestaw IV

1. Napisz funkcję wpisującą każdemu węzłowi (x) drzewa BST o korzeniu k, wysokość poddrzewa, którego korzeniem jest x. UWAGA: Nie należy używać zmiennych globalnych.

2. Scharakteryzuj - tzn. opisz algorytm, podaj: złożoności: pamięciową i obliczeniową (optymistyczną, średnią i pesymistyczną - dla jakich danych zachodzą), czy algorytm jest stabilny - sortowanie przez wybór dla tablic „SelectSort”.

3. Zbuduj drzewo AVL wstawiając do niego kolejno klucze: 9, 3, 15, 7, 10, 12, 4, 20, 2
   - jak będzie wyglądało to drzewo po usunięciu węzła 9 (opisz jak to się robi),
   - jaki wydruk uzyskamy po uruchomieniu dla tego drzewa funkcji druk?
   int druk(Wsk t) {if(t) {druk(t->p); druk(t->l); cout<<t->kl;}}

4. Narysuj B-drzewo rzędu 1 (węzeł mieści 2 elementy, czyli może mieć do 3 potomków) powstałe przez wstawianie elementów: 1, 2, 3, 7, 5, 6, 4. Podaj postać drzewa po usunięciu klucza 1.

Zestaw V

1. Jakie struktury danych wykorzystuje się do przechowywania elementów kolejek priorytetowych?

2. Napisz funkcję obliczającą liczbę węzłów drzewa BST o podanym korzeniu t, których klucze są większe od podanej wartości x. Nie przechodź całego drzewa jeśli to nie jest konieczne.

3. Dane są następujące deklaracje: struct Elem {int kl; Elem *nast.}; typedef Elem *Wsk; Napisz funkcję Wsk cykl(unsigned int N), tworzącą jednokierunkową listę cykliczną zawierającą kolejne klucze od 1 do N. Wynikiem funkcji ma być adres początku listy.

4. Dane są następujące definicje: struct Elem {int kl; Elem *nast.}; typedef Elem *Wsk;
   void f(Wsk &a, Wsk x) {if(a) if(a!=x) f(a->nast., x); else a=a->nast.;}
   Jaki będzie efekt działania tej funkcji po wywołaniu f(poc,x), gdzie poc - początek jednokierunkowej listy, x -wskaźnik do pewnego elementu.

5. a) do podanego poniżej drzewa AVL wstaw węzeł o kluczu 10.
   b) z podanego poniżej drzewa ACL usuń węzeł o kluczu 30.
   

			16
		4				30
	2			8			40
1			6		12

Zestaw VI

1. Napisz treść funkcji Podziel, która otrzymuje prostą, jednokierunkową listę liczb całkowitych o początku a, a jej wynikiem są dwie listy: a - zawierająca elementy o wartościach parzystych i b - pozostałych.

2. Scharakteryzuj tzn. opisz algorytm, podaj złożoności: pamięciową i obliczeniową (optymistyczną, średnią i pesymistyczną) - dla jakich danych zachodzą, czy algorytm jest stabilny - sortowanie przez wybór dla list "SelectSort".

3. Napisz funkcję Maks zwracającą największy element prostej jednokierunkowej listy. Funkcja powinna usunąć znaleziony element z listy.

4. Napisz funkcję obliczającą wysokość drzewa BST o korzeniu k.

5. Zbuduj drzewo AVL wstawiając do niego kolejno klucze: 9, 4, 7, 13, 6, 19, 15, 1, 10

---