ASD ITN e! 06 2002 C 1

Algorytmy i Struktury Danych Egzamin ITN 2002-06*21 grupa C

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

1. Oszacuj z góry koszt t wykonania algorytmu

if n<10 tben P(n,x) else B(n,x) n,

jeżeli P(n..\) jest algorytmem sekwencyjnym wyszukiwania pewnego elementu x tv uporządkowanym zbioize u-elementowym, a B<u.x) jest algorytmem binarnych poszukiwań.

- t = 0( Ig n)

-1 = 0(n")

-1» 0(n)

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

-    5³ⁿ = 0(5") Y &

-    n!=0(n") )C

on

•2^-eOgn*) %

3.    Niech A będzie algorytmem o złożoności T(n) = u^-'. Wykonanie tego algorytmu dla danych rozmiaru m=64 nu pewnym komputerze zajmuje 16 sek. He czasu zajmie wykonanie tego algorytmu dla danych n=8?

°^dp:'    ^    rv o*o

4.    Zbadać co robi następujący algorytm, tzn. sformułować warunek końcowy oraz niezmiennik pętli, jeżeli warunkiem początkowym jest: |n > O A ne Ni .

{

i:= 0; z:= 0;    Niezmiennik:

while (i< n) {

z:-z+(2i+l); i := i+I;

j    W arunek Końcowy:

}

UKiwama elementu najmmejs:

5. Jaki jest minimalny koszt wyszukiwania elementu najmniejszego i największego w ciągu n elementowym algorytmem optymalnym?

Odp.:

6. Oszacować koszt pesymistyczny wyszukiwania elementu x w eiągu uporządkowanym n elementowym metoda skoków co 5 elementów. Odp.:    ,

4W»i + •? r<

7. Podaj kolejne stany tablicy, której element należy uporządkować rosnąco stosując algorytm sortowania przez scalanie tmerge-sort). i w której na początku znajdują się elementy: 5. I. 2. 4. 6. 3. 8. 7. ^N..... ri yi    A 1

U

6 ^U soności algorytmów sortowania ciągu n elementowego przez porównywanie 4 £

Odp.:    $/lf    ...............Y

-Vjr«Jslł%    ^..................

^u vfe

M. Podaj dolne oszacowanie złozo elementów.

Odp.:    -4