ASD e( 01 2003 1

Algorytmy i struktury danych 2002/2003 Egzamin II rok PJWSTK, 28 stycznia 2003-01-24, Grupa C

1. Dany jest ciąg funkcji: 4^{lg n}, lg n!, Ig n, Vn, n³ 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.

c.    Dokończ zdanie „jeżeli f(n)+g(n) = 0(h(n)), to każdą z funkcji f(n) i g(n) można

oszacować.....”

2.    Na komputerze K wykonanie algorytmu A dla danych o rozmiarze 6 zajmuje 8 sekund.

Złożoność tego algorytmu opisuje funkcja T(n) = 2".

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

b.    Jaki jest największy rozmiar danych, dla których czas wykonania jest <32 sek.?

c.    Ile czasu zużyje komputer 1024 razy szybszy na wykonanie tego algorytmu dla danych o rozmiarze 20?

3.    Rozważmy algorytm: { i := 0; while n>l do i := i+1 od }, w którym początkowa wartość zmiennej n jest liczbą naturalną no, no>0.

a.    Dopisz jedną instrukcję, tak by otrzymany algorytm A zatrzymywał się dla dowolnej wartości naturalnej zmiennej n.

b.    Podaj niezmiennik pętli w otrzymanym algorytmie A.

c.    Sformułuj warunek końcowy, jeśli do podanego w zadaniu tekstu, tuż po „do”, dopisano instrukcję n := n div 2, a warunek początkowy = „n jest potęgą dwójki „?

4. Dany jest ciąg n elementowy.

a.    Jaki jest koszt algorytmu wyszukiwania dowolnego elementu w tym ciągu metodą sekwencyjną?

b.    Wypisz elementy, z którymi zostanie porównana liczba 8, jeśli jej poszukujemy w ciągu 2,3,4,5,6,7,8,9 tą metodą ?

c.    Jaki jest koszt wyszukania dowolnego elementu, jeśli elementy ciągu zostały wcześniej umieszczone jako etykiety drzewa AVL, a jedyne dostępne operacje, to operacje struktury kolejek priorytetowych?

5. Dany jest n elementowy ciąg ai,..., a„. Rozważamy problem wyszukiwania k-tego co do wielkości elementu tego cia^u.

a.    Jaki jest koszt algorytmu Hoare ?

b.    Ile porównań elementów wykona algorytm Hoare. jeśli zastosujemy go do ciągu

5,2,3,4,7,6,8 i k=4?

1