Egzamin poprawkowy 2018/19 (17.02.2019)#
Zadanie 1 (22 punkty)#
[5 punktów] Niech S będzie n-elementowym zbiorem liczb całkowitych i niech d będzie nieujemną liczbą całkowitą. Zaproponuj efektywny algorytm, który znajduje w zbiorze S najliczniejszy podzbiór, w którym różnica między największym i najmniejszym elementem wynosi co najwyżej d. Załóżmy teraz, że S jest dynamicznym, skończonym zbiorem zbiorem liczb całkowitych. Początkowo zbiór S jest pusty. Na zbiorze S wykonujemy następujące operacje:
Wstaw(S,x):: \(S := S \cup \{x\}\);
Usuń(S,x):: \(S := S \ \{x\}\);
Element(S,x):: return \((x \in S)\);
[7 punktów] Zaproponuj strukturę danych umożliwiających efektywne wykonanie 2019n operacji Wstaw, Element i dodatkowo Spójny(S), której wynikiem jest liczność najliczniejszego podzbioru S złożonego z kolejnych liczb całkowitych przy założeniu, że elementy z S pochodzą z przedziału [1,n], n > 0.
[10 punktów]* Zaproponuj strukturę danych, która dla zadanej z góry liczby całkowitej d z przedziału [0,n], n > 0, umożliwia efektywne wykonanie ciągu n operacji Wstaw, Usuń, Element i dodatkowo Podzbiór(S), której wynikiem jest liczność najliczniejszego podzbioru S, w którym różnica między największym i najmniejszym elementem wynosi co najwyżej d.
Zadanie 2 (13 punktów)#
[4 punkty] Jaka może być najmniejsza głębokość liścia w AVL-drzewie o wysokości h?
[4 punkty] Podaj przykład AVL-drzewa i wskaż w nim element, którego usunięcie będzie wymagało wykonania dokładnie dwóch podwójnych rotacji.
[5 punkty] Rozważamy algorytm usuwania klucza z wewnętrznego węzła BST-drzewa, w którym w przypadku gdy węzeł posiada dwójkę dzieci, klucz w węźle jest zastępowany przez najmniejszy klucz w prawym poddrzewie. Zaprojektuj efektywny algorytm wyznaczający ciąg kluczy, które zostaną usunięte kolejno z danego n-węzłowego BST-drzewa, jeśli usuwamy po kolei klucze znajdujące się w korzeniu drzewa.
Zadanie 3 (5 punktów)#
Dana jest plansza o rozmiarach \(1\times n\). Na planszy możemy położyć żeton lub przenieść żeton z jednego pola na inne. Jeśli powstaną dwa stosy żetonów o tej samej wysokości, to jeden z tych stosów jest zdejmowany z planszy. Położenie, przeniesienie lub zdjęcie jednego żetonu zajmuje jednostkę czasu. Jaki jest koszt zamortyzowany jednej operacji?
Uwaga: Uzasadnij poprawność swoich rozwiązań i przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów.