Egzamin poprawkowy 2011/12

Zadanie 1

Słowa kluczowe: struktury danych, BST

Niech T będzie \(n\)-węzłowym drzewem binarnym, w którego węzłach zapisano \(n\) parami różnych kluczy całkowitoliczbowych. Na drzewie dopuszczalne są operacje dwóch rodzajów: pojedyncza rotacja i zamiana synów węzła wraz z poddrzewami (jeden z synów może być pusty).

1. Pokaż najkrótszy ciąg przekształceń, który przeprowadza drzewo

   

   na drzewo BST.

2. Udowodnij, że każde drzewo binarne \(T\) z kluczami w węzłach można przekształcić na drzewo BST wykonując ciąg operacji zdefiniowanych powyżej.

Zadanie 2

Słowa kluczowe: struktury danych, wzbogacanie, Find-Union

Mamy \(n\) kul ponumerowanych od \(1\) do \(n\). Na początku wszystkie kule są zielone. Na kulach wykonujemy następujące operacje:

1. \(Pokoloruj(a, b, kol):: 1 \leq a \leq b \leq n, kol \in \{zielony, czerwony \}\) - pokoloruj kule o numerach od \(a\) do \(b\) na kolor \(kol\),

2. \(Kolor(a):: 1 \leq a \leq n\) - podaj kolor kuli o numerze \(a\).

3. Zaproponuj strukturę danych, która umożliwi efektywne wykonanie w trybie ,,on-line” \(m\) operacji Pokoloruj i Kolor.

4. Załóżmy, że na początku wykonujemy \(m \geq n\) z góry znanych operacji Pokoloruj, a następnie pytamy o kolor każdej kuli. Zaproponuj efektywny algorytm obliczający kolory wszystkich kul po wykonaniu wszystkich operacji Pokoloruj.

Zadanie 3

Słowa kluczowe: teksty

1. Podaj przykłady słów nad alfabetem \(\{a, b\}\), dla których tablice prefikso-sufiksów są postaci: \([0, 0, 1, 2, 3, 4, 5]\), \([0, 0, 1, 0, 1, 0, 1, 0, 1]\), \([0, 0, 1, 2, 3, 0, 1, 2, 3]\). (Uwaga: tablice są indeksowane od \(0\); pierwszy znak słowa jest na pozycji 1.)

2. Zaprojektuj efektywny algorytm, który dla danego słowa \(u\) oblicza najkrótsze słowo \(w\) takie, że \(u\) jest podsłowem (spójnym fragmentem) słowa \(ww\).