Ctrl+K

2. Klasówka 2003/04

Zawartość

2. Klasówka 2003/04#

Zadanie 1#

Słowa kluczowe: grafy, struktury danych

Grafem trójkątnym nazywamy każdy graf płaski (graf narysowany na płaszczyźnie, w którym jednymi wspólnymi punktami różnych krawędzi są ich końce) zdefiniowany następująco:

  • trójkąt jest grafem trójkątnym;

  • jeżeli \(G\) jest grafem trójkątnym, to graf otrzymywany z \(G\) przez umieszczenie wierzchołka (punktu) wewnątrz dowolnej ściany wewnętrznej (trójkąta bez żadnych wierzchołków w jego wnętrzu) i połączenie go odcinkami z wierzchołkami tej ściany, jest też grafem trójkątnym;

  • żaden inny graf nie jest grafem trójkątnym.

Zaproponuj strukturę danych, która umożliwia efektywne wykonywanie następujących operacji na dynamicznym trójkątnym grafie \(G\):

  • \(Ini\):: inicjalizacja grafu \(G\) jako pojedynczego trójkąta o wierzchołkach ponumerowanych \(1, 2, 3\); ta operacja jest wykonywana tylko raz na samym początku;

  • \(Dodaj(a, b, c)\):: sprawdź, czy w grafie \(G\) istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak i wewnątrz tego cyklu (trójkąta) nie leżą żadne inne wierzchołki grafu, to dodaj nowy wierzchołek wewnątrz trójkąta \([a, b, c]\), połącz go krawędziami (odcinkami) z wierzchołkami \(a, b, c\) i nadaj mu etykietę równą najmniejszej dodatniej liczbie całkowitej różnej od pozostałych etykiet wierzchołków w grafie;

  • \(Usun(a, b, c)\):: sprawdź, czy w \(G\) istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak, to usuń z \(G\) wszystkie wierzchołki leżące wewnątrz cyklu (trójkąta) \([a, b, c]\) oraz krawędzi incydentne z tymi wierzchołkami;

  • \(Ile(a, b, c)\):: sprawdź, czy w grafie istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak, to podaj liczbę wierzchołków leżących wewnątrz cyklu (trójkąta) \([a, b, c]\).

Uzasadnij poprawność swojego rozwiązania i dokonaj analizy czasów wykonywania poszczególnych operacji.

Zadanie 2#

Słowa kluczowe: struktury danych; BST

W \(n\)-węzłowym drzewie poszukiwań binarnych liczba węzłów zewnętrznych (,,nili”) wynosi \(n + 1\). Każdy nowy klucz zajmuje pozycje jednego z węzłów zewnętrznych. Zaprojektuj efektywny algorytm, który dla danego AVL-drzewa sprawdzi, ile jest w nim węzłów zewnętrznych, w których umieszczenie klucza wymaga wykonania rotacji w celu przywrócenia własności AVL-drzewa. Należy przyjąć, że atrybutami każdego węzła wewnętrznego są: \(klucz\), \(lewy\_syn\), \(prawy\_syn\), \(wskaznik\_zrownowazenia\).

Do drzewa odwołujemy się przez korzeń. Uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoność czasowej zaproponowanego algorytmu.

Zawartość