egzamin (35)

1	2	3	4	5	6	7	Algorytmy i struktury danych 2006/07, egzamin I

kierunek:    imię i nazwisko:

zaliczenie zima:    zal. wiosna:

Punktacja: każdy podpunkt lub zadanie bez podpunktów = 5; razem 50

1.    Jakie typowe operacje wykonujemy na kopcach dwumianowych? Podać nie tylko same nazwy, ale tez wyjaśnienie co dana operacja robi.

2.    Omówić złożoność czasową algorytmu sortowania szybkiego Quicksort uzasadniając skrótowo jedno z przedstawianych stwierdzeń o złożoności.

3.    Rozważmy tablice z haszowaniem i łańcuchową metodą rozwiązywania konfliktów.

(a)    jaka jest złożoność pesymistyczna operacji wstaw a jaka operacji szukaj-, podać krótkie uzasadnienie

(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)

4.    (a) Podać definicję kopca binarnego.

(b) Jaka jest złożoność czasowa następującej operacji na kopcu binarnym: Extract-max (usunięcie elementu maksymalnego)? Uzasadnić krótko odpowiedź.

5.    (a) Jaka jest złożoność pesymistyczna operacji wstaw wykonywanej na drzewie poszukiwań binarnych; krótko ją uzasadnić

(b) Jaka jest złożoność pesymistyczna operacji wstaw wykonywanej na drzewie czerwono-czarnym; krótko ją uzasadnić

6.    Przy każdym z poniżej podanych algorytmów dopisać, jaki sposób organizacji efektywnych algorytmów został w nim wykorzystany. (Do wyboru są: metoda dziel i zwyciężaj, strategia zachłanna, programowanie dynamiczne.)

-    algorytm Huffmana:

-    Quicksort:

-    algorytm szukania najdłuższego wspólnego podciągu:

-    algorytm Dijkstry wyznaczania najkrótszych ścieżek w grafie między ustalonym wierzchołkiem a każdym innym wierzchołkiem:

7.    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?