AISDT - Kolokwium 2 poprawkowe 26 stycznia 2008

Podpis

Zadanie 1 (6p)

S jest słownikiem zaimplementowanym w BST. Wstawienie do S nie istniejącego w nim klucza k wymagało 3 porównań. A) Ile po­równań zostanie wykonanych przy próbie po­nownego wstawienia k do S∪{k}. B) Ilu porów­nań wymaga teraz usunięcie k z S∪{k}. C) Ile po­równań zostanie teraz wykonanych przy wyszukiwaniu k usuniętego z S∪{k}.

A) Wymagało .................... porównań. B) Wymagało .................... porównań. C) Wymagało .................... porównań.

Zadanie 2 (6p)

Słownik upo­rz­ą­d­kowany S zawiera klucze {1, 3,5,7}. Użyto metodę podziału interpola­cyj­ne­go, wygenerowano optymalne wartości wartowników, ope­racja dominująca: porów­na­nie kluczy. Określić wartowników. Ilu operacji wymaga wyszuka­nie wszyst­kich ist­nie­jących kluczy? Ilu operacji wymaga wyszukanie wartowników?

Wartownik lewy=........................................... Wartownik prawy=......................................... Wyszukanie wszystkich: .................. operacji Wyszukanie wartowników: ............... operacji

Zadanie 3 (6p)

Wyszukanie P=[12] w T=[2xxx] (x dowolne być może różne symbole) nad alfabetem V={0,...9} algoryt­mem Rabina-Karpa z q=6 wymagało 3 porównań symboli. Znaleźć wszystkie możliwe T.

T=.................................................................... T=.................................................................... T=.................................................................... T=....................................................................

Zadanie 4 (6p)

P=[aab], V={a,b}. Określić za pomocą funkcji sufiksowej i wypisać tablicę przejść automatu. Ilu porównań symboli wymaga obliczenie sigma([P2,a]) taką metoda jak stosowana w algorytmie?

q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... q=....., x=........ q'=sigma(................)=......... Wymaga ................. porównań symboli.

Zadanie 5 (6p)

Narysować krawędzie grafu skierowanego acyklicznego o 6 krawędziach, takiego, że przeszukanie go algo­ryt­mem DFS dało podane wartości d/f i w grafie występuje 1 cięciwa poprzeczna. Ile rozwiązań ma zadanie? Spróbuj podać wszystkie.

---