2. Klasówka 2000/01#
Zadanie 1#
Dany jest graf skierowany \(G = (V, E)\), którego krawędzie są poetykietowane symbolami, relacyjnymi \('<'\), \('>'\) i \('='\). Niech \(k\) będzie nieujemną liczbą całkowitą. Powiemy, że \(G\) jest \(k\)-dobry, jeśli wierzchołkom grafu \(G\) można przypisać liczby całkowite z przedziału \([0..k]\) w taki sposób, że liczby na końcach każdej krawędzi spełniają przypisaną tej krawędzi relację. Pierwszym elementem w takie relacji jest zawsze początek krawędzi. Zaproponuj algorytm, który dla danego grafu \(G\) znajduje najmniejsze takie \(k\), że \(G\) jest \(k\)-dobry.
Zadanie 2#
Pokaż, że każde \(n\)-wierzchołkowe drzewo binarne można przekształcić w dowolne inne \(n\)-wierzchołkowe drzewo binarne za pomocą \(O(n)\) rotacji.
Podpowiedź
Każde drzewo można za pomocą rotacji przekształcić na listę (oraz listę na dowolne drzewo).
Zadanie 3#
Dany jest zbiór \(S\) złożony z \(n\) odcinków domkniętych \([a_i, b_i]\) leżących na osi \(OX\), \(i = 1, 2, \cdots, n\). Zaprojektuj strukturę danych, która umożliwia szybką realizację zapytań o wszystkie odcinki, które zawierają zadany punkt \(x\) (\(k\) jest liczbą takich odcinków). Przeanalizuj koszt przygotowanie swojej struktury danych.
Zbiór odcinków domkniętych na osi nazywamy nawiasowym, jeśli każde dwa odcinki albo nie przecinają się, albo jeden zawiera się całkowicie w drugim. Zaproponuj efektywną strukturę danych, która umożliwia wykonywanie następujących operacji na skończonym, dynamicznym zbiorze odcinków nawiasowych:
dodanie nowego odcinka;
usunięcie odcinka;
policzenie ile odcinków zawiera dany punkt \(x\).