Egzamin 2003/04#

Zadanie 1 [10 punktów]#

Słowa kluczowe: grafy

Powiemy, że dwa wierzchołki w grafie są parzysto-odległe wtedy i tylko wtedy, gdy istnieje pomiędzy nimi ścieżka (wierzchołki i krawędzie mogą się powtarzać) o parzystej długości.

  1. [3 punkty] Udowodnij, że relacja parzystej odległości jest relacją równoważności

  2. [7 punktów] Zaproponuj efektywny algorytm, który dla danego grafu \(G\) obliczy klasy abstrakcji relacji parzystej odległości. Uzasadnij poprawność zaproponowanego algorytmu i przeanalizuj jego złożoność - czasową i pamięciową.

Zadanie 2 [8 punktów]#

Słowa kluczowe: struktury danych; AVL

Wykaż, że istnieje AVL-drzewo o wysokości 10 (wysokość to długość najdłuższej ścieżki od korzenia do węzła wewnętrznego), które zawiera co najmniej 1364 węzłów zewnętrznych takich, że umieszczenie w każdym z nich nowego klucza wymaga wykonania rotacji (pojedynczej lub podwójnej) dla przywrócenia równowagi w drzewie. Uwaga: za wskazanie tylko drzewa o więcej niż 1200 węzłach zewnętrznych o tej własności można otrzymać 4 punkty.

Zadanie 3 [12 punktów]#

Słowa kluczowe: statystyki pozycyjne, asymptotycznie optymalny

Dane są dwie uporządkowane rosnąco tablice \(A[1..n]\) i \(B[1..n]\) zawierające \(2n\) różnych elementów oraz liczba całkowita \(k\), \(1 \leq k \leq 2n\).

  1. [6 punktów] Zaproponuj algorytm, który za pomocą możliwie małej liczby porównań pomiędzy elementami zbioru \(A \cup B\) znajdzie takie dwa indeksy \(a\) i \(b\), że \(A[1..a] \cup B[1..b]\), to podzbiór \(k\) najmniejszych elementów zbioru \(A \cup B\). Uzasadnij poprawność swojego algorytmu i przeanalizuj liczbę porównań w pesymistycznym przypadku.

  2. [6 punktów] Jaka jest dolna granica na liczbę porównań w tym zadaniu? Odpowiedź uzasadnij.

Zadanie 4 [10 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie

Zaprojektuj strukturę danych umożliwiającą efektywne wykonywanie następujących operacji na permutacji \(p[1..n]\) liczb \(1..n\):

  1. \(Inicjalizacja\):: dla każdego \(i = 1, 2, \cdots, n : p[i] = i\). Ta operacja jest wykonywana tylko raz jako pierwsza.

  2. \(Zamien(i, j)\):: jeśli \(i\) oraz \(j\) należą do różnych cykli permutacji \(p\), to zamień wartości \(p[i]\) i \(p[j]\).

  3. \(Dlugosc(i)\):: podaj długość cyklu w permutacji \(p\) zawierającego \(i\).

Uzasadnij poprawność i przeanalizuj złożoność poszczególnych operacji w zaproponowanym rozwiązaniu.