1. Zbadaj, czy tablica o elementach 2,5,4,8,7,9,12,15  reprezentuje kopiec. Zaproponuj algorytm sprawdzania w przypadku ogólnym, czy dana tablica jest reprezentacją kopca. Uzasadnij poprawność przedstawionego algorytmu.
    

2. Zaproponuj iteracyjny algorytm konstrukcji drzewa-kopca na podstawie danej reprezentacji tablicowej.  Jaki jest koszt tego algorytmu?
    

3. Zapisz implementację algorytmu wstawiania elementu do kopca reprezentowanego przez drzewo o korzeniu root, jako procedurę o trzech parametrach, którymi są

   • korzeń drzewa,

   • wstawiana etykieta (z założenia różna od wszystkich istniejących w drzewie etykiet) i

   • pierwszy od lewej wierzchołek na przedostatnim poziomie,  który nie ma dwóch następników, lub pierwszy z lewej liść na ostatnim poziomie, gdy poziom przedostatni jest całkowicie wypełniony.
      

4. Napisz program wyliczający liczbę elementów w danym kopcu reprezentowanym jako drzewo. Oszacuj koszt podanego algorytmu.
    

5. Zaproponuj metodę wyznaczania  pierwszego  wierzchołka na przedostatnim poziomie drzewa-kopca, który nie ma dwóch następników, znając tylko liczbę wierzchołków i korzeń drzewa.
    

6. Dane są dwa zbiory A i B w postaci kopców H1 i H2. Zaproponuj algorytm wyznaczania sumy teoriomnogościowej tych zbiorów. Przedstaw wynik, również w postaci kopca. Jaki jest koszt tego algorytmu?
    

7. Sformułuj warunki konieczne i dostateczne na to, by drzewo binarne <A,x,B>, otrzymane przez złączenie  dwóch kopców A i B było kopcem.
    

8. Udowodnij, że

   • lokalnie pełne drzewo binarne o k liściach ma k-1 wierzchołków wewnętrznych,

   • każdy kopiec ma liczbę liści co najwyżej o 1 większą niż liczbę wierzchołków wewnętrznych.

 

« poprzedni punkt

następny punkt »