ASD ITN e! 06 2002 A v2 1

Algorytmy i Struktury Danych

Egzamin ITN 2002-06-21 grupa A

tmie i Nazwisko

Numer Studenta

Ocena

1	2	3	4	5	6 17 |8			9	10	11	12 | 13 1 14		15	16 | 17		18 119 |20 !
											i i i							i !

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 przypadku innch form zadania. Żadne materiały pomocnicze nie są dozwolcne. Powodzenia!

O

O

1.    Dany algorytm składa się z dwóch części A i B wykonywanych po sobie. Część A realizuje pewien algorytm ^    \

sortowania zbioru X (przez porównywanie elementów), a koszt całkowity realizacji części B jest liniowy (D 1^1 względem mocy zbioru X. Zatem, koszt realizacji całego algorytmu dla danych rozmiaru n daje się oszacować

przez

-    O(n)

-    © (n Iz n)

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

^•2" = 0(2"'')

— 3^:" = 0(3")

(3/2)ⁿ = 0(n^: )

3.    Niech A będzie algorytmem o złożoności T(n) = Ig n. 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.:    Q U - 1 C,

r - v ^x " 2> .

4.    Niech A[l...n] będzie tablicą liczb całkowitych. Zbadać co robi następujący algorytm, tzn. sformułować warunek końcowy oraz niezmiennik pętli jeżeli warunkiem początkowym jest {n > 0 a ne N} .

Niezmiennik:

Wamnek Końcoww

i := 1; s := 0; w'hile (i <= n) {

s = s + A[ij; i = i-i- 1;

5.    Jaki jest minimalny koszt wyszukania elementu najmniejszego w ciągu n elementowym?

^0dp-^;    v\ - A

6.    Jaki jest średni koszt algorytmu wyszukiwania k-tej co do wielkości wartości w ciągu n elementowym metodą Hoare‘a?

Odo.:

7. Podaj kolejne stany tablicy, której elementy należy uporządkować rosnąco stosując algorytm sortowania przez wybór (seieaion-son). i w której na początku znajdują się elementy: K 5.

SkO

^ AA AA

^ AA.u, S

*1 /    A A\ ]/ -f O

S. Podaj koszt algorytmu sortowania przez scalanie (merge-sorr) dla ciągu n elementowego. /[    y) A

Oćd.:    A    ^

>5

OdD.:

w (a