AISDT - Kolokwium 2 19 stycznia 2009

Podpis:

Zadanie 1 (5p)

Słownik składa się z n elementów, jest zaimplementowany w tablicy uporządkowanej i przeszukiwany algorytmem podziału binarnego. Operacją dominującą jest porównanie kluczy dające trzy wyniki: mniejszy, większy lub równy. Złożoność czasowa pesymistyczna wyszukiwania W(n)=4. Określić wszystkie możliwe wartości n. Narysować drzewo podziału binarnego dla tego przypadku.

n = .............................................................(3p) drzewo podziału (2p)

Zadanie 2 (5p)

Słownik zawierający klucze {1,2,3} zaimple­mentowano w drzewie BST. Operacją dominującą jest porównanie kluczy dające wynik: mniejszy lub większy. Określić złożoność pesymistyczną W, optymistyczna B i oczekiwaną A wstawienia jednego klucza spośród {0,4}. Prawdopodobieństwa każdej możliwej struktury BST są jednakowe. Prawdopodobieństwa wstawiania 0 i 4 są jednakowe. Zamieścić rysunek wszystkich przypadków drzew BST i możliwych wstawień.

B(n)=........................................................(1p) W(n)=.......................................................(1p) A(n)=........................................................(2p) Rysunek (1p)

Zadanie 3 (5p)

Algorytmem Rabina-Karpa wyszukujemy wzorzec P=[101] w tekście T=[0101] nad alfabetem V={0,1} przy q=3. Ile razy zostanie wykonane strng_comp? Ile razy zostaną porównane elementarne symbole? Podać analogiczne wyniki dla algorytmu Naive. Wyciągnąć wniosek.

Dla R-K: strng_comp wykonane .......... razy (1p) liczba porównań symboli=.............. (1p) Dla Naive: strng_comp wykonane .......... razy (1p) liczba porównań symboli=.............. (1p) Wniosek (1p) ....................................................................... ....................................................................... .......................................................................

Zadanie 4 (4p)

P=[32123], V={1,2,3,4}, T=[421321432]. Automat znajduje się w stanie q=3 (licząc od 0). Określić ile symboli tekstu zostało wczytanych i ile symboli wzorca zostało znalezionych? Wyrazić za pomocą funkcji sufiksowej od konkretnego ciągu symboli i podać liczbowo numer stanu automatu po wczytaniu następnego symbolu tekstu.

Liczba wczytanych symboli tekstu=..........(1p) Liczba znalezionych symboli wzorca=......(1p) Numer stanu=sigma([...........................])=......

Zadanie 5 (6p)

Algorytmem BFS przeszukano graf nieskierowany o n wierzchołkach. dmax jest największą wartością atrybutu d wierzchoł­ków. Ile wynosi maksimum oraz minimum dmax wśród wszystkich realizacji grafów o n wierz­chołkach? Ile wynosi największa wartość dmax mniejsza od tego maksimum?

Minimum dmax = ......................................(2p) Maksimum dmax =.....................................(2p) Największa dmax < maksimum = .............(2p)

Zadanie 6 (5p)

Na rysunku podano wynik działania DFS dla pewnej krawędzi grafu G. Czy krawędź ta należy do drzewa przeszukiwania? Czy G jest cykliczny? Czy można wierzchołki G posortować topologicznie? Ile najmniej wierzchołków może zawierać graf G ?

Należy do drzewa? (tak/nie)? ...................(1p) Cykliczny? (tak/nie/nie wiadomo)? ..........(1p) Czy można posortować (tak/nie/nie wiadomo)?..........................................................(1p) Zawiera najmniej ............. wierzchołków (2p).

---