WS 2002/2003 Übung 6
H. Schweppe
Ausgabe: 21.11.2002
Abgabe: 3.12.2002
16.00
Aufgabe 6.1 ( 10 P)
a) (5) Gesucht ist eine "dynamische Implementierung" von Vektoren mit
Hilfe von Feldern ohne Kopieroperationen bei Vergrößerung des Vektors. Die
Schnittstelle lautet:
interface dynamicVector {
//
model: sequence (xi), i=0,... of objects
// inv: MAX = 10000;
public void createDV(int m);
public Object objectAt(int i);
// pre: true
// post: if an object has been
already inserted at
// position i return it, else return null
public void insertDV( Object x);
// pre: true
// post:
for all i >= r objectAt(i) == null
// => x == objectAt(r), &&
r==R+1, insert at rear
public void insertAt(int i, Object x);
// pre: true
// post: objectAt(i) == x
}
Das Feld
soll mit Länge m initialisiert. Hat es bei Aufruf von insertAt(i,obj)
die Gesamtlänge
s = c*m < i, wird es um die Länge k*m mit minimalem k so erweitert
, dass s + k*m > i .
b) (3) wie lauten Abstraktionsfunktion und Repräsentationsinvariante?
c) (2) Welche Laufzeit und welchen Platzbedarf hat der Zugriff auf ein Feldelement
im schlechtesten Fall , wenn n Elemente in das Feld eingefügt wurden.
Aufgabe 6.2 ( 6 P)
a) (4) Gesucht ist ein externer Iterator für
Mengen ganzer Zahlen, die als class
IntSetMixed (siehe Vorlesung, Quelltext
im Netz ) implementiert sind. Testen Sie
den Iterator mit einer lesenden Aktion (z.B. "Iteriere über alle Elemente
und gib den Wert aus").
b(1) ) Geben Sie Gründe an, die für die Verwendung von Iteratoren sprechen.
Welche sprechen dagegen?
c) (1) Warum ist die remove() Operation des
Iterator-Interface kritisch? Geben
Sie ein Beispiel an, aus dem das deutlich wird.
Aufgabe 6.3 ( 10 P)
a) (6 P) Erweitern Sie die Klasse LinkedList des java.util-Pakets zu
einer sortierten Liste. Hinweis: verwenden Sie das Interface Comparable (aus
java.lang). Java Dokumentation benutzen! Test nicht vergessen!
b) (4 P) machen Sie das Gleiche mit der Klasse für einfach verkettete Listen,
die für Aufgabe 1.4 vorgegeben wurde und vergleichen Sie die Lösungen.
Aufgabe 6.4 ( 6 P)
a)(1) Gegeben die Klassen
class Fahrzeug {...
public String getTyp();
public int getGeschwindigkeit();
public date getBaujahr();
} und
class
Transportmittel{...
public int Sitzplätze();
public int maxGewicht();
}
Gesucht ist eine Klasse class
TransportFahrzeug, die beide Klassen im Sinne
von Mehrfachvererbung vereinigt. Gäbe es in Java mehrfach erbende Klassen
würde man schreiben: class
TransportFahrzeug extends Fahrzeug, Transport {..}. Geben
Sie eine Möglichkeiten zur Definition von TransportFahrzeug
in Java an, bei denen Code von Fahrzeug
bzw. Transportmittel wiederverwendet wird.
b) (1) Gegeben die Variablenvereinbarungen IF1 x; IF2 y; IF1 und IF2 sind Java Interfaces. Geben Sie die genauen Bedingungen dafür an, dass die Typzuweisung x = y; aus Sicht des Java-Übersetzers korrekt ist.
c) (4) Zeichnen Sie alle freien Bäume mit den Knoten x, y und z; alle Wurzelbäume mit Knoten x,y,z und Wurzel x, alle geordneten Bäume mit Knoten x,y,z mit der Wurzel x, und alle binären Bäume mit Knoten x,y,z mit Wurzel x.
d) (Bonusaufgabe, 4 Punkte) Schreiben Sie eine Haskell - Funktion, die alle Knoten eines binären Baums traversiert (beliebige Reihenfolge) und eine Operation auf dem Wert jedes Knotens ausführt. Rufen Sie die Funktion z.B. mit einer Funktion "verdoppeln" und einem Binärbaum auf, dessen Knotenwerte ganze Zahlen sind.
32 Punkte + 4 Bonuspunkte