Deutsch
Menü

Datenstrukturen und Algorithmen

In einer Hashtabelle der Größe 7 (Positionen 0 bis 6) werden mit der Hashfunktion h(k) = k mod 7 die Schlüssel 10, 17, 24 und 3 in dieser Reihenfolge gespeichert. Kollisionen werden durch lineares Sondieren aufgelöst, das jeweils eine Position weiterrückt (nach 6 folgt 0), bis ein freier Platz gefunden ist. An welcher Position wird der Schlüssel 3 gespeichert?

  1. APosition 3
  2. BPosition 4
  3. CPosition 6
Antwort und Erläuterung anzeigen

Antwort: C. Position 6

Alle vier Schlüssel lassen bei Division durch 7 den Rest 3, daher prüft jeder zuerst Position 3. Der Schlüssel 10 kommt an Position 3; 17 findet Position 3 belegt und kommt an Position 4; 24 findet die Positionen 3 und 4 belegt und kommt an Position 5. Der Schlüssel 3 findet die Positionen 3, 4 und 5 belegt und wird an Position 6 gespeichert. Wie dieses Beispiel zeigt, ballen sich beim linearen Sondieren die belegten Positionen zusammen (Clustering), sodass später eintreffende Schlüssel mehr Sondierschritte brauchen.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Welche Aussage vergleicht die Verkettung (Chaining: Elemente derselben Position werden in einer verketteten Liste verbunden) und die offene Adressierung (eine andere freie Position innerhalb der Tabelle wird gesucht) als Verfahren zur Kollisionsauflösung in Hashtabellen richtig? Der Belegungsfaktor ist die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße.
  2. Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?
  3. Auf 1000 verschiedene, aufsteigend sortierte Werte wird eine binäre Suche angewendet. Ein Vergleich liefert jeweils „gleich“, „kleiner“ oder „größer“. Wie viele Vergleiche sind höchstens nötig, erfolgreiche und erfolglose Suchen zusammengenommen?
  4. Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?
  5. Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?