Prof. Dr. R. Laue                                                                                                                                  SS98
                                Informatik II
                                Übungsblatt 4
                                Abgabe: 4.06.98 bis 10.00 Uhr
 
URL:         /axel/informatik2_ss98_blatt4.html
Dieses  Übungsblatt ist in Zweiergruppen  zu bearbeiten.

Aufgabe 10 (4 Punkte)
Geben Sie die Wahrscheinlichkeit an, daß beim Sortieren eines Feldes der Länge n mit verschiedenen Einträgen Quicksort die maximale Anzahl von Schritten braucht.

Aufgabe 11 (4 Punkte)
Wieviel Vertauschungen braucht ein auf paarweisen Vergleich beruhender Algorithmus mindestens um Ihre (eine Ihrer) Matrikelnummer aufsteigend zu sortieren. Beweis!

Aufgabe 12 (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)