Algorytmy i struktury danych.

Zadania z egzaminu (dr. J. Ratajczak)

1. Scharakteryzuj drzewo BST (budowa węzła, definicję drzewa BST, operacje wykonywane na drzewie i ich złożoność, wady i zalety w porównaniu z innymi strukturami danych, przeznaczenie drzewa).

2. Napisz procedurę, która wstawi nowy rekord osoby do uporządkowanego wg. nazwiska pliku elementowego.

3. Napisz procedurę, która podzieli (niszcząc ją) prostą, jednokierunkową listę rekordów o początku poc na dwie listy (a i b), zawierające: lista pierwsza - rekordy z pierwszej połowy poc i lista druga - rekordy z drugiej połowy listy poc.

4. Omów algorytm sortowania MergeSort (zasadę, cechy, przydatność do sortowania określonych struktur danych).

5. Argumentem funkcji F jest adres korzenia drzewa BST. Podać słownie co oblicza funkcja F (jaki jest sens wyniku, a nie jak działa).
   
   FUNCTION f(t:wsk):word;
   begin
   if t=nil then f:=0 else f:=1+max(f(t^.l), f(t^.p))
   end.
   
   FUNCTION max(a, b:word):word;
   begin
   if a>b then max:=a else max:=b
   end;
   

6. Dla danej listy sąsiedztwa grafu nieskierowanego:
   A->B,C B->A,D,E C->A,F D->B,E,G E->B,D,F F->C,E,G G->D,F

1. narysować ten graf,

2. ponumerować węzły w kolejności ich odwiedzania przy przechodzeniu grafu wszerz (BSF). (wierzchołkiem startowym jest A)

---