URL:         /axel/informatik2_ss00_blatt4.html

Die Programmieraufgaben sind alleine zu bearbeiten, die anderen Aufgaben können in Zweiergruppen bearbeitet werden.
 

Aufgabe 7 (2+3+3 Punkte)
In der Vorlesung wurde als Erweiterung einer linearen Liste die doppelt verkettete lineare Liste erwähnt. Damit ist auch das entgegengesetzte Durchlaufen der Daten möglich. Geben Sie ein Definition des Datentyps an. (Beschreibung der Komponenten, d.h. wieviel Zeiger etc., und die Bedeutung der Komponenten. Wie schaut eine leere Liste aus?) (2 Punkte) Beschreiben Sie in einem Pseudocode die Operationen beim Einfügen (3 Punkte) und Löschen (3 Punkte)
 

Aufgabe 8 (3+ 4 + 3 Punkte)
Formulieren Sie den Algorithmus countsort  mittels eines Flussdiagramms. (3 Punkte)  Führen Sie den countsort mit dem Feld der Länge 14 durch, welches sie durch die Verknüpfung Ihrer beiden Matrikelnummern bekommen. Zulässige Eintrage im Feld sind die Ziffern 0-9. (4 Punkte) Ist der Algorithmus countsort stabil? Beweis. (3 Punkte)
 

Ein Sortieralgorithmus ist stabil, wenn  die Reihenfolge von Datensätzen mit gleichen Schlüssel sich während des Sortieralgorithmus nicht ändert.