ASD e( 01 2003 2

c. Jaki byłby koszt rozwiązania, gdybyśmy umieścili wszystkie elementy w kopcu i k razy wyjmowali z kopca element minimalny?

6.    Rozważamy problem sortowania n elementowego ciągu w porządku rosnącym.

a.    Ile porównań wykona algorytm selectionsort zastosowany do ciągu 1,2,3,4,5,6,77

b.    Podaj przykład ciągu (o ile to możliwe), dla którego algorytm Quicksort wykona 0(n²) porównań.

c.    Jaka jest złożoność algorytmu Mergesort?

7.    Dokończ następujące zdania:

a.    Średnia długość ścieżki w drzewie decyzyjnym dla algorytmów sortowania przez

porównywanie elementów wynosi.................

b.    Koszt pamięciowy algorytmu sortowania przez zliczanie zastosowanego do ciągu n

elementowego, złożonego z liczb 3 cyfrowych wynosi...................

c.    Sortowanie koszykowe nie wymaga.................

8.    Zbudowano drzewo BST wkładając kolejno do początkowo pustego drzewa elementy: 4, 3, 8, 5, 6,2 ,1,9. Zapisz elementy otrzymanego drzewa w porządku

a.    inorder:............................................

b.    preorder:...........................................

c.    postorder:..........................................

9.    Rozważmy drzewo otrzymane w zadaniu 8.

a.    Narysuj to drzewo i oblicz wagi.

b.    Jeśli nie jest to drzewo AVL, to wykonaj stosowną rotację, wstaw element 7 i narysuj AVL otrzymane w wyniku.

c.    Oszacuj wysokość drzewa AVL o n wierzchołkach......................

10.    Niech będzie tablica tab = [2,7,5,4,8,1,3, 6].

a.    Narysuj kopiec-drzewo otrzymane w wyniku kolejnego wkładania elementów tablicy do początkowo pustego drzewa.

b.    Jaki jest koszt utworzenia kopca o n wierzchołkach?................

c.    Skonstruuj kopiec w tablicy tab i wypisz jej zawartość...........................................

11.    Zbadaj prawdziwość następujących zdań (odpowiedz tak/nie i dlaczego?):

a.    Jeśli d jest drzewem BST i wykonano na nim operacje delete(insert(d,e), e) to

otrzymane drzewo jest identyczne z drzewem d....................

b.    Jeśli kopiec ma 32 elementy, to na ostatnim poziomie jest dokładnie jeden liść.

c.    Każdy model struktury stosów jest izomorficzny z pewnym modelem standardowym