Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws11 [18.02.2013 15:47] – Dawodo | pruefungen:bachelor:aud:loesungws11 [16.03.2018 20:26] – Evren | ||
---|---|---|---|
Zeile 11: | Zeile 11: | ||
**b)** Antwort RO ist richtig: Stark zusammenhängend | **b)** Antwort RO ist richtig: Stark zusammenhängend | ||
- | **c)** 2. Antwort ist richtig: Preorder | + | **c)** 2. Antwort ist richtig: Preorder. Postorder müsste auch stimmen, denn die Reihenfolge, |
+ | \\ | ||
+ | Doch die Reihenfolge ist festgelegt: L-R-N (Links, Rechts, Mitte), siehe [[https:// | ||
**d)** Richtig | **d)** Richtig | ||
Zeile 17: | Zeile 19: | ||
**e)** Richtig, beispielsweise wenn sich die Werte für BucketSort eignen | **e)** Richtig, beispielsweise wenn sich die Werte für BucketSort eignen | ||
- | **f)** | + | **f)** |
- | * f ist linear rekursiv | + | * f ist linear rekursiv |
- | * g ist iterativ | + | nach Definition ist eine Funktion genau dann linear rekursiv, wenn sie in jedem Zweig einer Fallunterscheidung höchstens einmal aufgerufen wird. \\ |
+ | Bei Funktion f gilt:\\ | ||
+ | Fall 1: Ist (x < = 0) ∨ (x % 2 = 0), also für die Zahlen (..., -3, -2, -1, 0, 2, 4, 6, ...), kommt es zu gar keinem rekursiven Funktionsaufruf. \\ | ||
+ | Fall 2: Ist (x > 0) ∧ (x % 2 != 0) ∧ (x % 3 != 0), also für die Zahlen (1, 5, 7, 11, 13, ...) wird x um eins inkrementiert und der Schleiferumpf erneut ausgeführt. \\ | ||
+ | Da jetzt mit Sicherheit Fall 1 vorliegt, kommt es ebenfalls zu keinem rekursiven Funktionsaufruf. \\ | ||
+ | Fall 3: Ist (x > 0) ∧ (x % 2 != 0) ∧ (x % 3 == 0), also für die Zahlen (3, 9, 15, ...), kommt es zu einem rekursiven Aufruf f(x+1). Bei diesem Aufruf liegt mit Sicherheit Fall 1 \\ | ||
+ | vor, weshalb x = x + 1 gilt. Anschließend wird x um eins inkrementiert und wir sind garantiert im Fall 2, bei dem es zu keinem rekursiven Funktionsaufruf kommt. | ||
+ | Damit ist gezeigt, dass f linear rekursiv ist. | ||
+ | |||
+ | * g ist iterativ | ||
+ | nach Definition ist eine Funktion f nur genau dann rekursiv, wenn zur Berechnung von f diese Funktion f benutzt wird. | ||
**g)** Antwort RO und LU sind richtig | **g)** Antwort RO und LU sind richtig | ||
Zeile 29: | Zeile 41: | ||
==Adjazenzmatrix== | ==Adjazenzmatrix== | ||
^ ^ S ^ A ^ B ^ C ^ D ^ E ^ | ^ ^ S ^ A ^ B ^ C ^ D ^ E ^ | ||
- | ^ S | - | + | + | - | - | - | | + | ^ S | 0 | 1 | 1 | 0 | 0 | 0 | |
- | ^ A | - | - | - | + | + | - | | + | ^ A | 0 | 0 | 0 | 1 | 1 | 0 | |
- | ^ B | - | - | - | - | + | - | | + | ^ B | 0 | 0 | 0 | 0 | 1 | 0 | |
- | ^ C | - | - | - | - | - | + | | + | ^ C | 0 | 0 | 0 | 0 | 0 | 1 | |
- | ^ D | - | - | - | + | - | + | | + | ^ D | 0 | 0 | 0 | 1 | 0 | 1 | |
- | ^ E | - | - | - | - | - | - | | + | ^ E | 0 | 0 | 0 | 0 | 0 | 0 | |
==Graphische Darstellung== | ==Graphische Darstellung== | ||
Zeile 40: | Zeile 52: | ||
{{: | {{: | ||
- | ==Als Reihung== | + | ==Als Reihung |
- | ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^ | + | | Bezeichnungen: |
- | ^ 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 | | + | | Array-Indizes: |
+ | | Array-Werte: | ||
**b)** | **b)** | ||
Zeile 61: | Zeile 74: | ||
<code java> | <code java> | ||
- | // Solange es noch unbesuchte Knoten gibt | + | boolean color(Node v) { |
- | while(!q.isEmpty()) { | + | LinkedList< |
- | // Aktuellen Knoten aus der Queue entnehmen: | + | v.color = BLACK; |
- | // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden | + | q.addLast(v); |
- | Node current = q.removeFirst(); | + | |
- | + | // Solange es noch unbesuchte Knoten gibt | |
- | // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) | + | while(!q.isEmpty()) { |
- | Color neighborColor = WHITE; | + | // Aktuellen Knoten aus der Queue entnehmen: |
- | + | // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden | |
- | // Gehe alle Nachbarknoten einmal durch | + | Node current = q.removeFirst(); |
- | for(Node n : neighbors) { | + | |
- | // Ist der aktuelle Nachbarknoten WHITE, dann wurde er noch nicht besucht | + | // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) |
- | // -> Füge ihn der Queue hinzu | + | Color neighborColor = WHITE; |
- | if(n.color == WHITE) { | + | |
- | q.addLast(n); | + | // Gehe alle Nachbarknoten einmal durch |
+ | for(Node n : neighbors) { | ||
- | // Ist der aktuelle | + | // Ist der aktuelle Nachbar WHITE, dann wurde er noch nicht besucht |
- | // und ist entweder BLACK oder GRAY | + | // -> Füge ihn der Queue hinzu |
- | } else { | + | if(n.color == WHITE) { |
- | // Ist die Variable für die Farbe der Nachbarn noch nicht | + | q.addLast(n); |
- | // gesetzt | + | |
- | if(neighborColor == WHITE) | + | // Ist der aktuelle |
- | neighborColor = GRAY; | + | // und ist entweder BLACK oder GRAY |
- | + | } else { | |
- | // Hat der aktuelle | + | // Ist die Variable für die Farbe der Nachbarn noch nicht gesetzt |
- | // betrachteten Nachbarknoten, | + | // (d.h. WHITE), dann initialisiere sie anhand des aktuellen Nachbarn |
- | if(n.color != neighborColor) | + | if(neighborColor == WHITE) |
- | return false; | + | neighborColor = n.color; |
+ | |||
+ | // Hat der aktuelle | ||
+ | // betrachteten Nachbarknoten, | ||
+ | if(n.color != neighborColor) | ||
+ | return false; | ||
+ | } | ||
} | } | ||
- | + | ||
// Färbe den Knoten korrekt ein und markiere ihn so als besucht | // Färbe den Knoten korrekt ein und markiere ihn so als besucht | ||
// Die Farbe muss das Gegenteil der Farbe der Nachbarn sein! | // Die Farbe muss das Gegenteil der Farbe der Nachbarn sein! | ||
Zeile 97: | Zeile 116: | ||
current.color = (neighborColor == BLACK) ? GRAY : BLACK; | current.color = (neighborColor == BLACK) ? GRAY : BLACK; | ||
} | } | ||
- | } | + | |
+ | // Die Schlange ist leer, alle Knoten wurden abgearbeitet, | ||
+ | // wurde erfolgreich gefärbt. | ||
+ | return true; | ||
</ | </ | ||
Zeile 110: | Zeile 132: | ||
| | | **gd.g(" | | | | **gd.g(" | ||
| | | GC | | | | | | | GC | | | | ||
+ | |||
+ | Anmerkungen: | ||
+ | * Immer auf die Bindungstypen achten (statisch versus dynamisch) | ||
+ | * Es kommen grundsätzlich nur die Attribute / Methoden in Frage, die der statische Typ kennt | ||
+ | * Bei überladenen Methoden wird die spezifischte verwendet | ||
Programm zum selber Testen: {{: | Programm zum selber Testen: {{: | ||
Zeile 129: | Zeile 156: | ||
} else if(rechts != null) { | } else if(rechts != null) { | ||
groesser = rechts; | groesser = rechts; | ||
+ | } | ||
- | } else { | + | if(groesser == null) { |
return; | return; | ||
} | } | ||
Zeile 136: | Zeile 164: | ||
if(k.wert > groesser.wert) | if(k.wert > groesser.wert) | ||
return; | return; | ||
- | |||
- | if(groesser == null) { | ||
- | return; | ||
- | } | ||
vertausche(k, | vertausche(k, | ||
Zeile 146: | Zeile 170: | ||
</ | </ | ||
**b)** | **b)** | ||
+ | Nach dem Postorder-Prinzip: | ||
<code java> | <code java> | ||
private void erzeugeHalde(Knoten k) { | private void erzeugeHalde(Knoten k) { | ||
Zeile 173: | Zeile 198: | ||
// Wiederholt Wurzel entnehmen und an Liste anhängen | // Wiederholt Wurzel entnehmen und an Liste anhängen | ||
while(wurzel != null) { | while(wurzel != null) { | ||
- | Knoten tmp = entferneMax(); | + | schlepp.rechts |
- | schlepp.rechts | + | schlepp = schlepp.rechts; |
- | schlepp = tmp; | + | |
} | } | ||
Zeile 186: | Zeile 210: | ||
**a)** | **a)** | ||
+ | |||
+ | Alle Instanzen von **Tabelle** stellen eine verkettete Liste dar. Der älteste, also letzte Eintrag, dieser Liste ist " | ||
+ | |||
<code java> | <code java> | ||
double letzte(String lort) { | double letzte(String lort) { | ||
- | if(ort.equals(lort)) | + | // Sind wir im letzten Element " |
- | return wert; | + | |
if(naechster == null) | if(naechster == null) | ||
return 0; | return 0; | ||
+ | |||
+ | if(ort.equals(lort)) | ||
+ | return wert; | ||
return naechster.letzte(lort); | return naechster.letzte(lort); | ||
Zeile 199: | Zeile 227: | ||
**b)** | **b)** | ||
+ | |||
+ | Die Methode **meth** summiert offenbar den Wert jedes Elements in der List auf. | ||
+ | |||
< | < | ||
OPS: | OPS: | ||
Zeile 212: | Zeile 243: | ||
< | < | ||
OPS: | OPS: | ||
- | meth: Tabelle x String -> | + | filter: Tabelle x String -> |
AXS: | AXS: | ||
filter(leer, | filter(leer, | ||
- | filter(in(tab, | + | filter(in(tab, |
= filter(tab, ort2) sonst | = filter(tab, ort2) sonst | ||
</ | </ | ||
Zeile 294: | Zeile 325: | ||
**c)** | **c)** | ||
+ | |||
+ | < | ||
+ | Zu zeigen: {I ∧ ¬b} => wp(A, Q) | ||
+ | Anmerkung: A beschreibt das Programmstück nach der Schleife, aber vor der Nachbedingung. Hier ist A " | ||
+ | |||
+ | {I ∧ ¬b} = | ||
+ | (ret = Ω_i ∧ i ≤ n ∧ ¬(i < n)) = | ||
+ | (ret = Ω_i ∧ i ≤ n ∧ i ≥ n) = | ||
+ | (ret = Ω_i ∧ i = n) = | ||
+ | (ret = Ω_n) | ||
+ | |||
+ | {I ∧ ¬b} => wp(A, Q) = | ||
+ | {I ∧ ¬b} => Q = | ||
+ | (ret = Ω_n) => Q = | ||
+ | (ret = Ω_n) => (ret = Ω_n) = | ||
+ | (true) | ||
+ | </ | ||
+ | |||
+ | Folgender Abschnitt ist ein korrekter Beweis für die **nicht in der Klausur gestellte** Fragestellung: | ||
+ | " | ||
< | < | ||
Zu zeigen: {I ∧ b} => wp(A, I) | Zu zeigen: {I ∧ b} => wp(A, I) | ||
Zeile 360: | Zeile 411: | ||
< | < | ||
IV_(n-1) (n-1): | IV_(n-1) (n-1): | ||
- | indRec(n-1) = Ω_(n-1) | + | indRec(n-1) = Ω_(n-1) |
</ | </ | ||
Zeile 371: | Zeile 422: | ||
< | < | ||
= 4*n^2 - 4*n + 1 + Ω_(n-1) = | = 4*n^2 - 4*n + 1 + Ω_(n-1) = | ||
- | = 2(n - 1)^2 + Ω_(n-1) = | + | = (2n - 1)^2 + Ω_(n-1) = |
- | = Ω_(n-1) + 2(n - 1)^2 = | + | = Ω_(n-1) + (2n - 1)^2 = |
- | = Σ{from 1 to i-1} (2k - 1)^2 + 2(n - 1)^2 = | + | = Σ{from 1 to i-1} (2k - 1)^2 + (2n - 1)^2 = |
= Σ{from 1 to i} (2k - 1)^2 = | = Σ{from 1 to i} (2k - 1)^2 = | ||
= Ω_(n) | = Ω_(n) | ||
Zeile 379: | Zeile 430: | ||
q.e.d. | q.e.d. | ||
- |