Aufgabenblatt GPK2

185.A02 Grundlagen der Programmkonstruktion
2015S
1
Aufgabenblatt GPK2
zu Grundlagen der Programmkonstruktion
für die Übung am 21. Mai 2015
Dieses Aufgabenblatt gilt nur für Teilnehmer(innen) an „Grundlagen der Programmkonstruktion“, nicht für Teilnehmer(innen) an „Programmkonstruktion“ oder „Programmierpraxis“. Bitte lösen Sie alle Aufgaben auf diesem Aufgabenblatt und bringen Sie die Lösungen zur Übung am 21. Mai 2015 in den HS14 mit. Ablauf und Beurteilung erfolgen
wie bei der ersten Übungseinheit.
1
Reihenfolgen
Eine im Detail unbekannte, zu Beginn leere Datenstruktur x ist vorgegeben. Mittels add
fügt man einen Wert (vom Typ int) in die Datenstruktur ein. Ein Aufruf von remove
entfernt einen Wert aus der Datenstruktur und gibt ihn zurück. Folgender Java-Code wird
ausgeführt:
x.add(1);
x.add(2);
System.out.print(x.remove() + ", ");
x.add(3);
x.add(4);
System.out.print(x.remove() + ", ");
System.out.print(x.remove());
Je nach Datenstruktur (Fälle a bis c) wird dabei folgende Zeile ausgegeben:
a) 1, 2, 3
b) 2, 4, 3
c) 1, 3, 2
Aufgaben:
• Beschreiben Sie für a) bis c), welche Art von Datenstruktur x sein könnte. Achtung:
Nicht jede dieser Datenstrukturen muss einen allgemein bekannten Namen haben.
• Implementieren Sie die Datenstrukturen entsprechend a) bis c) jeweils mit den Methoden add und remove, wobei die Daten in Arrays abgelegt werden.
185.A02 Grundlagen der Programmkonstruktion
2
2015S
2
Binärbaum und Liste
Lösen Sie folgende Programmieraufgaben ohne Zuhilfenahme vordefinierter Methoden aus
Java-Bibliotheken:
• Erweitern Sie die Klasse IntTree aus der Vorlesung vom 4. 5. 2015 um zwei Methoden, die jeweils eine Liste (vom Typ IntQueueElem aus derselben Vorlesung)
zurückgeben. Das Ergebnis einer Methode enthält die Elemente des Baums in aufsteigender Reihenfolge, das der anderen Methode in absteigender Reihenfolge.
• Erweitern Sie IntQueueElem um eine Methode, die ein Array zurückgibt, das die
Elemente der Liste in derselben Reihenfolge wie die Liste enthält. Die Größe des
Arrays soll der Länge der Liste entsprechen.
• Erweitern Sie IntTree um einen Konstruktor mit einem int-Array als Parameter,
wobei die Werte im Array aufsteigend sortiert sind. Der erzeugte Baum soll alle Elemente des Arrays enthalten, und alle linken und rechten Teilbäume sollen annähernd
gleich groß sein.
• Testen Sie den Code, indem Sie
– einen Baum aus Zufallszahlen aufbauen (ohne den neuen Konstruktor),
– den Baum in eine aufsteigend sortierte Liste umwandeln,
– die Liste in ein Array umwandeln,
– aus dem Array einen neuen Baum aufbauen,
– beide Bäume in absteigend sortierte Listen umwandeln
– und schließlich diese beiden Listen miteinander vergleichen.
3
Bubblesort
Wandeln Sie die Methode bubbleSort aus der Vorlesung vom 11. 5. 2015 so ab, dass die
Variable done nicht mehr benötigt wird. Stattdessen wird der Rumpf der äußeren Schleife
so oft wiederholt ausgeführt wie das Array Einträge hat.
Beantworten Sie dazu folgende Fragen:
• Warum terminiert die abgewandelte Methode?
• Wie ändert sich der Aufwand im besten, durchschnittlichen und schlechtesten Fall?
• Wie hoch ist der Aufwand der ursprünglichen (unveränderten) Methode bubbleSort
wenn das Array vor dem Sortieren a) schon sortiert ist, b) Zufallszahlen enthält bzw.
c) umgekehrt sortiert ist?
• Wie hoch ist der Aufwand der veränderten Methode bubbleSort wenn das Array
vor dem Sortieren a) schon sortiert ist, b) Zufallszahlen enthält bzw. c) umgekehrt
sortiert ist?
185.A02 Grundlagen der Programmkonstruktion
4
2015S
3
Klassen und Objekte
Geben Sie tiefgehende Antworten auf folgende Fragen in Bezug auf Java:
• Wodurch unterscheiden sich Konstruktoren syntaktisch und inhaltlich von Methoden? Kann man statt Konstruktoren stets Initialisierungsmethoden verwenden?
Kann man statt Initialisierungsmethoden stets Konstruktoren verwenden?
• Wozu benötigt und wie verwendet man die Pseudovariable this sowie Aufrufe der
Form this(...)? Angenommen, this und this(...) würde es nicht geben. Wie
könnte man entsprechende Anwendungsfälle stattdessen lösen?
• Aus welchen Gründen sind Objektvariablen meist private? Welche Vor- und Nachteile ergeben sich daraus?
• Warum werden Ihrer Meinung nach Objektvariablen gleich bei der Objekterzeugung
mit einem Default-Wert belegt, lokale Variablen aber nicht? Auf diese Frage gibt es
keine Standardantwort. Sie müssen Ihre eigene Meinung ergründen und mit kleinen
Beispielen belegen bzw. hinterfragen.
• Warum werden Ihrer Meinung nach aus Klassen erzeugte Objekte in Java immer
über Referenzen angesprochen, elementare Werte (z.B. vom Typ int) aber nicht?
Muss das auch in anderen Sprachen stets so sein? Auch hier brauchen Sie keine
Standardantwort geben, sondern sollen Ihre eigene Meinung ergründen, belegen und
hinterfragen.
5
Datenstrukturen
Beantworten Sie folgende Fragen im Detail, nicht nur oberflächlich:
• Wodurch unterscheiden sich in Java Objekte vom Typ Map von Arrays? In welchen
Fällen ist welche dieser Datenstrukturen vorteilhaft?
• Der Typ Deque stellt zahlreiche Methoden bereit um FIFO- und LIFO-Verhalten zu
erreichen. Geben Sie einen Überblick über diese Methoden. Welche der Methoden
passen gut zusammen, und durch welche Kombinationen von Methoden wird welches
Verhalten erreicht?
• Anhand welcher Kriterien kann man entscheiden, ob für eine gegebene Aufgabenstellung Map (bzw. ein Array) oder Deque (bzw. Queue) besser geeignet ist?
• Angenommen, eine gewünschte Datenstruktur kann als Liste oder binärer Baum
implementiert werden. Anhand welcher Kriterien treffen Sie die Auswahl?
• Die binäre Suche in einem Array ist sehr effizient, die Erzeugung eines dafür notwendigen sortierten Arrays oft aber nicht. Unter welchen Bedingungen ist der gesamte
Ansatz (sortiertes Array erzeugen und darin suchen) vorteilhaft, in welchen nicht?