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.

Wyszukiwarka

Podobne podstrony:
teoriaA Algorytmy i struktury danych 2009/10, egzamin I imię i nazwisko:    zAliczenl
vl4216 egz algorytmy 1 2 3 4 5 6 7 Algorytmy i struktury danych 2008/09, egzamin I Z imię
Algorytmy i struktury danych I FD + DUMFL - egzamin poprawkowy II 2006Nazwisko i imię..Numer albumZa
fetch php Egzamin. 1 tcmun. 19 czerwca 2(KWr Algorytmy i struktury danych Zadanie 1(10 pkt) 1  
Algorytmy i struktury danych I EF-DI — egzamin poprawkowy 2009 Nazwisko
egzamin (35) 1 2 3 4 5 6 7 Algorytmy i struktury danych 2006/07, egzamin I kierunek:
algorytmyisd4pu AWiip_Algorytmy i Struktury Danych - semestr IV_ EGZAMIN 1    14. 06.
ASD e( 01 2003 1 Algorytmy i struktury danych 2002/2003 Egzamin II rok PJWSTK, 28 stycznia 2003-01-2
egz1 Zestaw C ALGORYTMY I STRUKTURY DANYCH - Egzamin Nazwisko i imię:
egz2 Zestaw 11 Nr indeksu: ALGORYTMY l STRUKTURY DANYCH - Egzamin Nazwisko i imię UWAGA: Każde zadan
egz3 Zestaw A Nr indeksu: ALGORYTMY I STRUKTURY DANYCH - Egzamin Nazwisko i imię: UWAGA: Każde zadan
egz5 Zestaw C Nr indeksu: ALGORYTMY I STRUKTURY DANYCH - Egzamin Nazwisko i imię UWAGA: Każde zadani

więcej podobnych podstron