ASD Ćwiczenia 9

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenie [Dowód lematu 1]

Udowodnij lemat 1

Rozwiązanie




Ćwiczenie [Kolejka dwumianowa 1]

Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo ?

Rozwiązanie




Ćwiczenie [Przykładowy ciąg operacji]

Narysuj
(a) kolejkę dwumianową
(b) kopiec Fibonacciego
otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, wykonaniu Delmin, zmniejszeniu klucza 7 do wartości 1 i usunięciu klucza 8.

Rozwiązanie




Ćwiczenie [Reprezentacja]

Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację wszystkich operacji z podanymi kosztami.

Rozwiązanie




Ćwiczenie [Meld i DelMin]

Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie



Ćwiczenie [Koszty operacji]

Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego?

Rozwiązanie




Ćwiczenie [Pseudokod]

Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.

Rozwiązanie


Ćwiczenie [Zaznaczanie węzłów]

Węzeł 7 nie został zaznaczony w ostatniej fazie operacji DecreaseKey w animacji z wykładu, pomimo że właśnie stracił jednego syna. Powodem jest to, że podczas wykonywania DecreaseKey nie ma potrzeby zaznaczać korzeni (zastanów się, dlaczego!). Jednak jego sąsiad 18 jest zaznaczony. Jak mogło do tego dojść?

Rozwiązanie



Ćwiczenie [Wysokość drzewa]

Czy wysokość drzewa w -wierzchołkowym kopcu Fibonacciego jest ?

Rozwiązanie



Ćwiczenie [Modyfikacja kopca Fibonacciego]

Czy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany ?

Rozwiązanie