2. Klasówka 1997/98 (1998-01-09)#
Zadanie 1 (5 punktów)#
Wektorem inwersji dla permutacji \(\pi=(p_1,\ldots,p_n)\) liczb \(\{1,\ldots,n\}\) nazywamy wektor \(\alpha=(a_1,\ldots,a_n)\) taki, że \(a_i=|\{j : j < i\ \wedge\ p_j > p_i\}|\). Zaproponuj i zanalizuj algorytm, który dla danego ciągu liczbowego \(\alpha=(a_1,\ldots,a_n)\) takie, że \(a_i \in \{0,\ldots,i-1\}\), znajduje permutację \(\pi\), dla której \(\alpha\) jest wektorem inwersji.
Zadanie 2 (6 punktów)#
Danych jest n domkniętych odcinków na prostej. Zaprojektuj i zanalizuj algorytm znajdujący liczbę wszystkich par przecinających się odcinków.
Zadanie 3 (3 punkty)#
Jaka jest wysokość B-drzewa o minimalnym stopniu t=2 powstałego w wyniku wstawienia do pustego drzewa kolejnych kluczy \(1,\ldots,1998\)? Odpowiedź uzasadnij.
Zadanie 4 (3 punkty)#
Narysuj AVL-drzewa powstające w wyniku wykonywania na początkowo pustym drzewie ciągu następujących operacji: insert(6), insert(8), insert(5), insert(3), insert(1), insert(7), insert(4), delete(7).
Uwaga: Każde zadanie należy oddać na oddzielnej i podpisanej kartce.