Ctrl+K

Egzamin 2003/04

Egzamin 2003/04#

Zadanie 1#

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. Udowodnij, że relacja parzystej odległości jest relacją równoważności

  2. 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#

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#

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 liczb całkowita \(k\), \(1 \leq k \leq 2n\).

  1. 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..n] \cup B[1..n]\), to podzbiór \(k\) najmniejszych elementów zbioru \(A \cup B\). Uzasadnij poprawność swojego algorytmu i przeanalizuj liczbę porównań w pesymistycznym przypadku.

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

Zadanie 4#

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.

Zawartość