ASD e 02 2003 1

Algorytmy i struktury danych Egzamin II rok PJWSTK, 10 luty 2003 Grupa B

Nazwisko    numer grupy    nr indeksu

1.    Dany jest ciąg funkcji: Vn, 3ⁿ, n!, Ig n⁴,2^2,1 określonych w zbiorze liczb naturalnych.

a.    Uporządkuj je ze względu na rosnący rząd wielkości.

b.    Ustal rząd funkcji będącej sumą wymienionych funkcji.

2.    Na komputerze K wykonanie algorytmu A dla danych o rozmiarze 10 zajmuje 8 sekund. Złożoność tego algorytmu opisuje funkcp T(n) = n³.

2a. Ile czasu zajmie wykonanie algorytmu A dla danych o rozmiarze n=20?

2b. Jaki jest największy rozmiar danych, dla których czas wykonania nie przekroczy 27 sek.?

2c. Ile czasu zużyje komputer 10 razy szybszy na wykonanie tego algorytmu dladanych o rozmiarze 50?

3.    Niech a(l),..., a(n) będzie ustalonym ciągiem. Rozważmy następujący algorytm:

{ x := a(n); i:=n-l; while i>0 do x:= x + a(i); i:=i-l; od }.

3a. Podaj niezmiennik pętli w powyższym algorytmie.

3b. Czy koszt tego algorytmu jest liniowy, czy logarytmiczny?

4a. Oszacuj koszt wyszukiwania dowolnego elementu w n elementowym ciągu uporządkowanym metodą „skoków co 5”.

4b. Wypisz kolejne porównania, jeśli szukamy tą metodą liczby 6 (załóżmy, ze wiemy iż jest to element ciągu) w ciągu 0,1,2,3,4,5,6,7,8,9.

5a. Do równoczesnego wyszukania elementów minimalnego i maksymalnego zastosowano algorytm rekurencyjny. Ile co najwyżej razy trzeba go wywołać, jeśli ciąg ma 2 elementów.

5b. Jaki jest koszt tego algorytmu?

6a. Ile przestawień elementów wykona algorytm sortowania przez wybór zastosowany do ciągu 6, 3, 1, 4. 2?

6b. Czy liczba wykonanych w tym algorytmie porównań zależy od kolejności elementów?

7a. Jaki jest pesymistyczny koszt algorytmu Quicksort dla ciągu o i elementach?

7b. Wypisz stan ciągu 6, 1, 2, 8, 3, 7, 0, 8, 9 po jednokrotnym zastosowaniu algorytmu SPLIT (rozdzielanie), jeśli przyjmiemy, że medianąjest 6 .

8a. Ile wywołań rekurencyjnych wykona algorytm Mergesort (sortowania przez scalanie), jeśli go zastosujemy do ciągu o 2ⁿ elementach?

Sb. Ile porównań wykona algorytm scalania ciągów: 4, 7. 8 i 1,2,3.5,9?

10.    Załóżmy, że liczba 2 występuje w pewnym ciągu (a) na pozycjach 3 i 7. W jakiej kolejności wystąpią te dwójki po posortowaniu ciągu metodą „przez zliczanie”: (l)najpierw ta z pozycji 3, czy (2) najpierw ta z pozycji 7, czy może (3) ich kolejności nie można przewidzieć?

lOa. Jaki jest koszt czasowy algorytmu sortowania przez zliczanie?

11. Zbuduj drzewo BST, wkładając kolejno do początkowo pustego drzewa elementy:

6.3.5.1.8.7.O.9. Wypisz elementy otrzymanego drzewa w porządku

I la. inorder:............................................................................

1 lb. preorder:...........................................................................

lic. postorder:.......................................................................

12a. Narysuj drzewo D otrzymane w wyniku dołączenia elementu 8.5 do drzewa z zadania I I. potraktowanego jako drzewo AVL(jeśli trzeba, wykonaj konieczne rotacje)

I2b. Usuń i. stosując algorytm delete) korzeń tego drzewa i narysuj drzewo AVL. otrzymane w wyniku.