[UE ALGO 2 Homepage] Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

5. Übung - abzugeben am 10. 11. 1998 in Ihrer Übungsgruppe


5.a.1 Theorie

Gegeben sei eine Hashtabelle mit der Länge 7. Vervollständigen Sie folgende Tabellen - verwenden Sie dabei das Doppelhash-Verfahren nach der Quotientenmethode.

Berechnungstrace:
k 9 5 17 26 33 1
f0(k)            
c            

Formel: fi(k) = (f0(k) + i*c) MOD p

Hash-Tabelle:
0 1 2 3 4 5 6
             

 

5.a.2 Theorie

Vergleichen Sie lineare und quadratische Kollisionsstrategien mit dem Verfahren aus Beispiel a.1 und erläutern Sie Vor- und Nachteile. Welche Strategie erweist sich im obigen Beispiel als die günstigste? Halten Sie dieses Ergebnis für repräsentativ? Ist der sich ergebende Belegungsfaktor ein optimaler/plausibler Wert?


5.b Programm

Ändern Sie Ihr Programmbeispiel 4a+4b wie in der Übung besprochen. Stellen Sie auch von linearer Kollisionsstrategie auf Quotientenmethode um. Zeigen Sie im Kommentar genau, welche Änderungen dazu notwendig sind. Was ist zu ändern, wenn Sie auf quadratische Kollisionsstrategie umstellen wollen (Beschreibung/Kommentar)?


5.c Theorie

Zur Speicherung einer Adjazenzmatrix für ungerichtete Graphen gibt es unter anderem folgende Möglichkeiten:

Vergleichen Sie diese vier Möglichkeiten hinsichtlich ihres Platzbedarfs.

Knotenanzahl: 50 500 5.000
Kantenanzahl (angenommen): 70 700 8.000.000
Normale Adjazenzmatrix (rechteckig) Bytes Bytes Bytes
Gepackte Adjazenzmatrix (rechteckig)   Bytes Bytes Bytes
Gepackte Dreiecks-Adjazenzmatrix Bytes Bytes Bytes
Hashing Bytes Bytes Bytes


Last modified: hoermanseder@fim.uni-linz.ac.at 98-11-02