Bäume und Graphen

Question 1

Was ist der Grad eines Knotens?

Answer 1

Die Anzahl an Nachfolger.

Question 2

Was ist der Grad eines Baumes?

Answer 2

Die maximale Anzahl an Nachfolger, die ein Knoten in diesen Baum haben kann.

Question 3

Wie lässt sich die Tiefe eines Baumes herausfinden?

Answer 3

Durch Zählen der Kanten des längsten Pfads.

Question 4

Wie lässt sich die Tiefe eines Knotens herausfinden?

Answer 4

Durch Zählen der Kanten des Pfads, der von der Wurzel zum Knoten führt.

Question 5

Auf welcher Ebene ist die Wurzel?

Answer 5

Auf Ebene 0.

Question 6

Wodurch sind Binäre Bäume charakterisiert?

Answer 6

Der Grad des Baumes ist 2.

Question 7

Was ist ein binärer Suchbaum?

Answer 7

Wenn von der Wurzel und jedem Knoten aus links immer die kleineren Werte und rechts die größeren Werte vorzufinden sind, ist es ein binärer Suchbaum.

Question 8

Was ist eine Traversierung?

Answer 8

Alle Knoten von einem Baum werden systematisch abgearbeitet.

Question 9

Beschreibe die Preorder-Traversierung!

Answer 9

1. Es wird die Wurzel betrachtet, als
2. wird der linke Teilbaum betrachtet und als
3. wird der rechte Teilbaum betrachtet

Question 10

Beschreibe die Inorder-Traversierung!

Answer 10

1. Es wird der linke Teilbaum betrachtet, als
2. wird die Wurzel betrachtet und als
3. wird der rechte Teilbaum betrachtet

Question 11

Beschreibe die Postorder-Traversierung!

Answer 11

1. Es wird der linke Teilbaum betrachtet, als
2. wird der rechte Teilbaum betrachtet und als
3. wird die Wurzel betrachtet

Question 12

Wie läuft die binäre Suche in einem binären Suchbaum ab?

Answer 12

1. wird überprüft, ob der Baum und der gesuchte Wert einen Inhalt hat und gegebenenfalls null zurückgegeben, als
2. wird in den linken Teilbaum gegangen, falls der gesuchte Inhalt kleiner als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
3. in den rechten Teilbaum gegangen, falls der gesuchte Inhalt größer als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
4. der Wurzelinhalt zurückgegeben.

Question 13

Wie läuft das Einfügen eines Inhalts in einen binären Suchbaum ab?

Answer 13

1. wird überprüft ob der einzufügende Inhalt einen Wert hat, als
2. wird überprüft, ob der Baum leer ist und gegebenenfalls der Inhalt in die Wurzel gepackt. Falls dies nicht der Fall ist, wird als
3. der Auftrag des Einfügens mit dem linken Teilbaum gestartet, falls der einzufügende Inhalt kleiner, als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
4. der Auftrag des Einfügens mit dem rechten Teilbaum gestartet, falls der einzufügende Inhalt größer, als der Wurzelinhalt ist.

Question 14

Wie läuft das Entfernen eines Inhalts aus einem binären Suchbaum ab?

Answer 14

1. Falls der zu entfernende Inhalt gefunden wurde:
   - Falls der Baum keine Teilbäume hat, also ein Blatt ist, wird der Inhalt einfach null gesetzt.
   - Falls er nur einen Teilbaum besitzt kann dieser einfach aufrücken.
   - Falls der Baum zwei nichtleere Teilbäume hat, wird das Maximum des linken Teilbaums an die Stelle des gelöschten Knoten gesetzt und das Maximum wird nach den oberen Prinzipien gelöscht.
2. Falls der zu entfernende Inhalt noch nicht gefunden wurde wird nach der binären Suche weitergesucht.

Question 15

Was ist ein Partiell geordneter Baum?

Answer 15

Der Wert eines Knotens ist immer größer oder kleiner, als seine Nachfolger.

Question 16

Was ist ein AVL-Baum?

Answer 16

Ein ausbalancierter Baum, der auf jeder Seite ca. gleich viele Nachfolger hat. Wird mithilfe eines Balancefaktors bestimmt.

Question 17

Wie wird der Balancefaktor in einem AVL-Baum berechnet?

Answer 17

BF = Höhe rechter Teilbaum - Höhe linker Teilbaum

Question 18

Wann tritt eine Rotation in einem AVL-Baum ein?

Answer 18

Wenn der BF kleiner als -1 oder größer als 1 eines Knotens ist.

Question 19

Wie läuft die Rotation in einem AVL-Baum ab?

Answer 19

Wenn der BF kleiner als -1 ist und dessen Nachfolgers BF -1 ist, wird rechtsrotiert.
Wenn der BF größer als 1 ist und dessen Nachfolgers BF 1 ist, wird linksrotiert

Wenn der BF kleiner als -1 ist und dessen Nachfolgers BF 1 ist, wird linksrechtsrotiert.
Wenn der BF größer als 1 ist und dessen Nachfolgers BF -1 ist, wird rechtslinksrotiert

Question 20

Wie läuft eine Rechtsrotation in einem AVL-Baum ab?

Answer 20

Der linke Nachfolger des Knotens mit einem zu niedrigen BFs wird die neue Wurzel des Teilbaums und der Knoten mit dem zu niedrigen BF wird dessen rechter Nachfolger.

Question 21

Wie läuft eine Linksrotation in einem AVL-Baum ab?

Answer 21

Der rechte Nachfolger des Knotens mit einem zu hohen BFs wird die neue Wurzel des Teilbaums und der Knoten mit dem zu hohen BF wird dessen linker Nachfolger.

Question 22

Wie läuft eine Linksrechtsrotation in einem AVL-Baum ab?

Answer 22

Der rechte Nachfolgerteilbaum wird linksrotiert und dann wird der eigentliche Baum rechstrotiert. Danach hat die Wurzel des Baumes einen Nachfolger zu viel, also muss dieser in den rechten Teilbaum eingefügt werden.

Question 23

Wie läuft eine Rechtslinksrotation in einem AVL-Baum ab?

Answer 23

Der linke Nachfolgerteilbaum wird rechtsrotiert und dann wird der eigentliche Baum linksrotiert. Danach hat die Wurzel des Baumes einen Nachfolger zu viel, also muss dieser in den linken Teilbaum eingefügt werden.

Question 24

Wann ist eine Eulertour in einem Graphen möglich?

Answer 24

Wenn maximal zwei Knoten eines Graphen einen ungeraden Grad haben.

Question 25

Was sind Vor- und Nachteile einer Graphenmodellierung mit Adjazenzlisten?

Answer 25

+ Sie belegen nur soviel Speicherplatz wie nötig
- Beim Suchen muss man ggf. erst eine lange Kartenliste durchlaufen
+ Der Graph kann dynamisch ergänzt werden

Question 26

Was sind Vor- und Nachteile einer Graphenmodellierung mit Adjazenzmatrizen?

Answer 26

+ Es lässt sich schnell prüfen, ob eine Kante vorhanden ist

• Sie benötigen immer gleich viel und vergleichsweise viel Speicherplatz
• Der Graph kann nicht dynamisch erweitert werden

Question 27

Wann bietet sich eine Adjazenzliste an?

Answer 27

Bei dünnen Graphen mit wenigen Kanten

Question 28

Wann bietet sich eine Adjazenzmatrix an?

Answer 28

Bei dichten Graphen mit vielen Kanten

Question 29

Wie läuft die Tiefensuche in einem Graphen ab?

Answer 29

1. werden alle Markierungen aufgehoben, als
2. wird der besuchte Knoten markiert und als
3. wird der ganze Vorgang mit allen Nachbarknoten wiederholt, falls diese nicht markiert sind

Question 30

Wie läuft die Breitensuche in einem Graphen ab?

Answer 30

1. werden alle Markierungen aufgehoben, als
2. wird der besuchte Knoten markiert, als
3. wird der besuchte Knoten in eine Liste s eingefügt, als
4. wird solange s nicht leer ist der vorderste Knoten aus s genommen und dessen, falls sie noch nicht markiert sind, Nachbarknoten markiert und an s angehangen

Question 31

Wann lohnt sich eine Tiefensuche in einem Graphen?

Answer 31

Wenn der zu findende Knoten weit von dem Startknoten entfernt zu erwarten ist.

Question 32

Wann lohnt sich eine Breitensuche in einem Graphen?

Answer 32

Wenn der zu findende Knoten nah an dem Startknoten zu erwarten ist.

Question 33

Wie läuft die Suche nach einem Weg von einem zu einem anderen Knoten ab, mithilfe der Tiefensuche und des Backtrackings ab?

Answer 33

private boolean sucheWeg(Vertex start, Vertex ziel, List pWeg)
{
//Vertices überschreiben, Startknoten der Wegliste hinzufügen und markieren, Wegliste Access geben
Vertex s = g.getVertex(start.getID());
Vertex z = g.getVertex(ziel.getID());
pWeg.append(s);
s.setMark(true);
pWeg.toFirst();

//Überprüfen, ob der Zielknoten schon gefunden wurde 
 if(!s.getID().equals(z.getID())){ 

//Falls nicht: Nachbarn des Startknoten in eine Nachabrliste packen und dieser Access geben 
 List n = g.getNeighbours(s); 
 n.toFirst(); 

//Jeden Nachbarn aus der Liste abklappern und ab dort mit der Methode weitersuchen, falls derjenige nicht markiert ist 
 while(n.hasAccess()){ 
 if(!n.getContent().isMarked()){ 
 return sucheWeg(n.getContent(), z, pWeg); 
 } 
 n.next(); 
 } 

//Backtracke, nachdem alle Nachabarn durchsucht wurden
pWeg.toLast();
pWeg.remove();
return false;
}

//Füge den Weg der globalen Wegliste hinzu und breche den Vorgang 
 this.weg.concat(pWeg); 
 return true; 
 }

Question 34

Was ist die Grundidee vom Dijkstra-Algorithmus?

Answer 34

Man verfolgt immer den kürzesten Weg zum nächsten Knotenpunkt und geht dann von dort aus weiter.

Question 35

Wie läuft der Dijkstra-Algorithmus ab?

Answer 35

1. werden alle Knoten in eine Liste eingefügt, als
2. wird allen Knoten, außer dem Startknoten, der Wert unendlich zugewiesen, als
3. erhält der Startknoten den Wert 0, als
4. wird der Knoten K mit der geringsten Entfernung vom Startknoten aus der Liste entfernt, als
5. werden die Nachbarknoten betrachtet und dessen Entfernungen zu der von dem derzeit besuchten Knoten K Entfernung zum Startpunkt addiert. Falls diese Summe kleiner als die bisherige Entfernung ist, wird diese als neue Entfernung dessen Nachbarknoten gesetzt und als
6. wird das ganze bei Schritt 4 wiederholt, bis der Zielknoten entfernt werden soll

Question 36

Was ist ein gerichteter Graph?

Answer 36

Die Richtung der Kanten ist vorgegeben.
Wenn man in beide Richtungen gehen möchte, sind zwei Kanten nötig.

Question 37

Was ist ein ungerrichteter Graph

Answer 37

Die Richtung der Kanten ist nicht vorgegeben, man kann also auf eine Kante in beide Richtungen gehen. Den einzelnen Kanten können Gewichte zugeschrieben werden.

Question 38

Wann ist ein ungerichteter Graph zusammenhängend?

Answer 38

Wenn jeder Knoten erreichbar ist, sonst gibt es einzelne Knotengruppen

Question 39

Wann ist ein gerichteter Graph zusammenhängend?

Answer 39

• Er ist schwach zusammenhängend, wenn er als ungerichteter Graph zusammenhängend wäre.
• Er ist von einem Knoten v aus stark zusammenhängend, wenn es vom Knoten v aus einen gerichteten Weg zu allen anderen Knoten gibt.
• Er ist stark zusammenhängend, wenn es von jedem Knoten aus einen gerichteten Weg zu jeden anderen Knoten gibt.
• Er ist nicht zusammenhängend, wenn es einzelne Knotengruppen gibt.