Brainscape's Knowledge GenomeTM

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


See full index

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
Q

Wie fügt man in RS-Bäumen ein?

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

Welche Eigenschaften können nach dem Einfügen in ein RS-Baum verletzt sein?

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Was ist die Idee von RB-INSERT-FIXUP?

A

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”

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

Wie löscht man aus Rot-Schwarz-Bäumen?

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

Welche RS-Eigenschaften können durch das Entfernen eines Knotens verletzt sein?

A
  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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Was ist die Laufzeit von RB-INSERT, -DELETE und -SEARCH?

A

O(log n)

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

Was gilt für jeden Knoten in einem AVL-Baum?

A
32
Q

Wie viele Blätter hat ein AVL-Baum der Höhe h maximal?

A
33
Q

Wie kann man die Anzahl der Knoten in einem AVL Baum berechnen?

A
34
Q

Wie fügt man in AVL-Bäumen ein?

A
35
Q

Welche vier Fälle gibt es beim Enfügen von Knoten in den AVL-Baum?

A
36
Q

Gib die richtigen Rotationen an

A
37
Q

Wie heißt ein Suchbaum mit Höhe O(log n)?

A

balanciert

38
Q

Welche Höhe hat ein Suchbaum im worst case?

A
39
Q

In welcher Laufzeit erzeugen INSERT und DELETE eines AVL-Baumes einen balancierten Baum?

A

O(log n)

40
Q

Was ist die Idee von Hashing?

A

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
Q

Was sind Probleme beim Hashing?

A
  • Mehrere Schlüssel werden auf den gleichen Index abgebildet: Kollision
  • Der Index-Raum ist viel größer als die zu speichernden Daten
42
Q

In welcher Laufzeit sind INSERT, DELETE, SEARCH beim Hashing realisierbar?

A

O(1)

43
Q

Wie funktioniert Kollisionsauflösung durch Verkettung?

A
44
Q

Wie berechnet man den Belegungsfaktor?

A
44
Q

In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolglose Suche?

A

Θ(1+ α) erwartete Laufzeit

45
Q

In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolgreiche Suche?

A

Θ(1+ α) erwartete Laufzeit.

46
Q

Wie kann man Zeigen, dass die Suche in einer Hash-Tabelle in konstanter Zeit unter Annahme unabhängigen, gleichverteilten Hashings erfolgt?

A
47
Q

Nenn Anforderungen an eine Hashfunktion

A
48
Q

Was ist die Divisionmethode?

Wie kann man m optimal wählen?

A
49
Q

Was ist die Multiplikationsmethode?

A
50
Q

Was ist statisches Hashing?

A

Verwendung einer fest definierten Hashfunktion
* Divisionsmethode und Multiplikationsmethode (implementiert als Multiply- Shift-Methode) sind statische Hashverfahren

51
Q

Was ist randomisiertes Hashing?

A

Zufällige Auswahl einer Hashfunktion
unabhängig von der Schlüsselmenge

52
Q

Wann gilt eine Hashfunktion als universell?

A

Wenn die Anzahl aller möglichen Kollisionen kleiner ist, als die Anzahl an Funktionen durch m

53
Q

Wie hoch ist die Wahrscheinlichkeit einer Kollision bei einer Menge an Hashfunktionen, die universell sind?

A
54
Q

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?

A

O(p)

55
Q

Was sind Nachteile von Hashing mit Verkettung?

A
56
Q

Wie funktioniert Offene Adressierung?

A
57
Q

Was ist sondieren?

A

Sukzessives Überprüfen der Hashtabelle nach freien Plätzen

58
Q

Was ist eine Sondierungssequenz?

A

Folge von Hashadressen, die für einen Schlüssel k nach offenen Stellen durchsucht werden

59
Q

Wir nutzen Hashing mit Sondierung

Was passiert, wenn ein Schlüssel k gelöscht wird? Wie löst man das Problem?

A

Schlüssel, die nach k gespeichert werden, können nicht wiedergefunden werden, da die Repeat-Schleife bei T[j]=NIL terminiert!

60
Q

Was sollte in Anwendungen mit vielen DELETE-Operationen verwendet werden?
Verkettung oder Sondierung

A

Verkettung

61
Q

Was ist lineares Sondieren?

A
62
Q

Was ist quadratisches Sondieren?

A
63
Q

Wann entsteht primäres Clustern?

A

Lineares Sondieren: Bei insert ist die Wahrscheinlichkeit groß, lange Ketten zu verlängern

64
Q

Wann entsteht sekundäres Clustern?

A

quadratisches Sondieren: Bei Kollisionen h‘(k) = h‘(k‘) haben beide Schlüssel die gleiche Sondierungsfolge

65
Q

Was ist doppeltes Hashing?

A
66
Q

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?

A

1 / (1 - α)

67
Q

Wie viele Sondierungen benötigt unter der Annahme des gleichmäßigen Hashings HASH-INSERT() im Mittel höchstens?

A

1/(1- α)

68
Q

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?

A

(1/ α ) * ln(1 / (1 - α))

69
Q

Wie funktioniert Brents Insert Operation?

A
70
Q

Was ist der Vorteil offener Adressierung?

A

speichereffizienter als Verkettung

71
Q

Welche Methode ist bei offener Adressierung zu bevorzugen?

A

Doppeltes Hashing

72
Q

Wie schnell findet man Elemente, wenn man mit Brents INSERT-Operation hasht?

A

in durchschnittlich weniger als 2.5 Sondierungsschritten

73
Q

Was ist der Nachteil an Brents INSERT-Operation?

A

Schnelle Suche geht auf Kosten auf Kosten einer etwas langsameren INSERT-Operation

74
Q

Gibt es perfekte Hashverfahren mit Worst- Case Laufzeit O(1) für INSERT und SEARCH?

A

Ja, für statische Datenmengen

Algorithmen und Datenstrukturen (8 decks)

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