Egzamin poprawkowy 2006/07#
(uwaga! w pliku Pdf jest niepoprawna data!)
Zadanie 1 (10 punktów)#
Tablica A[1..n] jest 2-posortowana jeśli dla każdego \(i=1,\ldots,n-2\) zachodzi \(A[i] \le A[i+2]\).
Zaprojektuj efektywny (w sensie liczby porównań elementów tablicy) algorytm sortujący 2-posortowaną tablic rozmiaru n, oraz
pokaż, że zaproponowany algorytm jest optymalny.
Uwaga: W tym zadaniu analiza złożoności czasowej powinna być wykonana dokładnie, a nie tylko asymptotycznie. Złożoność pamięciowa nie jest istotna.
Zadanie 2 (10 punktów)#
Dana jest n–elementowa lista jednokierunkowa L. Każy element listy \(e\in L\) przechowuje wskaźnik do swojego następnika next (nil w przypadku elementu ostatniego). Wzbogać każdy element listy o jeden dodatkowy wskaźnik tak, aby można było dla dowolnego k efektywnie znajdować k–ty element listy. Ocenie podlega poprawność i efektywność algorytmu szukania k–tego elementu, jak również algorytmu obliczającego dodatkowe wskaźniki.
Zadanie 3 (10 punktów)#
Zaprojektuj strukturę danych umożliwiającą wykonywanie następujących operacji na początkowo pustym zbiorze punktów w \(R^3\).
Dodaj(p):: dodaje punkt p do zbioru,
Usuń(p):: usuwa punkt p ze zbioru,
Max_Odl():: zwraca najiększą odległość między punktami zbioru.
Odległość między punktami definiujemy następująco:
\(d((x_1,y_1,z_1), (x_2, y_2, z_2)) = |x_1-x_2| + |y_1-y_2| + |z_1 - z_2|\)
Zadanie 4 (10 punktów)#
Dany jest graf skierowany G=(V, E) oraz pewna ścieżka prosta p w G. Zaproponuj strukturę danych, która pozwala odpowiadać na pytania postaci:
Przecina(v, w):: zwraca true wtw, gdy istnieje w G ścieżka skierowana z v do w, przecinająca ścieżkę p (tzn. mająca z nią \(\ge 1\) wierzchołek wspólny).
Uwaga! Ocenie podlega czas odpowiedzi na zapytanie oraz czas budowowania i złożoność pamięciowa zaproponowanej struktury.
Uwaga! Rozwiązania każdego zadania proszę pisać na osobnej i wyraźnie (!) podpisanej kartce.