Aufgabe 33 (8 Punkte)
Gegeben sei folgender Graph:
Kodieren Sie diesen Graphen mit 9 Knoten als Nachbarschaftsliste
(2 Punkte). Unter Zusammenhangskomponente versteht man
die zusammenhängenden Teilgraphen (Im Beispiel gibt
es 2 Stück). Entwerfen Sie einen Algorithmus, der alle Zusammenhangskomponenten
findet. (4 Punkte) Entwerfen Sie eine Datenstruktur ähnlich der Nachbarschaftsliste
für die Zusammenhangskomponenten.(2 Punkte)
Aufgabe 34 (6 Punkte)
A,B,X1,Y1,X2,Y2,A1,A2,B1,B2 sind Werte, die mittels einer
Hashfunktion zu speichern sind. Die Codierung sei durch den 8 Bit
ASCII
Code (7 Bit + Parität beim höchstwertigen Bit) definiert.
Man beurteile die Eignung von Mitte des Quadrats und Divisionsrest als
Hashfunktion, wenn 64 als Größe des Adressbereichs gewählt
wird. Bei den zweistelligen Werten wird der 16 stellige Code verwendet,
der durch hintereinander Schreiben entsteht.