Seite 1 von 15 Klausur DAP 1 – 27.09.2019
Datenstrukturen, Algorithmen und Programmierung 1
Modulprüfung – Klausur (180 min)
Name: __________________________ Matr.-Nr.:
Unterschrift: __________________________
Note: _____
Prüfer: ___________
wichtige Hinweise:
• Im Anhang dieser Klausur finden Sie die eventuell benötigten Programmtexte zu den vorgegebenen,
bereits aus der Vorlesung bekannten Klassen und Interfaces.
• In dieser Klausur dürfen Sie immer nur vorgegebene Java-Programmtexte mit Bezug zu den durch
Rahmen gekennzeichneten Stellen ergänzen, idealerweise durch Schreiben innerhalb dieser
Rahmen, aber auch durch Angabe einer eindeutigen Beziehung durch Pfeile oder Markierungen.
• An den vorgegebenen Programmtexten dürfen Sie keine Änderungen vornehmen.
• An keiner Stelle dieser Klausur dürfen Sie konzeptionell außerhalb von Rahmen liegende
Programmtexte ergänzen.
• Gehen Sie bei allen Aufgaben davon aus, dass an einen Feld-Parameter immer ein Feld-Objekt
(und nicht null) als Argument übergeben wird.
Aufgabe mögliche
Punkte
erreichte
Punkte
1 14
2 8
3 20
4 12
5 18
6 16
7 12
Summe 100
Zum Bestehen der Klausur
müssen mindestens 40 Punkte
erreicht werden.
Benotungsskala
Mindest-
punktzahl
Note
94 1,0
88 1,3
82 1,7
76 2,0
70 2,3
64 2,7
58 3,0
52 3,3
46 3,7
40 4,0
Seite 2 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 1 (Datenstrukturen, Algorithmen)
a) [2 Punkte] (Binärer Suchbaum)
Stellen Sie den binären Suchbaum grafisch dar, der aus einem leeren Baum entsteht, wenn nacheinander die
folgenden Werte in der vorgegebenen Reihenfolge eingefügt werden:
29, 17, 35, 51, 64, 58, 1, 11, 14, 67, 22, 4
Geben Sie die Werte des oben von Ihnen dargestellten Baums in der Reihenfolge an, in der sie bei einem
Preorder-Durchlauf besucht werden:
__________________________________________________________________________________
b) [4 Punkte] (Quicksort)
Sortieren Sie die nachfolgenden Zahlen mit dem in der Vorlesung vorgestellten Quicksort-Algorithmus.
Wählen Sie als Pivotelement das letzte Element des zu sortierenden Bereichs. Geben Sie die Werte der
gewählten Pivotelemente in der Reihenfolge an, in der sie beim Sortieren bestimmt werden.
zu sortierenden Zahlenfolge: 7 42 24 82 36 66 20 30 33 45
Werte der Pivotelemente: ______________________________________________
___ / 4
___ / 2
Seite 3 von 15 Klausur DAP 1 – 27.09.2019
c) [4 Punkte] (Huffman-Codierung)
Geben Sie den Huffman-Baum an, der sich für die in der folgenden Tabelle aufgeführten Zeichen mit den
angegebenen Häufigkeiten ergibt. Benutzen Sie den in der Vorlesung vorgestellten Algorithmus.
d) [4 Punkte] (Mustererkennung)
Konstruieren Sie gemäß des in der Vorlesung vorgestellten Algorithmus einen Moore-Automaten, der in
einer Folge von Zeichen aus Σ mit {x,y,z} ⊆ Σ das Muster xyzxxyzx erkennt.
Geben Sie die Zustandsüberführungsfunktion des Moore-Automaten in der aus der Vorlesung bekannten
tabellarischen Notation an.
Zeichen a b c d e f g
Häufigkeit 26 70 28 60 63 98 91
s ∈ Σ \ {x,y,z}
0
x
y
z
___ / 4
___ / 4
Seite 4 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 2 (Polymorphie)
[8 Punkte] Gegeben sind die beiden folgenden Klassenhierarchien.
public class All { … }
public class Most extends All { … }
public class Normal extends Most { … }
public class Special extends Normal { … }
public class Top
{
public void m( All p ) { System.out.print(“A”); }
public void m( Special p ) { System.out.print(“B”); }
}
public class Upper extends Top
{
public void m( Most p ) { System.out.print(“M”); }
public void m( Normal p ) { System.out.print(“P”); }
}
public class Middle extends Upper
{
public void m( Normal p ) { System.out.print(“X”); }
}
public class Bottom extends Middle
{
public void m( All p ) { System.out.print(“E”); }
}
public class Test
{
public static void run()
{
All all = new Most();
Most most = new Most();
Normal normal = new Special();
Special special = new Special();
Top tu = new Upper();
Upper um = new Middle();
Middle mm = new Middle();
Middle mb = new Bottom();
tu.m( most );
tu.m( special );
um.m( normal );
um.m( special );
mm.m( normal );
mm.m( special );
mb.m( all );
mb.m( normal );
}
}
Geben Sie die Zeichenfolge an, die durch die Methode run ausgegeben wird:
Ausgabe: ___ ___ ___ ___ ___ ___ ___ ___
___ / 8
Seite 5 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 3 (Methoden)
a) [8 Punkte] Vervollständigen Sie die Methode int[] top2( int[] arr ).
Die Methode top2 gibt ein neues Feld zurück, das die beiden größten in arr vorkommenden Werte
enthält. Sie können dabei davon ausgehen, dass in arr kein Wert doppelt vorkommt und dass alle Werte
in arr größer als 0 sind. Hat arr weniger als zwei Elemente, wird ein Feld der Länge 0 zurückgegeben.
Das Feld arr soll unverändert bleiben.
public static int[] top2( int[] arr )
{
}
___ / 8
Seite 6 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 3 (Methoden) – Fortsetzung
b) [8 Punkte] Vervollständigen Sie die Methode boolean nTimes( int[] arr, int n ).
Die Methode nTimes gibt true zurück, falls es mindestens einen Wert im Feld arr gibt, von dem es
genau n Vorkommen gibt.
Existiert kein solcher Wert oder ist n kleiner als 1, wird false zurückgegeben.
Das Feld arr soll unverändert bleiben.
public static boolean nTimes( int[] arr, int n )
{
}
___ / 8
Seite 7 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 3 (Methoden) – Fortsetzung
c) [4 Punkte] Vervollständigen Sie die rekursive Methode boolean do(int[] arr1, int[] arr2, int p),
die von der Methode use aufgerufen wird.
Die Methode use gibt true zurück, falls das Feld arr1 an allen Indizes die gleichen Werte wie das Feld
arr2 hat. Ist das Feld arr2 kürzer als das Feld arr1 oder unterscheiden sich Werte am gleichen Index,
wird false zurückgegeben.
Die Implementierung von do darf keine Schleifen enthalten.
public static boolean use( int[] arr1, int[] arr2 )
{
return do( arr1, arr2, arr1.length-1 );
}
private static boolean do( int[] arr1, int[] arr2, int p )
{
}
___ / 4
Seite 8 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 4 (Entwurfsmuster Iterator)
a) [6 Punkte] Implementieren Sie den Iterator LimitedIterator
Der Iterator LimitedIterator liefert nacheinander bis zu 100 Inhalte des Attributs data. Besitzt data
weniger als 100 Inhalte, so liefert der Iterator alle Inhalte.
Falls kein Inhalt zurückgegeben kann, gibt die Methode next() den Wert null zurück.
public class Container
{
private Iterable
public Container( Iterable
data = d;
}
public Iterator
return new LimitedIterator
}
private class LimitedIterator
{
}
}
___ / 6
Seite 9 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 4 (Entwurfsmuster Iterator) – Fortsetzung
b) [6 Punkte] Implementieren Sie die Methode containsDouble.
Die Methode
von data mindestens einmal zwei Inhalte liefert, die gleich sind. Diese Inhalte müssen nicht unmittelbar
aufeinander folgen. Der Vergleich der Inhalte soll mit der Methode equals erfolgen. Gibt es keine zwei
gleichen Inhalte, wird false zurückgegeben.
Sie dürfen bei der Implementierung davon ausgehen, dass der Parameter data nicht auf null verweist
und auch nur Inhalte besitzt, die ungleich null sind.
public static
{
}
___ / 6
Seite 10 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 5 (Methoden zur Klasse DoublyLinkedList
Ergänzen Sie die aus der Vorlesung bekannte Klasse DoublyLinkedList
der Implementierung der geforderten Methoden dürfen nur die im Anhang aufgeführten Methoden genutzt
werden.
a) [8 Punkte] Vervollständigen Sie die Methode boolean containsAll( Iterable
Die Methode containsAll gibt true zurück, wenn die ausführende Liste alle Inhalte enthält, die der
Iterator von data liefert. Sonst wird false zurückgegeben. Die Gleichheit soll mit der Methode equals
festgestellt werden.
Sie dürfen bei der Implementierung davon ausgehen, dass der Parameter data nicht auf null verweist und
die ausführende Liste und data nur Inhalte besitzt, die ungleich null sind.
public boolean containsAll( Iterable
{
}
___ / 8
Seite 11 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 5 (Methoden zur Klasse DoublyLinkedList
b) [10 Punkte] Vervollständigen Sie die Methode void insert( DoublyLinkedList
Die Methode insert fügt alle Elemente der Liste list unmittelbar vor dem Element der ausführenden
Liste ein, in dem erstmals der Inhalt cont vorkommt. Zugleich werden alle Elemente aus der Liste list
gelöscht. Kommt cont nicht als Inhalt der ausführenden Liste vor, bleiben beide Listen unverändert.
Die Gleichheit soll mit der Methode equals festgestellt werden.
Sie dürfen bei der Implementierung davon ausgehen, dass die Parameter list und cont nicht auf null
verweisen und die ausführende Liste nur Inhalte besitzt, die ungleich null sind.
public void insert( DoublyLinkedList
{
}
___ / 10
Seite 12 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 6 (Methoden zur Klasse BinarySearchTree
Ergänzen Sie die aus der Vorlesung bekannte Klasse BinarySearchTree
die Sie im Anhang finden. Bei der Implementierung der geforderten Methoden dürfen nur die im Anhang
aufgeführten Methoden genutzt werden.
a) [8 Punkte] Vervollständigen Sie die Methode int minimal().
Die Methode minimal gibt die Anzahl der Kanten zurück, die mindestens zwischen der Wurzel des Baums
und jedem beliebigen Blatt liegen.
Ist der Baum leer oder besteht er nur aus der Wurzel, wird 0 zurückgegeben.
public int minimal()
{
}
___ / 8
Seite 13 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 6 (Methoden zur Klasse BinarySearchTree) – Fortsetzung
b) [8 Punkte] Vervollständigen Sie die Methode T bigOnLevel( int lev ).
Die Methode bigOnLevel gibt den größten Inhalt zurück, der auf der Ebene lev liegt.
Besitzt der Baum keine Ebene lev, wird null zurückgegeben.
Die Wurzel liegt auf Ebene 0.
public T bigOnLevel( int lev )
{
}
___ / 8
Seite 14 von 15 Klausur DAP 1 – 27.09.2019
Aufgabe 7 (Lambda-Ausdrücke)
[12 Punkte] Gegeben sind die Interfaces IntFunc, IntIntFunc und die Klasse Data.
public interface IntFunc {
int apply( int x);
}
public interface IntIntFunc {
int apply( int x, int y );
}
public class Data {
private int[] iValues;
public Data( int[] p ) { iValues = p; }
public int act( IntFunc f, IntIntFunc g ) {
int result = 0;
int i = f.apply( -1 );
while ( i >= 0 && i < iValues.length ) {
result = g.apply( iValues[i], result );
i = f.apply( i );
}
return result;
}
}
Für die folgenden Teilaufgaben gilt: Die Referenz d verweist auf ein Data-Objekt.
a) Ergänzen Sie Argumente derart, dass der Aufruf von act die Summe der Werte des Feldes iValues
zurückgibt, die an ungeraden Indizes stehen. Hat ivalues weniger als zwei Elemente, wird 0 zurück-
gegeben.
d.act(
);
b) Ergänzen Sie Argumente derart, dass der Aufruf von act die Anzahl der Elemente des Feldes iValues
zurückgibt, an denen positive Werte stehen.
d.act(
);
c) Ergänzen Sie Argumente derart, dass der Aufruf von act den Wert des letzten Elements des Feldes
iValues zurückgibt.
d.act(
);
d) Ergänzen Sie Argumente derart, dass der Aufruf von act die Summe der ersten elf Werte des Feldes
iValues zurückgibt. Hat ivalues weniger als elf Elemente, wird die Summe aller Werte zurückgegeben.
d.act(
);
___ / 12
Seite 15 von 15 Klausur DAP 1 – 27.09.2019
Anhang – Programmcode der Klasse BinarySearchTree
public class BinarySearchTree
private T content;
private BinarySearchTree
public BinarySearchTree() { … }
public T getContent() { … }
public boolean isEmpty() { … }
public boolean isLeaf() { … }
}
Anhang – Programmcode der Klasse DoublyLinkedList
public class DoublyLinkedList
private Element first, last;
private int size;
public DoublyLinkedList() { … }
public int size() { … }
public boolean isEmpty() { … }
// Element
private static class Element {
private T content;
private Element pred, succ;
public Element( T c ) { … }
public T getContent() { … }
public void setContent( T c ) { … }
public boolean hasSucc() { … }
public Element getSucc() { … }
public void connectAsSucc( Element e) { … }
public void disconnectSucc() { … }
public boolean hasPred() { … }
public Element getPred() { … }
public void connectAsPred( Element e ) { … }
public void disconnectPred() { … }
}
}
Anhang – Programmcodes der Interfaces
public interface Iterator
public abstract boolean hasNext();
public abstract T next();
}
public interface Iterable
public abstract Iterator
}
public interface Comparable
public abstract int compareTo( T t ); // Der Rückgabewert ist positiv, falls das
} // ausführende Objekt größer als t ist.