ALGORYTMY I STRUKTURY DANYCH 2009/2010
egzamin 09.06.2010
Zad. 1 Wpisać poniżej definicję notacji T(n)=O(f(n))
Rozważmy następujące obliczenie, w którym złożoność pesymistyczna operacji P(i,j) jest Ś(1) dla
każdych i,j
for i�!1 to n do
for j�!1 to n do P(i,j)
Niech T(n) oznacza pesymistyczną złożoność czasową powyższego obliczenia.
Które twierdzenia są prawdziwe
T(n)=O(n) T(n)=O(n2) T(n)=O(n3)
Zad. 2 Podać oszacowania złożoności pesymistycznej i średniej algorytmu sortowania QuickSort
(średniej dla wersji probabilistycznej) Uzasadnić
Zad. 3 Jakie jest dolne oszacowanie złożoności pesymistycznej dla algorytmów sortujących przez
porównania ? Jaką rolę pełnią drzewa decyzyjne w uzasadnieniu tej złożoności ?
Zad. 4 Rozważmy tablicę z haszowaniem i łańcuchową metodą rozwiązywania konfliktów.
a) jaka złożoność pesymistyczna operacji wstaw, a jaka operacji szukaj.
b) podać stwierdzenie o złożoności oczekiwanej operacji szukaj wyjaśniając też założenie
probabilistyczne z tego stwierdzenia ( nie wystarczy sama nazwa założenia).
Zad. 5
a) Podać definicję kopca binarnego i narysować przykład kopca zawierającego 6 węzłów.
b) Jaka jest złożoność Extract-max (usunięcie elementu maksymalnego) na kopcu.
Zad. 6
a) Jaka jest złożoność pesymistyczna operacji wstaw na drzewie binarnym.
b) Jaka jest złożoność pesymistyczna operacji wstaw na drzewie czerwono-czarnym.
Zad. 7 Podać oszacowanie wysokości B-drzewa stopnia t w zależności od ilości kluczy w drzewie i
naszkicować dowód tego oszacowania.