Ctrl+K

Egzamin 2008/09

Egzamin 2008/09#

(uwaga! w pliku Pdf i Rtf jest niepoprawna data!)

Zadanie 1#

Słowa kluczowe: struktury danych, BST, wzbogacanie

Dane jest \(n\)-węzłowe drzewo binarne z \(n\) różnymi kluczami w węzłach. Rozważamy następujący algorytm rekurencyjny przywracania porządku kopcowego w takim drzewie:

  1. Jeśli drzewo składa się z co najwyżej jednego węzła, to porządek kopcowy jest przywrócony. W przeciwnym przypadku znajdujemy w drzewie węzeł z najmniejszym kluczem i zamieniamy klucze z korzenia i ze znalezionego węzła; rekurencyjnie przywracamy porządek kopcowy w lewym i prawym poddrzewie korzenia.

  2. Przyjmijmy, że węzeł z najmniejszym kluczem znajdujemy jedną z metod obchodzenia drzewa (preorder, inorder lub postorder).

    1. Jaka jest (asymptotycznie) pesymistyczna złożoność przywracania porządku kopcowego wyrażona jako funkcja \(n\)?

    2. Jaka jest złożoność powyższego algorytmu dla drzewa o wysokości \(\lceil \log n \rceil\)?

  3. Zaproponuj strukturę danych, które umożliwi efektywne wykonywanie następujących operacji na \(n\)-węzłowym drzewie binarnym:

    1. \(Min(v) ::\) znajdź w poddrzewie o korzeniu \(v\) węzeł z najmniejszym kluczem;

    2. \(Exch(u, v) ::\) zamień klucze z węzłów \(u\) i \(v\).

Zadanie 2#

Słowa kluczowe: struktury danych

Zaprojektuj strukturę danych umożliwiającą wykonywanie następujących operacji na \(n\)-wierzchołkowym lesie \(G\) (grafie nieskierowanym bez cykli):

  1. \(Init(G) ::\) utwórz strukturę danych dla grafu \(G\) zadanego przez listy sąsiedztwa (możesz przyjąć \(V(G) = \{1, 2, \cdots, n\}\);

  2. \(Remove(u, v) ::\) usuń krawędź \(\{u, v\}\) z grafu \(G\);

  3. \(Path(u, v) ::\) sprawdź, czy w grafie \(G\) istnieje ścieżka pomiędzy wierzchołkami \(u\) i \(v\).

    1. Zaprojektuj takie rozwiązanie, w którym całkowity koszt wykonania operacji \(Init\) i \(k\) operacji \(Remove/Path\) nie przekracza \(O(k + n \log n)\).

    2. Załóżmy, że cały ciąg \(k\) operacji jest dany ,,off line” (tzn. jest znany w całości z góry), a celem jest obliczenie wyników wszystkich operacji \(Path\). Zaproponuj algorytm, który zrobi to w czasie \(o(n \log n)\), gdy \(k = O(n)\).

Zadanie 3#

Słowa kluczowe: struktury danych, wzbogacanie

Zaproponuj efektywną strukturę danych, z pomocą której można wykonywać następujące operacje na dynamicznym zbiorze \(S\) odcinków domkniętych na prostej rzeczywistej:

  1. \(Init(S) ::\) utwórz pusty zbiór odcinków (wykonywana tylko raz na początku algorytmu);

  2. \(Add(S, I) ::\) dodaj do zbioru \(S\) nowy odcinek \(I\), ale tylko wtedy, gdy dla każdego odcinka \(J\) z \(S\), odcinek \(I\) ma puste przecięcie z \(J\) lub \(I\) jest zawarty w \(J\) lub \(J\) jest zawarty w \(I\);

  3. \(Delete(S, I) ::\) usuń \(I\) z \(S\);

  4. \(Incl(S, I) ::\) podaj ile odcinków z \(S\) jest zawartych w odcinku \(I\).

Zawartość