Klausur Informatik I - Hochschule Karlsruhe

Hochschule Karlsruhe – Klausur Informatik I –
Prof. Dr. Christian Pape
Klausur Informatik I – SS06
Aufgabe
1
2
3
Max. Punkte
57
53
10
Punkte
Gesamtpunkte
(max. 120):
Note:
Bearbeitungszeit 120 Minuten
Keine Hilfsmittel
Tragen Sie als erstes Ihren vollständigen Namen und Ihre
Matrikelnummer ein.
Name:
Matrikelnummer:
Fragen Sie bei Unklarheiten in der Aufgabenstellung sofort nach. Tragen
Sie Ihre Lösungen nur in diese Aufgabenblätter ein und verwenden Sie
auch die Rückseite (mit Bezug zur Teilaufgabe). Sollte der Platz nicht
ausreichen, so erhalten Sie weitere Blätter. Geben Sie alle
Aufgabenblätter ab. Falls Sie die Heftung der Klausur entfernen, dann
schreiben Sie bitte auf jedes einzelne Blatt Ihren Namen und
Matrikelnummer. Verwenden Sie keine Bleistifte und keine rote Farbe.
Halten Sie Ihren Studentenausweis zur Kontrolle bereit.
- 1 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
1.
UML, Java
a)
Aktivitätsdiagramm (10 Punkte)
Prof. Dr. Christian Pape
Beschreiben Sie folgenden Ablauf aus dem Arbeitsleben von Gabelstaplerfahrer Klaus mit
einem UML 2.0 Aktivitätsdiagramm. Verwenden Sie dabei keine Abkürzungen oder
Kurzschreibweisen der UML.
Klaus beginnt seine Arbeit immer mit einer rigorosen Überprüfung seines
Gabelstaplers. Wenn alles in Ordnung ist, dann macht er eine Frühstückspause.
Falls etwas nicht in Ordnung ist, beseitigt er das Problem – die Pause fällt dann
aus. Bei seiner anschließenden Arbeit holt Klaus immer eine Palette oben von
einem Stapel von Paletten und stapelt die Palette wieder oben auf einen anderen
Stapel. Dieses wiederholt sich so lange, bis die Sirene den Feierabend einläutet
(die letzte von einem Stapel entnommene Palette stapelt er aber pflichtbewusst
noch auf einen Stapel bevor er geht).
- 2 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
b)
Prof. Dr. Christian Pape
UML Klassendiagramm (12 Punkte)
Da die Arbeit von Klaus insbesondere für alle anderen Mitarbeiter sehr gefährlich ist, soll das
Stapeln von Paletten automatisiert werden. Sie sind dafür verantwortlich, den rein zum
Stapeln der Paletten notwendigen Softwareteil zu entwerfen – alles andere dürfen Sie
ignorieren. Die Stapel in der Werkhalle sind am Anfang leer - sie werden erst bei Anlieferung
durch fortgesetztes stapeln und entstapeln gefüllt. Die Stapel haben jeweils eine maximale
Höhe, die je nach Werkshalle aber variiert. Die Höhe ist direkt proportional zur Anzahl
Paletten. Es wird immer nur genau eine Palette gestapelt.
Geben Sie ein vollständigen UML Klassendiagramm mit dem sich Paletten stapeln lassen.
Halten Sie sich bei Ihrem Entwurf an die Java-Namenskonventionen. Der Entwurf muss in
jedem Fall objekt-orientiert sein und das Geheimnisprinzip wahren.
- 3 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
c)
Prof. Dr. Christian Pape
Implementierung (25 Punkte)
Implementieren Sie von Ihrem Entwurf diejenige Klasse in Java, welche die Methoden zum
Stapeln von Paletten enthält. Jeder Aufruf einer Methode, die eine Palette auf den Stapel
schiebt oder wieder herunterholt, darf nur maximal O(1) Laufzeit haben. Da die automatisiert
fahrenden Gabelstapler keine Paletten über die maximale Deckenhöhe stapeln können und
auch nicht mehr Paletten abholen als wirklich da sind, brauchen Sie diese Fälle im Programm
nicht behandeln.
- 4 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
- 5 von 11 -
Prof. Dr. Christian Pape
Hochschule Karlsruhe – Klausur Informatik I –
d)
Prof. Dr. Christian Pape
JUnit (10 Punkte)
Schreiben Sie eine JUnit-Testmethode, die bei einer Deckenhöhe von 10 Paletten einen Stapel
von zwei Paletten schrittweise auf einen anderen Stapel „entstapelt“ und überprüft, dass
danach der Stapel die beiden Paletten in der richtigen Reihenfolge enthält.
- 6 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
2.
Prof. Dr. Christian Pape
Variante der Binärsuche
a)
Problemstellung (6 Punkte)
Gegeben: Eine Folge aufsteigend sortierter, unterschiedlicher int-Zahlen.
Gegeben als int-Feld a.
Gesucht: true, falls ein i mit a[i] = i existiert; false, falls kein solcher Index
existiert (i = 0, 1, …)
Markieren Sie in den nächsten Zahlenfolgen jeweils alle Vorkommen von Zahlen mit a[i] = i
mit einem Kreis.
b)
-7
-3
-1
0
1
4
6
8
-1
0
4
7
9
12
16
19
-1
1
2
5
7
8
10
12
Implementierung, Java (30 Punkte)
Implementieren Sie eine rekursive Methode, die obiges Problem löst.
Der Zeitaufwand der Methode darf O(log n) nicht überschreiten.
- 7 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
- 8 von 11 -
Prof. Dr. Christian Pape
Hochschule Karlsruhe – Klausur Informatik I –
c)
Prof. Dr. Christian Pape
Aufrufbaum (10 Punkte)
Geben Sie den vollständigen Aufrufbaum für Ihre Methode und die Folge -1, 0, 4, 7, 9, 12,
16, 19 an.
d)
Laufzeitkeller (5 Punkte)
Geben Sie den Zustand des Laufzeitkellers an, den Ihre Methode bei Rekursionstiefe 3 hat.
- 9 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
e)
Prof. Dr. Christian Pape
(2 Punkte)
Um welchen Rekursionstyp handelt es sich bei Ihrer Implementierung?
- 10 von 11 -
Hochschule Karlsruhe – Klausur Informatik I –
3.
Prof. Dr. Christian Pape
UTF-8 (10 Punkte)
Gegeben sei das Unicodezeichens FEB1 als Hexadezimalzahl. Geben Sie den UTF-8-Code
für dieses Zeichen an. Geben Sie jeden Einzelschritt Ihrer Berechnung an.
- 11 von 11 -