teoriaB

1	2	3	4 | 5 | 6	^ 1	Algorytmy i struktury danych 2009/10, egzamin I
			I

imię i nazwisko:    zaliczenie zima:    zai. wiosna:

Uwaga: proszę wyjaśniać używane symbole, np ° n ilość, elementów tablicy . Punktacja, każdy podpunkt lub zadanie bez podpunktów ~ 5; razem 50

1. Wpisać poniżej definicję notacji T(n) 0(/(n))

Rozua/im imstępujące oblu ,> nic, w Vi«\ tu r\<|h«>\medycz/wt operacji P(i,j) jest 0(1) dU każdych i, j

for i *- l to n do

for j «—    1 to a do PU,))

Niech oenari* |xM-8i«4vtm    <v-»>**** powyzaaego obliczenia, Które z podanych po-

tuzej stwierdam oą prawdziwe, a które iwe? (DuptMr tak lub me)

t(»> = o(«*)    i\»> - n(o*)    r(»> « a<»)

2- P»>W o^zacowaina zio&jnaśći czasowej (dolne i górne) algorytmu sortowania przez kopcowanie Beap-sorx. Uzasadnić skrótowo jedno z przecklawianych oszacowań

3.    Rcewazim tabbee z baaaowssueru i adresowainem otwartym

(a)    jaka jest zJoououbć pesymistyczna operacji .%zukuf. podać krótkie uzasadnienie

(b)    podać stwierdzenie o złożoności oczekiwanej operacji szukaj, wyjaśniając: tez założenie probabilistyczne z tego stwierdzeni* (nie wystarczy sama nazwa założenia)

4.    Co wiemy o pesynaatyczoej i ocsakiwatMij wyaokuści drzew |>ortzukiwań binarnych zawierających n węzłów⁷

o. (a) podać definicję drzewa czerwono-czarnego

(b) jaka jest złożoność iieymistyczna oj m racji usuń wykonywanej tut drzewie czerwono-czarnym; krótko ją uzasadnić

6.    (a) Jaka- są wymagania co do ilości khu zy w węźle 11 drze wa o lniuiinalnym stopniu ł? Narysować przykład Eł-drzewa stopnia 3 zawierającego co najmniej 12 kluczy.

(b) Jaka jest złożoność operacji w.daw w lin Ir zewie o minimalnym stopniu tl Uzasadnić krótko odpowiedź.

7.    Podać oszacowanie wysokości kopca binarnego w zależności od ilości kluczy w kopcu i naszkicować

dowód tego oszacowania.