WorksheetsTut04
Total questions: 15
Worksheet time: 8mins
Was ist das Hauptziel von Hashing?
Daten zu sortieren
Daten schnell zu finden
Daten zu komprimieren
Daten zu verschlüsseln
Was bedeutet der Begriff 'Kollision' im Kontext von Hash-Tabellen?
Zwei Schlüssel haben denselben Hash-Wert
Ein Schlüssel hat keinen Hash-Wert
Ein Schlüssel wird gelöscht
Ein Schlüssel wird hinzugefügt
Welche Zeitkomplexität wünschen wir uns von der Operation find(k : Key) von einer Hash-Tabelle?
O(n)
O(log n)
O(1)
O(n^2)
Was ist eine perfekte Hash-Funktion?
Eine Funktion, die Daten sortiert
Eine Funktion, die Daten verschlüsselt
Eine Funktion, die alle Daten komprimiert
Eine Funktion, die keine Kollisionen erzeugt
Was ist die (Worst-Case) Zeitkomplexität für das Entfernen eines Elements in einer Hash-Tabelle mit verketteten Listen? (n = Anzahl Elemente in der Tabelle)
O(n^2)
O(1)
O(log n)
O(n)
Was ist die Rolle des Schlüssels in einer Hash-Tabelle?
Er sortiert die Daten
Er verschlüsselt die Daten
Er komprimiert die Daten
Er identifiziert die Daten
Was ist eine typische Anwendung von Hashing in der Informatik?
Datenkompression
Datenbankabfragen
Datenverschlüsselung
Datenvisualisierung
Was für eine Zeitkomplexität wünschen wir uns für das Einfügen eines Elements in eine Hash-Tabelle?
O(n)
O(1)
O(log n)
O(n^2)
Was ist der Zweck der verketteten Listen beim Hashing mit verketteten Listen?
Speicher Sparen
Schneller Zugriff
Leichtere Implementation
Kollisionen handhaben
Was sind potentielle Probleme bei der Implementierung perfekter Hash-Funktionen?
Sie sind teuer
Sie sind schwer zu finden
Sie sind ineffizient
Sie sind einfach zu implementieren
Ab welcher Anzahl an Leuten sollte man Wetten, das 2 am selben Tag Geburtstag haben?
178
111
23
86
Was ist der Zweck der Hash-Funktion?
Um Daten zu sortieren
Um einen Schlüssel in einen Index umzuwandeln
Um Daten zu verschlüsseln
Um Daten zu komprimieren
Welche ist eine typische Universelle Famillie? (m = Array größe, M = anzahl schlüssel)
a*x mod m
M⋅km⋅a
x+a mod m
xa mod m
Was ist die Idee bei Hashing mit Linearer Suche (Linear Probing)?
Bei voller Zelle einfach weiterlaufen bis eine leere kommt und so Kollisionen handeln
Bei jeder Zelle eine Linked List speichern und so Kollisionen handeln
Einfach das Ergebnis der Hashfunktion wieder einsetzen, bis man eine freie Zelle findet und so Kollisionen handeln.
Was ist der Vorteil von Linear Probing ( im vergleich zu Hashing mit Linked Lists)?
Cache wird besser genutzt
Läuft nie voll
Bessere Laufzeitgarantien bei Universellem Hashing
Einfacher zu Implementieren
