ASD ITN k1 05 2002 3

^VAr_cT ^ ckw^^/wKClu^(Lx-C 't/oi irq ^ItyLoUtcłu<.

/    /    ^CcAvAf^

Zad.4 W słowniku zawierającym 4096 haseł uporządkowanych alfabetycznie, chcemy

wyszukać hasło " kolokwium". Ilę stron musimy obejrzeć zanim znajdziemy stronę z naszym

hasłem, jeśli zastosowaliśmy algorytm binarnych poszukiwań?    '*^Ł ”^_

^0dp........................^    ^    3z jfaj-Uj_% XU

IAJ

;*• --teC vvi |

Czwartej wersji jeszcze nie wymyśliłam

szcze me wymysmam _{A v}    j    _    a

y cyf^Cnr-

Zad. 5 Jaki jest koszt czasowy optymalnego algorytmu wyszukiwania 2-go co do wielkości '^\aątĄ elementu w zbiorze reprezentowanym przez tablicę zawierającą n różnych elementów?

(a)    3n/2 - 2

(b)    2*lg n ({ć))n+lg n -2

(d) inna odpowiedź................

Zad. 5 Jaka jest wysokość drzewa turniejowego w algorytmie wyszukiwania elementu drugiego co do wielkości zastosowanym do 64 elementowego ciągu .

!$> 6 2^

(c)    9

(d)    inna odpowiedź....................

^CvWv^ -

^TtLCCw': - & I^CYc

Zad. 5 Niech A będzie algorytmem 'turniej¹ wyszukiwania elementu drugiego co do wielkości. ** Które z następujących zdań są prawdziwe, a które fałszywe?    ^,t-u

(a)    Koszt czasowy algorytmu A zależy od kolejności elementów w ciągu prawda J(|a}sz\)

(b)    Element największy zawsze znajduje się w korzeniu drzewa turniejowego, prawda)' fałsz

(c)    Element drugi co do wielkości musi się znajdować na poziomie 2 w drzewie turnTćju.

prawdatflałsz)

Zad. 5 Niech A będzie algorytmem 'turniej' wyszukiwania elementu drugiego co do wielkości. Które z następujących zdań są prawdziwe, a które fałszywe?

— (a) W najgorszym razie algorytm wykona n² porównań dla ciągu n elementowego.

prawda (faktt

-f (b) Dla ciągu 16 elementowego algorytm wykona 18 porównań.    ^prawdą>/ fałsz

_j. (c) Dla ciągu 8 elementowego algorytm wykona 9 porównań    ^pfawdaTjFałsz

T

W

Zad. 6 Jeśli zastosujemy algorytm Quick-sort (jako medianę wybieramy zawsze pierwszy element sortowanego aktualnie ciągu) do ciągu n elementowego uporządkowanego rosnąco, to

“ u) nie wykona on ani jednego porównania "łv) wykona on 0(n~) porównań -•w) wykona on co najwyżej n porównań

prawda X^łsz> ^prawda)/fałŚ^ prawda Qalśz^

Zad. 6 Jeśli zastosujemy algorytm Merge-sort do ciągu n elementowego odwrotnie uporządkowanego. to

x)    wykona on 0(n²) porównań

y)    wykona on stałą nizależną od n liczbę porównań

-i