Abstrakter Datentyp Queue und Tree

Question 1

Warum sagt man, eine Schlange arbeitet nach dem FIFO-Prinzip?

Answer 1

Weil neu hinzugefügte Elemente Nachfolger vom letzt hinzugefügten Element sind. Der Head bleibt solange auf dem ältesten Element, bis dieses Dequed wird. Dann wandert der Head auf das nächst älteste Element.

Question 2

Nenne die Methoden einer Schlange

Answer 2

empty
enque
front
deque

Question 3

Nenne die Methoden einer Schlange

Answer 3

empty
enque
front
deque

Question 4

Schreibe wie ich eine generische Klasse Box deklariere

Answer 4

public class Box <T>{</T>

Question 5

Beschrifte einen Baum, welche Bestandteile hat er?

Answer 5

Im Grunde ist der Baum eine Verkettung von Knoten.
Der Quellknoten ist der Wurzelknoten. Ein Knoten besteht aus zwei Zeigerattributen links, rechts, diese zeigen auf den nächsten Knoten, und einem Inhaltattribut.

Question 6

Nenne die Methoden eines Baumes

Answer 6

boolean empty()
Baum left()
Baum right()
Object value()

Question 7

Was kann ein Knoten alles sein?

Answer 7

Der Wurzelknoten des gesamten Baumes
Der Wurzelknoten eines Teilbaums
Wenn der Knoten links und rechts null hat, also keine Kinder, dann ist er ein Blatt(leaf)

Question 8

Nenne die drei Traversierungsarten für einen Baum

Answer 8

Inorder- Traversierung
Preorder-Traversierung
Postorder-Traversierung

Question 9

Was ist die Traversierung eines binären Baumes?

Answer 9

Das systematische besuchen aller Knoten in einer bestimmten Reihenfolge

Question 10

Wie funktioniert die Inorder-Traversierung?

Answer 10

Reihenfolge LVR
Er geht immer soweit wie es geht in die Tiefe, um links zu erreichen. Siehe Bild:
https://i.imgur.com/FcHS9Z9.png

Question 11

Wie funktioniert die Preorder-Traversierung?

Answer 11

Reihenfolge VLR
https://i.imgur.com/mSZPbmg.png

Question 12

Wie funktioniert die Postorder-Traversierung?

Answer 12

Reihenfolge LRV
https://i.imgur.com/IcCURwJ.png

Question 13

Erkläre wie die Tiefensuche bei einem binären Baum funktioniert

Answer 13

Man geht links vor rechts in die Tiefe.
Wenn man ganz unten angekommen ist, geht man den nächsten Pfad der rechtsabgeht wieder links vor rechts in die Tiefe.
https://i.imgur.com/Kel3XWD.png

Question 14

Erkläre die Breitensuche im binären Baum

Answer 14

Man fängt oben an der Wurzel an zu zählen und dann Ebene für Ebene von oben links nach unten rechts
https://i.imgur.com/9yZ3DYu.png

Question 15

Erkläre wie der Rekrusive anzahlKnoten(Baum b) funktioniert

Answer 15

Der Algorithmus fängt bei der Wurzel an. Hier ist der Zähler bereits bei 1. Jetzt ruft sich die Methode rekursiv aber mit linker und rechter tochter auf. Sollte mind. eins existieren, steigt der Zähler wieder um +1.

Solange bis keine Tochter mehr da empty(), dann return 0.

Code:
public static int anzahlKnoten(Baum b){
if(b.empty()) return 0;
else return 1 + anzahlKnoten(b.left) + Anzahl Knoten(b.right());
}

Question 16

Was ist ein Suchbaum

Answer 16

Ein binärer Baum, bei dem alle Einträge des Teilbaums links vom Knoten x kleiner sind, und rechts größer. https://i.imgur.com/aMov34R.png

Question 17

Warum hat man Suchbäume entwickelt?

Answer 17

Eine sehr effiziente Datenstruktur, mit der Lookup, insert und delete sehr effizient geht.

Question 18

Wie ist die Komplexität des Suchbaums. Nenne Best case, Worst case & Average case

Answer 18

BestCase (Jeder Knoten hat zwei Töchter) ausgenommen Blätter (leaf)
h = log(n) Wegknoten
h == höhe
n == Anzahl der Knoten

Worst Case: Elemente untereinander eingegeben
Der Baum wird zur Liste…
Aufwand 0(n)

Average case: O(log(n))

Question 19

Was ist ein AVL-Baum?

Answer 19

Ein ausgeglichener binärer Suchbaum. Das bedeutet: Die Höhen der Töchterknoten unterscheiden sich maximal um 1.

Question 20

Ein unausgeglichener Baum hat irgendwo einen Knoten, der unausbalancierte Kinder hat.
Nenne die Bezeichnungen, um die Position dieses unausgeglichenen Knotens zu finden.

Answer 20

Man unterscheidet zwischen vier Fällen. Man guckt an welcher Position ausgehend von der Wurzel, der unausgeglichene Knoten hinzugefügt wurde.
LL == Linker Teilbaum Linkes Kind
RR == Rechter Teilbaum Rechtes kind
LR == Linker Teilbaum Rechtes Kind
RL == Rechter Teilbaum Linkes Kind

Question 21

Unbalancierte Wurzel LL, welche Rotation macht man?

Answer 21

Eine Rechtsrotation, sodass die Wurzel des Fehlerhaften Teilbaums nun die Wurzel des gesamten Baumes ist.

Question 22

Unbalancierte Wurzel RR, welche Rotation macht man?

Answer 22

Eine Linksrotation, sodass die Wurzel des Fehlerhaften Teilbaums nun die Wurzel des gesamten Baumes ist.

Question 23

Unbalancierte Wurzel LR, welche Rotation macht man?

Answer 23

Eine Doppelrotation, sodass der Vater des Fehlerhaften Elements nun die Wurzel des gesamten Baumes ist.
Das Fehlerhafte Element wird dann korrekt einsortiert.

Question 24

Unbalancierte Wurzel RL, welche Rotation macht man?

Answer 24

Eine Doppelrotation, sodass der Vater des Fehlerhaften Elements nun die Wurzel des gesamten Baumes ist.
Das Fehlerhafte Element wird dann korrekt einsortiert.

Question 25

Unbalancierte Wurzel LL, welche Rotation macht man?

Question 26

Was ist ein Heap

Answer 26

Ein binärer Baum, bei dem alle Ebenen von links nach rechts besetzt sind. Lediglich die letzte muss nicht vollständig besetzt sein. Mind. jedoch ein Element, sonst existiert die Ebene nicht.
Der Vater ist immer <= der Töchter

Question 27

Wenn man in einem Heap ein neues Element hinzufügt, wie findet man dann für das Element die richtige Position?

Answer 27

Man vergleicht das Element mit jeweils dem Vater, wenn Element < Vater, tauscht man die Positionen der Elemente.

Question 28

Was ist Hashing?

Answer 28

Zum abspeichern von Objekten an einem bestimmten Index(Speicheradresse) verwendet man eine Hashfunktion. Diese rechnet einem schnell, die Adresse für das zu speichernde Objekt aus.

Question 29

Unterschied offenes und geschlossenes Hashing

Answer 29

Beim offenen werden bei Kollisionen, Listen für dieses Index erstellt, in dem alle Objecte drin stehen.

Beim geschlossenen Hashing wird, wenn ein Platz bereits belegt ist, sondiert oder nochmal gehashed.
Idee ist, dass man relativ schnell ausgehend von dem eigentlich errechneten Platz, einen neuen leeren findet.

Question 30

Nenne die Anzahl der Schritte mitdouble Hashing für die erfolglose Suche und die erfolgreiche Suche

Answer 30

alpha = Auslastungsfaktor
Erfolglos = 1/(1-alpha)
Erfolgreich = -ln(1-alpha)/alpha

Question 31

In einem Heap.. Der Vater hat Index 27, welchen Index hat der linke Sohn?

Answer 31

2*i+1 = 55

Question 32

Welchen Index hat der Vater eines Elements mit der Indexnummer 28?

Answer 32

(j-1)/2 = 13 (abgerundet)

Question 33

Schreibe in java das Interface für den abstrakten Datentyp Schlange

Answer 33

https://i.imgur.com/f7nfSkv.png

Question 34

Schreibe den java code für das auslesen der Höhe eines Baumes

Answer 34

Bild

Question 35

Schreibe java code für die inorder Traversierung

Answer 35

https://i.imgur.com/XlQejds.png

Question 36

K wird entfernt, wie wird reorgansisiert? Es gibt zwei Möglichkeiten
https://i.imgur.com/iuJSnor.png

Answer 36

https://i.imgur.com/QN4p33c.png

Question 37

An welchen Knoten ist unbalanced. Rotiere Korrekt, um AVL Baum herzustellen
https://i.imgur.com/jJyFkeY.png

Answer 37

Wurzel 76 und neun
https://i.imgur.com/z4NE1Vo.png

Die oberste Wurzel wo ein Fehler auftritt, wird bearbeitet.

Question 38

Erkläre den Floyds Algorithmus: All Pairs Shortest Path

Answer 38

Man erstellt zwei Matrizen. Eine Distanzmatrix und eine Wegematrix. Hier fängt man an, dass man nur einen Knoten zur Hilfe nehmen darf, um zum Ziel zu kommen. In den darauffolgenden macht man dasselbe aber man darf jeweils einen anderen Knoten zur Hilfe nehmen. Es gibt dann n Distanz und Wegematrixen mit n = Anzahl der Knoten.
Die letzte Distanzmatrix zeigt an, wie die kürzesten Strecken zwischen den Punkten ist. Man ändert nämlich nur etwas an der Tabelle, wenn sich ein kürzerer Weg ergibt.