2. Klasówka 1999/00#
Zadanie 1#
Niech \(T(a_1, a_2, \cdots, a_n)\) będzie drzewem poszukiwań binarnych powstałym w wyniku wstawienia do początkowo pustego drzewa kolejno \(a_1,a_2, \cdots, a_n\). Dla ilu permutacji \([a_1, a_2, \cdots, a_{2^k - 1}]\) liczb \(1, 2, \cdots,2^k - 1\) wysokość drzewa \(T(a_1, a_2, \cdots, a_{2^k - 1})\) wynosi \(k - 1\)? Odpowiedź uzasadnij.
Zadanie 2#
Na osi liczbowej umieszczane i usuwane są punkty białe i czarne. Zaprojektuj strukturę danych umożliwiającą efektywne wykonywanie następujących operacji:
\(Utworz(S)\):: utwórz pusty zbiór punktów;
\(Dodaj(S, x, k)\):: dodaj do \(S\) punkt koloru \(k\) o współrzędnej \(x\);
\(Usun(S, i)\):: usuń z \(S\) \(i\)-tym punkt co do wartości współrzędnej;
\(Licz(S, k, i, j)\):: podaj liczbę punktów o kolorze \(k\) między \(i\)-tym a \(j\)-tym punktem (włącznie);
\(Nast(S, i)\):: zwróć następny po \(i\)-tym punkt tego samego koloru.
Zadanie 3#
Niech \(M\) będzie maszyną Turinga o lewostronnie ograniczonej taśmie i \(2\) głowicach, które poruszają się (lub nie) tylko w prawo. Początkowo głowice są na początku taśmy. Zasymuluj działanie maszyny na kilku stosach tak, aby możliwe było wykonanie następujących operacji:
\(przesun(T_1, T_2)\):: przesunięcie głowic odpowiednio o \(T_1\) i \(T_2\) pozycji, gdzie \(T_1, T_2 \in \{0, 1\}\);
\(zmien(x,y)\):: zamiana zawartości aktualnie odwiedzanych komórek na odpowiednio \(x\) i \(y\);
\(czytaj\):: czytanie zawartości komórek wskazanych przez głowice.
Uwaga: W miarę możliwości algorytmy należy opisywać słowami, ale na tyle precyzyjnie, żeby można było zanalizować ich złożoność.