ASD ITN e! 06 2002 B v1 1

Algorytmy i Struktury Danych Egzamin ITN 2002-06-21 grupa B

Imię i Nazwisko

Numer Studenta    Ocena

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybrana odpowiedź kółkiem . lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze me są dozwolone. Powodzenia!

—    1. Jaki jest koszt algorytmu (mierzony ilością porównań elementów)

for i := n downto 1 do P(i) od,

jeżeli P(k) Jest optymalnym algorytmem wyszukiwania największego elementu w zbiorze k- elementowym'

®(rt²)

Q(n Ig n)

Q(n³)

—    2. Zaznacz, formuły, które są prawdziwe:

-    n² =0(2")

-    3”* ‘ - 0(3^r“)

-    n Ign “- ©(tr)

3. Niech A będzie algorytmem o złożoności T(n) = ir. Wykonanie tego algorytmu dla danych rozmiaru n=64 na pewnym komputerze zajmuje 16 sek. Ile czasu zajmie wykonanie tego algorytmu dla danych n=8?.....Odp.:

ov> ęo^u-yK _t    V*

_{_}_.    4. Zbadać co robi następujący algorytm, tzn. sformułować warunek końcowy oraz niezmiennik pętli, jeżeli

warunkiem początkowym jest: Jn > O A ne N) .

{    Niezmiennik:

i := 1; s := 1; while (i <= n) { s = s * i; i=i+ l;

}

Warunek końcowy: ’

U 5. Jaki jest minimalny koszt wyszukiwania elementu najmniejszego i największego w ciągu n

elementowym algorytmem naiwnym ?

Odp.:    1 t    _ |

6.    Jaki jest optymalny koszt wyszukiwania drugiego codo wielkości elementu w zbiorze n elementowym.’ Odp.:

^    ,4    sa 0    ~2,)

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

Odp.:    '    ^- i l ąi {}

•8. Podaj średni koszt algorytmu szybkiego sortowania (ąuick-anrt) n elementów. Odp.:    1 ^7 J ( >

u .....^u.i .    ¹

9. W jakiej kolejności odwiedzane są wierzchołki drzewa D z zadania 11. jeśli zastosowano metodę "wszerz" ^ : Alti{}

6: V

S

BFS¹:

Odp.