Egzamin 2005/06 (09.02.2007)#

Zadanie 1 [11 punktów]#

Słowa kluczowe: max, asymptotycznie optymalny

W tablicy a[1..n] zapisano przesunięty cyklicznie, rosnący ciąg liczb całkowitych.

  1. (6 punktów) Zaproponuj algorytm, który wyznaczy największy element w tablicy a i zrobi to w sposób optymalny, tzn. minimalizujący w pesymistycznym przypadku liczbę porównań pomiędzy elementami ciągu

  2. (5 punktów) Uzasadnij optymalność swojego rozwiązania.

Zadanie 2 [12 punktów]#

Słowa kluczowe: struktury danych, AVL

  1. (6 punktów) Ile wynosi wysokość AVL-drzewa powstałego w wyniku wstawienia do pustego początkowo drzewa kolejno liczb \(1, 2,\ldots, n\)?

  2. (6 punktów) Dla \(n>2\) podaj dwie inne permutacje liczb \(1, 2,\ldots, n\) dające takie samo AVL-drzewo jak to, o którym mowa w pytaniu a).

Uzasadnij poprawność swoich odpowiedzi.

Zadanie 3 [12 + 12 (bonus)]#

Dane jest n-wierzchołkowe, ukorzenione drzewo T – dla każdego wierzchołka znana jest lista jego dzieci oraz dany jest korzeń r. Z każdego liścia w drzewie wychodzi ścieżka w kierunku korzenia, która nie musi się kończyć w korzeniu. Ścieżki są opisane za pomocą wyroczni \(O(w, l)\), która odpowiada na pytanie: Czy węzeł w należy do ścieżki zaczynającej się w liściu l? Zaprojektuj efektywne algorytmy:

  1. (12 punktów) sprawdzający, czy wszystkie ścieżki razem pokrywają całe drzewo,

  2. (12 punktów - bonus) wyznaczający dla każdego liścia koniec ścieżki o porzątku w tym liściu.

Uzasadnij poprawność zaproponowanych rozwiązań i dokonaj analizy złożoności obliczeniowej zaprojektowanych algorytmów.

Zadanie 4 [5 punktów]#

Słowa kluczowe: grafy

Dany jest graf niezorientowany \(G=(V, E)\) oraz funkcja \(f: V\rightarrow \{1,\ldots,k\}\).

Opracuj strukturę danych udostępniającą następujące operacje:

  • Buduj(G, f):: tworzy strukturę danych na podstawie grafu G i funkcji f.

  • Odległość(v, k):: zwraca odległość od v do najbliższego wierzchołka w takiego, że f(w)=k

  • Ścieżka(v, k):: zwraca najkrótszą ścieżkę z v do wierzchołka w, takiego, że f(w)=k.

Przy ocenie Twojego rozwiązania będą brane pod uwagę:

  • czas przetwarzania zapytań Odległość i Ścieżka,

  • czas działania procedury Buduj,

  • rozmiar struktury danych,

w powyższej kolejności (tzn. należy dążyć do uzyskania jak najmniejszego czasu przetwarzania zapytań, a następnie jak najmniejszego czasu budowy struktury, następnie jak najmniejszego rozmiaru). Przyjmujemy, że k<<n.