Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithmen und Datenstrukturen > Allgemeine Fragen > Flashcards

Allgemeine Fragen Flashcards

1
Q

Welche Eigenschaften sind für Binäre Suchbäume charakteristisch?

A

Für jeden Knoten sind die Schlüssel des linken Unterbaums kleiner und im rechten größer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was ist der Grad in einem Baum?

A

Die maximale Anzahl von Unterbäume.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was ist die Ebene in einem Baum?

A

Der Abstand zwischen einem Knoten bis zur Wurzel( => Wurzelknoten ist Ebene 0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist die Höhe eines Baumes?

A

Höchste Ebene eines Baumes (=> Baum mit nur Wurzel ist 0 hoch)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Wie wird die Baumwurzel in einem binären Baum realisiert?

A

Über eine Variable TreeNode <t> root.</t>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wie wird auf den binären Suchbaum von “außen” zugegriffen (die bekannten Methoden sind private)?

A 
Bspw.
public boolean contains(E key){
return lookup(root, key) != null;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Was ist die Schwachstelle von Binären Suchbäumen?

A
  • Struktur ist abhängig von der Einfügereihenfolge
  • Maximum/ Minimum ineffizient
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist das Ziel gewesen, von normalen binären Suchbäumen “wegzukommen”?

A

Versuch, eine GARANTIERTE Laufzeit von O(log(N)) zu realisieren und nicht O(N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was sind die Vorteile von Binären Suchbäumen?

A
  • Lookup nahezu so effizient wie auf Arrays
  • Einfügen/ Löschen effizienter als Arrys (kein Verschieben notwendig)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was ist ein 2-3-Baum?

A

Ein Baum, dessen Knoten entweder

  • 1 Schlüssel und 2 Unterbäume hat
  • 2 Schlüssel und 3 Unterbäume hat
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Zu welcher Kategorie gehören 2-3-Bäume?

A

Balancierte Suchbäume

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist der Vorteil an Balancierten Suchbäumen?

A

Lookup, Minimum, Maximum, Einfügen, Löschen in garantiert in O(log(N)) realisieren

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Wie sind Balancierte Suchbäume charakterisiert?

A
  • Alle Blätter in “ähnlichem” Abstand zur Wurzel
  • “Entartungen” werden vermieden
  • Worst Case Szenario nahe an mittlerer Laufzeit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Was ist die Worst-Case-Performance bei Suchen und Einfügen bei 2-3-Bäumen?
Unterscheidet sich diese vom Garantierten Fall?

A

Nein, die Performance ist auch dabei O(log(N))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Begründe, wieso das Worst Case Szenario in 2-3-Bäumen ebenfalls O(log(N)) ist.

A

Worst Case Knotenversuche ergibt sich aus Baumhöhe. Diese ist bei 2-3-Bäumen dann log2(N), weil der Baum im Worst Case ausschließlich aus Binären Knoten besteht (Best Case: Alles Tertiäre Knoten)
Pro Knoten sind damit im Worst Case 2 Schlüsselvergleiche (Best Case: 3 Vergleiche) notwendig –> Beschränkung durch Konstante.

=> O(log(N))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wieso sind 2-3-Bäume unattraktiv?

A

Vielzahl an Fallunterscheidungen benötigt (mehrere Schlüssel pro Knoten)

  • Unterschiedliche Implementierung (Binäre und Tertiäre Knoten)
  • Einfügen Fallunterscheidung. Ggf Umwandlung Binär in Tertiär
  • > Auswahl des Mittleren Knotens fordert erweiterten Vergleich und Zuordnungen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Wodurch wird die Begrifflichkeit von Balancierten BINÄREN Suchbäumen festgemacht?

A

Höhe des Baums, bzw. Höhenunterschied der Teilbäume (möglichst geringer Unterschied)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Wie ist die Höhe eines leeren Binären Suchbaums definiert?

A

Gar nicht

19
Q

Was ist ein leerer Suchbaum beim erweiterten binären Bäumen?

A

Spezielle Blattknoten (Externe Knoten)

20
Q

Sind binäre Suchbäume ebenfalls perfekt (Baumstruktur) wie 2-3-Bäume? Falls Nein: Wieso und in welchen Fällen ist dies nicht der Fall?

A

Nein, da bei bestimmter Schlüsselzahl eine neue Ebene erstellt wird, die nicht vollständig ist.

Nur vollständig bei Schlüsselanzahl, die in 2^N - 1 dargestellt werden kann

21
Q

Welche Anzahl Schlüssel können 2-3-Bäume mindestens und höchstens enthalten? (Abhängig von der Höhe H)

A

Zwischen 2^H - 1 bis 3^H - 1

22
Q

Was bedeutet bei Binären Suchbäumen die Begrifflichkeit der Vollständigkeit?

A

Die höchste Ebene muss nicht vollständig besetzt sein. Alle anderen jedoch schon.

23
Q

Welche 5 Eigenschaften haben Rot-Schwarz-Bäume?

B-WARE

A

Blätter - Blätter sind Schwarz
W - Wurzel Schwarz
A - Anzahl Schritte der Pfade(schwarze Knoten) bis alle Nachfolgeblätter immer gleich
R - Rote Knoten haben immer Schwarze Kindsknoten
E - Knoten Entweder Rot oder Schwarz

24
Q

Was ist nach Sedgewick bezüglich der Roten Kanten (Kantenfarbe = Farbe des Kindsknoten) entscheidend?

A

Nur linke Kanten dürfen rot sein!

25
Q

Welche Farbe hat ein neu eingefügter Knoten zunächst immer?

A

Rot

26
Q

Was muss bei der Implementiertung der öffentlich Klasse zum Einfügen eines Knotens in ein RB-Set explizit berücksichtigt werden?

A

Die Farbe des root muss auf schwarz gesetzt werden, da der Rekursive Aufstieg beim Einfügen nicht die root berücksichtigt. Stellt der neue Schlüssel jedoch die root dar, ist dieser immer als rot initiiert.

@Override
public MyRBSet insert<e>(E key){<br></br>this. root = insert(this.root, key);</e>

this.root.red = false;
return this;
}

27
Q

Wie ist die maximale Baumhöhe eines RB-Baums?
Welche Laufzeitkomplexität hat damit die Anzahl Schlüsselvergleiche im Worst Case?

A

2*log2(N)

–> O(log(N))

28
Q

Welche Laufzeitkomplexität hat bei RBT das Einfügen und wieso?

A

Lookup in maximal O(log(N)) und das Rotieren der Knoten ist konstant in O(1). Dadurch insgesamt O(log(N))

29
Q

Nenne die Anzahl der erforderlichen Schritte der Operationen look up, insert/delete, minimum/maximum für Arrays(unsortiert), Arrays(sortiert), Binärer Suchbaum, RB-Baum
im Worst Case!

A
30
Q

Was ist ein Rang beim Binären Suchbaum (RBT)? Wofür kann dieser genutzt werden?

A

Die Anzahl Knoten im LINKEN Teilbaum.
Realisierung von dem indizierten Zugriff auf Knoten. Durch den Rang kann der benötigte Index schnell gefunden werden

31
Q

Wann wird bei Binären Suchbäumen mit Rang-Information in den linken bzw. den rechten Teilbaum abgestiegen?

Wann ist der gesuchte Index gefunden?

A

Links: 0<= i = R-2 mit index i
Rechts: R<= i mit i - R

Gefunden bei: i = R - 1

32
Q

Wann wird bei Binären Suchbäumen mit Rang-Information zum Einfügen in den linken bzw. den rechten Teilbaum abgestiegen?

Wann ist die Einfügestelle gefunden?

A

Links: 0<= i = R-1mit index i
Rechts: R<= i mit i - R

Gefunden, sobald externes Blatt erreicht.
Bei Aufstieg Erhöhung des Rangs der Knoten um je 1, wenn Abstiegt linksseitig war

33
Q

Was ist hinsichtlich des Speicherbedarfs bei RBT zu sagen?

A

Benötigt nur 1 Bit mehr Speicherbedarf (Boolean Black/Red)

34
Q

Was ist die minimale und die maximale Höhe eines RBT

A

Minimal: log2(N)
Maximal: 2 * log2(N)

35
Q

Was ist die Haupteigenschaft an Heaps?

A

ALLE Schlüssel der Unterbäume kleiner/größer als der Knoten

36
Q

Wieso werden Heaps nicht in Arrays dargestellt?

A

Entartete Bäume führen zu Arrays, deren Größe in Abhängigkeit von N exponentiell ansteigt.

37
Q

Wie werden Heaps in Arrays realisiert? Wie erfolgt der Zugriff auf zB Eltern- bzw. Kindsknoten?

A

Wurzel ist an Index = 0;
parent = (i - 1) / 2;
left = 2 * i + 1:
right = 2 * 1 + 2:

38
Q

Wieso sind heaps ansonsten gut geeignet für die Repräsentation in Arrays?

A
  • Operationen können so implementiert werden, dass die Vollständigkeit des Binärbaums bestehen bleibt, indem von links nach rechts eingefügt wird –> Index nächsten “freien Knotens” bekannt
  • Vorteilhaft, da keine Rotation, sondern nur Schlüsseltausche benötigt
  • Stehts vollständige Binärbäume mit Höhe log2(N)
39
Q

Heaps: Wie kann der minimale und wie der maximale Index einer Ebene bestimmt werden?

A

Ebenen von 0 - H;

Minimal: 2^Ebene - 1
Maximal 2^Ebene

40
Q

Was sind Hashs? Was ist das Ziel davon?

A

Arrays. Elemente werden per hashCode in Zahlen umgewandelt und diese per Logik (Modulo der Array-Länge) zu einem Index umgewandelt.

Ziel ist, eine unendliche Menge von Zahlen auf eine endliche Größe zu beschränken.

41
Q

Was passiert im Hash, wenn mehrere Elemente die gleichen Indeces zugewiesen werden?

A

Zuweisung per linerarer Liste.

42
Q

In Hashs werden Lineare Listen verwendet, welche bei Lookup eine Laufzeitkomplexität von O(N) haben. Diese führt zu einer Gesamtkomplexität von O(N).

Wie wird dies in Hashs gelöst?

A

Vergrößerung des Arrays, sobald eine bestimmte Auslastung erreicht ist. Wenn bspw, im Schnitt mindestens jedes zweite Arrayfeld belegt ist, wird das Array um den load_factor vergrößert.

43
Q
A

Algorithmen und Datenstrukturen (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions