ASD ITN e! 06 2002 B v2 1

Algorytmy i Struktury Danych

Egzamin ITN 2002-06-21 grupa B

Imię i Nazwisko    Numer Studenta    Ocena

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20 |
					,

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ą dozwolone. Powodzenia!    2J.

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 algontmem wyszukiwania największego elementu w zbiorze k- elementowym? -f-    0(n^:)

Q (n lg n)

-    £2 (n³)

2.    Zaznacz, formuły, które są prawdziwe: n² = 0(2°)

Tf- 3"^łt = 0(3")

—— n Ign = 0(n“)

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

adać co robi następujący algorytm, tzn. sformułować warunek końcowy oraz niezmiennik pętli, jeżeli arunkiem początkowym jest: {n > 0 a ne N} .

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

}

Niezmiennik:

Warunek końcowy:

i

>n <('*>} i--/

y)

Odp.:

5. Jaki jest minimalny koszt wyszukiwania elementu najmniejszego i największego w ciągu n elementowym alaommem naiwn\m?

6.    Jaki jest optymalny koszt wyszukiwania drugiego co do wielkości elementu w zbiorze n elementowym?

m

^0dp'^:    ńcifo^Ui^    u-Z>

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

^0(jP-^: i&\Ol^\cluUL ®    ,«-<£>    £04,i fo/t, 2,^A,5

8.    Podaj średni koszt algorytmu szybkiego sortowania Cimck-son) n elementów.

“^P'^:    e Acj n)'

9.    W jakiej kolejności odwiedzane sa w ierzchołki drzew a D z zadania ! 1. jeśli zastosowano metode "wszerz"

^BFS? *-    Z    5.3-.Ć

3    \

Odp.:

7

/ \

%

wS£

& ~f-%

TLx

ca

3