2. Klasówka 2006/07 (10.01.2007)#
Zadanie 1 (6 punktów)#
Ciągi 0-1, w których występują długie bloki złożone z samych 0 lub samych 1, można kompresować w następujący sposób: każdy maksymalny blok złożonony z samych 0 zastępujemy liczbą zer występujących w tym bloku, natomiast każdy maksymalny blok złożony z samych 1 zastępujemy liczbą ujemną, której wartość bezwzględną jest liczba jedynek w tym bloku. Zaprojektuj strukturę danych, która umożliwi wykonywanie następujących operacji na ciągach skompresowanych:
Cyfra(i):: podaj cyfrę z pozycji i-tej w ciągu nieskompresowanym
Wstaw(c, i):: wstaw cyfrę c (0 lub 1) na pozycję i-tą w ciągu nieskompresowanym
Usuń(c, i):: usuń cyfrę z pozycji i-tej w ciągu nieskompresowanym
Zamiana(i, j):: zamień każdą cyfrę w przedziale [i, j] w ciągu nieskompresowanym na przeciwną (możesz założyć, że i jest początkiem bloku, a j jest końcem bloku).
Uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoności obliczeniowej poszczególnych operacji. Uwaga. możesz przyjąć, że parametry operacji są poprawne.
Zadanie 2 (6 punktów)#
Graf spójny nazywamy nieparzystym kaktusem, gdy jego każdego dwuspójna składowa jest cyklem o nieparzystej długości. Zaproponuj efektywny algorytm wyznaczania najliczniejszego skojarzenia w nieparzystym kaktusie. Uzasadnij, że Twój algorytm jest poprawny i dokonaj analizy jego złożoności obliczeniowej.
Zadanie 3 (8 punktów)#
Niech \(T_h\) będzie dowolnym AVL-drzewem o wysokości h i minimalnej dla tej wysokości liczbie wierzchołków i niech \(n_h\) będzie liczbą węzłów na najkrótszej ścieżce od korzenia do liścia w drzewie \(T_h\). Czy istnieje 2-3-4-drzewo o wysokości \(n_h-1\) zawierające dokładnie ten sam zbiór kluczy co drzewo \(T_h\)? Odpowiedź uzasadnij.