Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Forendiskussionen
Lösungsversuch
Aufgabe 1 - Wissensfragen
a) Falsch, der finally-Block wird immer ausgeführt (abgesehen von einigen extrem konstruierten Ausnahmen, siehe hier)
b) Antwort RO ist richtig: Stark zusammenhängend
c) 2. Antwort ist richtig: Preorder
d) Richtig
e) Richtig, beispielsweise wenn sich die Werte für BucketSort eignen
f) (unsicher)
- f ist linear rekursiv
- g ist iterativ
g) Antwort RO und LU sind richtig
h) Falsch, dies ist die grundlegende AVL-Eigenschaft
Aufgabe 2 - Graphen
a)
Adjazenzmatrix
S | A | B | C | D | E | |
---|---|---|---|---|---|---|
S | - | + | + | - | - | - |
A | - | - | - | + | + | - |
B | - | - | - | - | + | - |
C | - | - | - | - | - | + |
D | - | - | - | + | - | + |
E | - | - | - | - | - | - |
Graphische Darstellung
Als Reihung
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 |
b)
Tiefensuche: S → A → C → E → D → B
Breitensuche: S → A → B → C → D → E
c)
Vorüberlegungen:
Die Aufgabenstellung ist das Färben eines Graphen mit den Farben schwarz und grau. Die Farbe weiß bedeutet lediglich, dass dieser Knoten noch gar nicht gefärbt wurde.
Bei dem Verfahren soll Breitensuche verwendet werden.
Elementare Erkenntnis hierbei:
Hat ein Knoten zwei (oder mehr) Nachbarn, die verschiedene Farben haben, so kann der aktuelle Knoten nicht gefärbt werden, ohne dass er die gleiche Farbe wie mindestens ein Nachbarknoten erhält.
Das bedeutet: Hat ein Knoten mindestens einen Nachbarn, der grau ist und mindestens einen, der schwarz ist, so lässt sich der Graph nicht färben und das Verfahren soll mit dem Rückgabewert „false“ terminieren.
// Solange es noch unbesuchte Knoten gibt while(!q.isEmpty()) { // Aktuellen Knoten aus der Queue entnehmen: // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden Node current = q.removeFirst(); // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) Color neighborColor = WHITE; // Gehe alle Nachbarknoten einmal durch for(Node n : neighbors) { // Ist der aktuelle Nachbarknoten WHITE, dann wurde er noch nicht besucht // -> Füge ihn der Queue hinzu if(n.color == WHITE) { q.addLast(n); // Ist der aktuelle Knoten nicht WHITE, dann wurde er schon besucht // und ist entweder BLACK oder GRAY } else { // Ist die Variable für die Farbe der Nachbarn noch nicht // gesetzt (d.h. WHITE), dann initialisiere sie if(neighborColor == WHITE) neighborColor = GRAY; // Hat der aktuelle Knoten eine andere Farbe, als die bisher // betrachteten Nachbarknoten, dann ist der Graph nicht färbbar if(n.color != neighborColor) return false; } // Färbe den Knoten korrekt ein und markiere ihn so als besucht // Die Farbe muss das Gegenteil der Farbe der Nachbarn sein! // Gab es keine Färbung der Nachbar, so wird der Knoten BLACK current.color = (neighborColor == BLACK) ? GRAY : BLACK; } }
Aufgabe 3 - Schreibtischlauf
ad.a | bd.b | gd.a | be.a | ee.a |
AA | 12 | AA | 12 | AE |
ad.f(91) | bd.f(92) | gd.f(93) | be.f(95) | ee.f(96) |
23 | 92 | 23 | 95 | CE |
gd.g(83) | ||||
FC | ||||
gd.g(„YC“) | ||||
GC |
Programm zum selber Testen: Walkthrough.java
Aufgabe 4 - Sortieren
a)
private void versickern(Knoten k) { Knoten groesser = null; if(links != null && rechts != null) { groesser = (links.wert > rechts.wert) ? links : rechts; } else if(links != null) { groesser = links; } else if(rechts != null) { groesser = rechts; } else { return; } if(k.wert > groesser.wert) return; if(groesser == null) { return; } vertausche(k, groesser); versickern(groesser); }
b)
private void erzeugeHalde(Knoten k) { if(k.left != null) erzeugeHalde(k.left); if(k.right != null) erzeugeHalde(k.right); versickern(k); }
c)
public Knoten inListeSortieren() { // Kann leere Halde nicht sortieren if (wurzel == null) return null; // Max-Heap-Eigenschaft herstellen erzeugeHalde(wurzel); // Wurzel entnehmen und zum Kopf unserer Liste machen Knoten kopf = entferneMax(); Knoten schlepp = kopf; // Wiederholt Wurzel entnehmen und an Liste anhängen while(wurzel != null) { Knoten tmp = entferneMax(); schlepp.rechts = tmp; schlepp = tmp; } // Kopf unserer Liste zurückgeben return kopf; }
Aufgabe 5 - ADT
a)
double letzte(String lort) { if(ort.equals(lort)) return wert; if(naechster == null) return 0; return naechster.letzte(lort); }
b)
OPS: meth: Tabelle -> Double AXS: meth(leer) = 0 meth(in(tab, ort, wert)) = wert + meth(tab)
c)
OPS: meth: Tabelle x String -> Tabelle AXS: filter(leer, ort) = leer filter(in(tab, ort, wert), ort2) = in(filter(tab, ort2), ort1, wert) falls equals(ort1, ort2) = filter(tab, ort2) sonst
Aufgabe 6 - UML
a)
- 2. Antwort: Komposition
b)
class Buch { protected static int medienZaehler; public String name; private String autor; public Buch(String name, String autor) { } public static int gibMedienZaehler() { } public String gibAutor() { } }
Hinweis:
Konstruktoren haben keinen Rückgabetyp, auch nicht void.
c)
Dia-Sourcefile für etwaige Korrekturen: :pruefungen:bachelor:aud:02-12-uml1.dia.txt
d)
Dia-Sourcefile für etwaige Korrekturen: :pruefungen:bachelor:aud:02-12-uml2.dia.txt
Aufgabe 7 - Formale Verifikation
a)
LO: Falsch i = 1; ret = 1; n ≥ 1 i < n Für n = 1 nicht erfüllt RO: Richtig i = 1; ret = 1; n ≥ 1 ret = Ω_i ∧ i ≤ n Ω_1 = 1 ∧ 1 ≤ n Immer erfüllt! LU: Falsch i = 1; ret = 1; n ≥ 1 ret = Ω_n Offensichtlich nicht für jedes n erfüllt RU: Falsch i = 1; ret = 1; n ≥ 1 indIter(n) = O(n^2) Offensichtlich völliger Quatsch
b)
Zu zeigen: P => I wp("ret = 1; i = 1;", ret = Ω_i ∧ i ≤ n) = (1 = Ω_1 ∧ 1 ≤ n) = (1 = (1 * (2 - 1) * (2 + 1)) / 3 ∧ 1 ≤ n) = (1 = 3 / 3 ∧ 1 ≤ n) = (1 ≤ n) P => I = (n ≥ 1) => (1 ≤ n) = (true)
c)
Zu zeigen: {I ∧ b} => wp(A, I) wp(A, I) = wp("i = i + 1; ret = ret + 4 * i * i - 4 * i + 1;", ret = Ω_i ∧ i ≤ n) = wp("i = i + 1;", ret + 4 * i * i - 4 * i + 1 = Ω_i ∧ i ≤ n) = (ret + 4 * (i + 1) * (i + 1) - 4 * (i + 1) + 1 = Ω_(i + 1) ∧ (i + 1) ≤ n) = (ret + 4 * (i + 1)^2 - 4 * (i + 1) + 1 = Ω_(i + 1) ∧ i ≤ n - 1) Nebenrechnung: Ω_(i + 1) = Σ{from 1 to i + 1} (2k - 1)^2 = Σ{from 1 to i} (2k - 1)^2 + 2*((i + 1) - 1)^2 Nebenrechnung: (ret + 4 * (i + 1)^2 - 4 * (i + 1) + 1) = binomische Formel (über Substituierung von (i + 1) eventuell leichter zu sehen) (ret + (2*(i + 1) - 1)^2) Daraus ergibt sich: = (ret + (2*(i + 1) - 1)^2 = Σ{from 1 to i} (2k - 1)^2 + 2*((i + 1) - 1)^2 ∧ i ≤ n - 1) = (ret = Σ{from 1 to i} (2k - 1)^2 ∧ i ≤ n - 1) Und nach einem Blick auf die Definition von Ω_i ergibt sich: Σ{from 1 to i} (2k - 1)^2 = Ω_i Damit erhalten wir nun: = (ret = Ω_i ∧ i ≤ n - 1) {I ∧ b} => wp(A, I) = {ret = Ω_i ∧ i ≤ n ∧ i < n} => wp(A, I) = ¬{ret = Ω_i ∧ i ≤ n} ∨ wp(A, I) = (ret ≠ Ω_i) ∨ (i > n) ∨ wp(A, I) = (ret ≠ Ω_i) ∨ (i > n) ∨ (ret = Ω_i ∧ i ≤ n - 1) Sind (ret ≠ Ω_i) und (i > n) beide nicht gültig, dann gilt offensichtlich: (ret = Ω_i) und (i ≤ n) Gilt (i ≤ n), dann gilt natürlich auch (i ≤ n - 1) Damit können wir schlussfolgern: {I ∧ b} => wp(A, I) = (true)
d)
V = n - i i wird stetig inkrementiert -> (-i) ist damit monoton fallend i = 1, i ≤ n und n ≥ 1 -> n - i ≥ 0
e)
Induktionsanfang:
IA_1 (n = 1): Ω_1 = (1 * (2 - 1) * (2 + 1)) / 3 = 3 / 3 = 1 indRec(1) = 1
Induktionsschritt:
Induktionsvorraussetzung:
IV_(n-1) (n-1): indRec(n-1) = Ω_(n-1)
Aus dem Programmfragment ist zu entnehmen:
indRec(n) = 4*n*n - 4*n + 1 + indRec(n-1) =
über die obigen Induktionsvoraussetzungen kommt man auf:
= 4*n^2 - 4*n + 1 + Ω_(n-1) = = 2(n - 1)^2 + Ω_(n-1) = = Ω_(n-1) + 2(n - 1)^2 = = Σ{from 1 to i-1} (2k - 1)^2 + 2(n - 1)^2 = = Σ{from 1 to i} (2k - 1)^2 = = Ω_(n)
q.e.d.