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
- Bitte um Forenthreads erweitern!
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.
Eine elementare Erkenntnis hierbei ist:
Hat ein Knoten zwei Nachbar, die verschiedene Farben haben, so kann der aktuelle Knoten nicht gefärbt werden, ohne die gleiche Farbe wie mindestens einer sein
while (!q.isEmpty()) { Node current = q.removeFirst(); for (int i = 0; i < current.neighbors.size(); i++) { if (current.neighbors.get(i).color == WHITE) { q.addLast(current.neighbors.get(i)); } } // for zuende if (current.color == BLACK) { for (int i = 0; i < current.neighbors.size(); i++) { if (current.neighbors.get(i).color == BLACK) return false; if (current.neighbors.get(i).color == WHITE) q.get(i).color = GRAY; } // for zuende } else { for (int i = 0; i < current.neighbors.size(); i++) { if (current.neighbors.get(i).color == GRAY) return false; if (current.neighbors.get(i).color == WHITE) q.get(i).color = BLACK; } // for zuende } } // while zuende return true; // gruesse Gaku :) // EDIT: Die Lösung stimmt nicht ganz, wenn jemand was besseres hat, // kann er dashier gerne ersetzen!
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
Lösung von weißnix:
a)
private void versickern(Knoten k) { Knoten groesser = null; groesser = k.links; if(k.rechts != null){ if(k.links != null && k.links.wert < k.rechts.wert || k.links == null) { groesser = k.rechts; } } if(groesser == null) { return; } if(groesser.wert <k.wert) return; vertausche (groesser, k); 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){ Table next = this; while(next.ort != lort){ next = next.naechster; } if (next.ort == lort){ return next.wert; } return 0; }''
b)
ops
meth: → Double
axs
meth(leer) = 0
meth(in(tab, ort, wert)) = meth(tab)+wert
c)
ops
filter: Tabelle x String → Tabelle
axs
filter (leer, ort) = leer
filter (in (tab, ort, wert), ort2) = entweder a oder b:
a) filter (tab, ort2) für ort != ort2
b) in (filter (tab, ort2), ort2, wert) sonst
Aufgabe 6 - UML
a) Komposition
b)
class Buch { protected static int medienZaehler; public String name; private String autor; public void Buch(String name, String autor) { } public static int gibMedienZaehler() { } public String gibAutor() { } }
c) TODO
d) TODO
Aufgabe 7 - Formale Verifikation
a)
rechts oben: ret = Ω_i && i <= n //gruesse Gaku :)
b)
P => I wp (" ret = 1; i = 1; " , ret = Ω_i && i < = n ) = wp (" ret = 1; " , ret = Ω_1 && 1 < = n ) = (ret = 1 && 1 < = n) => True //gruesse Gaku :)
c)
I & nicht b => Q [ ret = Ω_i && i <= n ] & ( i >= n) = [ ret = Ω_i && i = n ] = [ ret = Ω_n ] = Q Bei der Lösung bin ich mir aber nicht 100% sicher. Inhaltlich stimmt sie schon, aber ob das auch so gefragt war? //gruesse Gaku :)
d)
'V = - i + n' Da i steigt => monotonfallend! Da i immer < = n ist = > ungleich null! //gruesse Gaku :)