Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Algorithmen und Datenstrukturen > Suchen > Flashcards

Suchen Flashcards

1
Q

Beschreib einen binären Suchbaum

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

Was ist eine Traversierung?

A

Systematisches Durchlaufen aller Knoten eines Baumes

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

Beschreib die Preorder Travesierung

A

Wurzel, linker Teilbaum, rechter Teilbaum

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

Beschreib die Postorder Travesierung

A

linker Teilbaum, rechter Teilbaum, Wurzel

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

Beschreib die Inorder Travesierung

A

linker Teilbaum, Wurzel, rechter Teilbaum

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

Wozu führt ein Inorder Treewalk auf einen binären Suchbaum?

A

aufsteigend Sortierte Liste

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

Welche Laufzeit benötigt ein Inorder Treewalk?

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

Beschreib die Suche in binären Suchbäumen

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

Welche Laufzeit hat die Suche in einem Binärbaum?

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

Wie löscht man in einem binären Suchbaum?

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

Welche Laufzeit hat Tree-Delete?

A

O(h)
mit h, Höhe vom Baum

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

Beschreib Rot-Schwarz-Bäume

ohne RS-Eigenschaften

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

Was gilt für die Wurzel in einem RS-Baum?

A

sie ist schwarz

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

Was gilt für rote Knoten in einem RS-Baum?

A

Für jeden roten Knoten gilt: beide Nachfolger sind schwarz.

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

Was gilt für jeden Knoten und dessen Pfade in einem RS-Baum?

A

Für jeden Knoten x gilt: Alle Pfade von x zu einem Blatt enthalten die gleiche Anzahl bh(x) schwarzer Knoten.

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

Wie hoch ist ein RS-Baum maximal?

A

“

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

Wie bestimmt man das Minimum in einem binären Suchbaum?

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

Wie bestimmt man den Successor in einem binären Suchbaum?

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

Welche Laufzeit hat TREE-MINIMUM?

A

O(h)

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

Welche Laufzeit hat TREE-SUCCESSOR?

A

O(h)

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

Wie fügt man in einen binären Suchbaum ein?

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

Welche Laufzeit haben SEARCH(), MINIMUM(), MAXIMUM(), SUCCESSOR()
und PREDECESSOR() in einem RS-Baum?

A

O(h) = O(log n)

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

Welche Laufzeit haben TREE-INSERT() und TREE-DELETE() in einem RS-Baum?

A

O(log n)

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

Wie funktioniert eine Linksroation in einem Suchbaum?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Wie fügt man in RS-Bäumen ein?
26
Welche Eigenschaften können nach dem Einfügen in ein RS-Baum verletzt sein?
1. Die Wurzel ist schwarz, falls z die Wurzel ist 2. Für jeden roten Knoten gilt: beide Nachfolger sind schwarz, falls z.p.color = ROT ist
27
Was ist die Idee von RB-INSERT-FIXUP?
Korrigiere die Eigenschaftsverletzung "Für jeden roten Knoten gilt: beide Nachfolger sind schwarz" lokal oder verschiebe diese sukzessiv zum Vorgänger. Wenn die Wurzel erreicht wird, korrigiere Eigenschaft "Die Wurzel ist nicht schwarz"
28
Wie löscht man aus Rot-Schwarz-Bäumen?
29
Welche RS-Eigenschaften können durch das Entfernen eines Knotens verletzt sein?
1. Wurzel ist schwarz, falls y = T.root und x.color = ROT 2. Für jeden roten Knoten gilt: beide Nachfolger sind schwarz, falls y.p.color = ROT und x.color = ROT 3. Für jeden Knoten x gilt: Alle Pfade von x zu einem Blatt enthalten die gleiche Anzahl bh(x) schwarzer Knoten.
30
Was ist die Laufzeit von RB-INSERT, -DELETE und -SEARCH?
O(log n)
31
Was gilt für jeden Knoten in einem AVL-Baum?
32
Wie viele Blätter hat ein AVL-Baum der Höhe h maximal?
33
Wie kann man die Anzahl der Knoten in einem AVL Baum berechnen?
34
Wie fügt man in AVL-Bäumen ein?
35
Welche vier Fälle gibt es beim Enfügen von Knoten in den AVL-Baum?
36
Gib die richtigen Rotationen an
37
Wie heißt ein Suchbaum mit Höhe O(log n)?
balanciert
38
Welche Höhe hat ein Suchbaum im worst case?
39
In welcher Laufzeit erzeugen INSERT und DELETE eines AVL-Baumes einen balancierten Baum?
O(log n)
40
Was ist die Idee von Hashing?
Berechne aus dem Schlüssel einen Index h(key), speichere die Daten in einem Array an Position h(key). Im RAM-Modell erfolgt der Array- Zugriff in konstanter Zeit.
41
Was sind Probleme beim Hashing?
* Mehrere Schlüssel werden auf den gleichen Index abgebildet: Kollision * Der Index-Raum ist viel größer als die zu speichernden Daten
42
In welcher Laufzeit sind INSERT, DELETE, SEARCH beim Hashing realisierbar?
O(1)
43
Wie funktioniert Kollisionsauflösung durch Verkettung?
44
Wie berechnet man den Belegungsfaktor?
44
In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolglose Suche?
Θ(1+ α) erwartete Laufzeit
45
In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolgreiche Suche?
Θ(1+ α) erwartete Laufzeit.
46
Wie kann man Zeigen, dass die Suche in einer Hash-Tabelle in konstanter Zeit unter Annahme unabhängigen, gleichverteilten Hashings erfolgt?
47
Nenn Anforderungen an eine Hashfunktion
48
Was ist die Divisionmethode? | Wie kann man m optimal wählen?
49
Was ist die Multiplikationsmethode?
50
Was ist statisches Hashing?
Verwendung einer fest definierten Hashfunktion * Divisionsmethode und Multiplikationsmethode (implementiert als Multiply- Shift-Methode) sind statische Hashverfahren
51
Was ist randomisiertes Hashing?
Zufällige Auswahl einer Hashfunktion unabhängig von der Schlüsselmenge
52
Wann gilt eine Hashfunktion als universell?
Wenn die Anzahl aller möglichen Kollisionen kleiner ist, als die Anzahl an Funktionen durch m
53
Wie hoch ist die Wahrscheinlichkeit einer Kollision bei einer Menge an Hashfunktionen, die universell sind?
54
Wie hoch ist die die erwartete Laufzeit von p INSERT-, SEARCH- und DELETE- Operationen mit höchstens O(m) INSERT-Operationen bei universellem Hashing mit Verkettung mit m Plätzen?
O(p)
55
Was sind Nachteile von Hashing mit Verkettung?
56
Wie funktioniert Offene Adressierung?
57
Was ist sondieren?
Sukzessives Überprüfen der Hashtabelle nach freien Plätzen
58
Was ist eine Sondierungssequenz?
Folge von Hashadressen, die für einen Schlüssel k nach offenen Stellen durchsucht werden
59
# Wir nutzen Hashing mit Sondierung Was passiert, wenn ein Schlüssel k gelöscht wird? Wie löst man das Problem?
Schlüssel, die nach k gespeichert werden, können nicht wiedergefunden werden, da die Repeat-Schleife bei T[j]=NIL terminiert!
60
Was sollte in Anwendungen mit vielen DELETE-Operationen verwendet werden? Verkettung oder Sondierung
Verkettung
61
Was ist lineares Sondieren?
62
Was ist quadratisches Sondieren?
63
Wann entsteht primäres Clustern?
Lineares Sondieren: Bei insert ist die Wahrscheinlichkeit groß, lange Ketten zu verlängern
64
Wann entsteht sekundäres Clustern?
quadratisches Sondieren: Bei Kollisionen h‘(k) = h‘(k‘) haben beide Schlüssel die gleiche Sondierungsfolge
65
Was ist doppeltes Hashing?
66
Für eine Hashtabelle mit offener Adressierung und Belegungsfaktor α < 1: Wie hoch ist die erwartete Anzahl der Sondierungen bei erfolgloser Suche unter der Annahme des gleichmäßigen Hashings ohne Löschen höchstens?
1 / (1 - α)
67
Wie viele Sondierungen benötigt unter der Annahme des gleichmäßigen Hashings HASH-INSERT() im Mittel höchstens?
1/(1- α)
68
Für eine Hashtabelle mit offener Adressierung und Belegungsfaktor α < 1 ist die Anzahl der erwarteten Sondierungen bei erfolgreicher Suche unter den Annahmen (1) gleichmäßiges Hashing ohne Löschen und (2) gleiche Wahrscheinlichkeit für den Suchschlüssel höchstens?
(1/ α ) * ln(1 / (1 - α))
69
Wie funktioniert Brents Insert Operation?
70
Was ist der Vorteil offener Adressierung?
speichereffizienter als Verkettung
71
Welche Methode ist bei offener Adressierung zu bevorzugen?
Doppeltes Hashing
72
Wie schnell findet man Elemente, wenn man mit Brents INSERT-Operation hasht?
in durchschnittlich weniger als 2.5 Sondierungsschritten
73
Was ist der Nachteil an Brents INSERT-Operation?
Schnelle Suche geht auf Kosten auf Kosten einer etwas langsameren INSERT-Operation
74
Gibt es perfekte Hashverfahren mit Worst- Case Laufzeit O(1) für INSERT und SEARCH?
Ja, für statische Datenmengen

Algorithmen und Datenstrukturen (9 decks)

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