Algorytmy i Struktury Danych

W E J S C I ÓW K I

W1 W2 W3 W4 W5 W6 W7

Grazyna Mirkowska
Konsultacje : srody 12-14 p.301

Wejsciówka 1

Notacja asymptotyczna
1. ( 3punkty)Pogrupować następujące funkcje w taki sposób, by dwie funkcje f i g należały do jednej grupy wttw gdy f =TETA (g), a następnie ustawić grupy w porządku rosnących rzędów funkcji. (n 5 +3n+5)/( (n+1)(n-1)), (n4 +3n+5)/2, 2lgn , n 2 + lg(n!), 100n 3 ,lg3 n, lg n 2

2.(za 2 punkty) Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w czasie t przy pomocy algorytmu A o złożoności T(A,n) = n 2, jeśli wiadomo, że ten sam algorytm, na komputerze 64 razy wolniejszym wykonuje w czasie t zadanie o rozmiarze 15.

powrót

Wejsciówka 2

Wyszukiwanie
1. Jaka metoda poszukiwań danego elementu x, w n-elementowym ciągu uporządkowanym, zapewnia minimalny koszt wyszukiwania i jaki jest rząd kosztu tej metody?
2. Jaka jest wysokość drzewa turniejowego zbudowanego dla znalezienia drugiego co do wielkości elementu w danym k elementowym zbiorze?
3. Jaki jest średni koszt wyszukiwania 4tego co do wielkości elementu w danym n elementowym ciągu, jeśli zastosowano metodę Hoare?
4. Ile porównań wykona optymalny algorytm wyszukiwania równoczesnego minimum i maksimum zastosowany do ciągu 5 6 2 1 8 4?

powrót

Wejsciówka 3

Poprawność algorytmu
Podane poniżej algorytmy działają w strukturze liczb naturalnych.
(a) Dla każdego algorytmu zbadać, jaka jest zależność między zmiennymi po wykonaniu algorytmu.
(b) Podać niezmiennik pętli.
(1) begin s := x; i := 1; while i < y do s := s + 1; i := i + 1; od end;
(2) begin S := 0; i := 0; p:=1; while i < n do s := s + p; p := p*2; i := i + 1; d end;
(3) begin s := 0; i := 0; while i < n do s := s + (2*i+1); i := i + 1; od end;


powrót

Wejsciówka 4

1. Ile porównań wykona algorytm sortowania przez selekcje ,
a ile algorytm Szybkiego sortowania, jeśli zastosujemy je do ciągu 1, 2, 3, 4.

2.  Podaj kolejne stany tablicy, której elementy należy uporządkować rosnąco stosując algorytm sortowania przez wstawianie (insertion_sort), i w której na początku znajdują się elementy 1 5 2 4 3.  

3. Ile porównań wykona algorytm sortowania przez wstawianie,
a ile algorytm Merge_sort (sortowania przez scalanie), jeśli zastosujemy je do ciągu 1, 2, 3, 4.

4.  Podaj kolejne stany tablicy, której elementy należy uporządkować rosnąco stosując algorytm sortowania przez wybór (selection_sort), i w której na początku znajdują się elementy 1 5 2 4 3.

5. Podać przykład ciągu 8 elementowego takiego, że algorytm Quick_sort (algorytm szybkiego sortowania) wykonuje dla tego ciągu więciej porównań niż algorytm Merge_sort (sortowania przez scalanie).Proszę podać obie liczby.

6. Czy następujące zdanie jest prawdziwe czy fałszywe? Odpowiedź uzasadnić.
" Gdybyśmy umieli znajdować element minimalny w dowolnym ciągu z kosztem stałym, to algorytm sortowania przez selekcję byłby algorytmem  liniowym."


powrót

Wejsciówka 5

1. Czy następuj¹cy ci¹g liczb mo¿e byæ ci¹giem etykiet drzewa BST odczytanym w porz¹dku inorder (tzn.: lewy, korzeñ, prawy): 1,4,6,8,9,3, 5. OdpowiedŸ uzasadniæ.
2. Utwórz drzewo BST wk³adaj¹c kolejno elementy 5, 1, 4, 8, 6, 3, 9, 2 do drzewa pocz¹tkowo pustego.
3. Jaki jest koszt pesymistyczny wstawienia jednego elementu do BST o n wierzcho³kach?
4. Jaka jest wysokoœæ drzewa binarnego, zawieraj¹cego 17 elementów? Podaj oszacowanie z góry i w do³u. OdpowiedŸ uzasadniæ.
5. Do pocz¹tkowo pustego drzewa BST w³o¿ono elementy 5,4,3,2,1,6,7,8. Narysuj drzewo otrzymane w wyniku.
6. Jaki jest koszt œredni usuniêcia jednego elementu z drzewa BST o n wierzcho³kach?
7. Czy z drzewie BST wszystkie wierzcho³ki le¿¹ce na tym samym poziomie tworz¹ ci¹g uporz¹dkowany? OdpowiedŸ uzasadniæ.
8. Z drzewa BST postaci 4 3 7 1 2 5 8 6 usuniêto korzeñ . Narysuj drzewo BST powstaj¹ce w wyniku tej operacji.
9. Jaki jest œredni koszt wyszukania 1 elementu w drzewie BST o n wierzcho³kach?

powrót

Wejsciówka 6


1. Dopisz wagi przy ka¿dym z wierzcho³ków podanego drzewa. x x x x x x x x
2. Jaki jest koszt usuniêcia jednego elementu z drzewa AVL, które zawiera ju¿ k wierzcho³ków.
3. Czy nastêpuj¹cy ci¹g mo¿e byæ ci¹giem elementów odczytanych z drzewa AVL w porz¹dku prefiksowym? (Jeœli tak – narysuj to drzewo, jeœli nie napisz dlaczego.) 8,5,3,2,1,4,6,7,10,9,11,12.
4. Narysuj minimalne drzewo AVL o wysokoœci 3.
5. Jaki jest koszt w³o¿enia jednego elementu do drzewa AVL, którego wysokoœæ wynosi h?
6. Narysuj drzewo otrzymane w wyniku w³o¿enia elementu 3,5 do podanego drzewa. 6 2 8 1 4 7 9 3 5
7. Jaka jest najwiêksza mo¿liwa wysokoœæ drzewa AVL, które ma 12 wierzcho³ków?
8. Jaki bêdzie efekt usuniêcia elementu 10 z nastêpuj¹cego drzewa AVL?
9. Ile co najwy¿ej rotacji trzeba wykonaæ przy wk³adaniu jednego elementu do drzewa AVL o n wierzcho³kach? 10 6 12 5 8 13 7

powrót

Wejsciówka 7

Wejściówka (bez numeru)

1.    Jaki jest koszt włożenia jednego elementu do kopca o n elementach?
2.    Narysuj kolejne stany drzewa-kopca, utworzonego przez włożenie  elementów 2,6,8,3,0,4,1 do początkowo pustego kopca.
3.    Skonstruuj kopiec w następującej tablicy  [4,8,5,6,3,2,1,9].


4.    Jaki jest koszt usuniecia elementu największego z kopca o k elementach?
5.    Narysuj kolejne stany drzewa-kopca, utworzonego przez włożenie elementów 5,2,8,7,6,4,3 do początkowo pustego kopca.
Skonstruuj kopiec w następującej tablicy [2,4,7,5,9,14,1,0].


6.    Jaka jest wysokość kopca, który przechowuje n elementów?
7.    Narysuj kolejne stany drzewa-kopca, utworzonego przez włożenie elementów 7,6,8,4,5,2,0 do początkowo pustego kopca.
8.    Skonstruuj kopiec w następującej tablicy  [4,7,6,2,9,1,0,3].


powrót