Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws11 [28.07.2013 10:38] – Dawodopruefungen:bachelor:aud:loesungws11 [18.03.2018 19:33] – 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, ob zuerst nach links oder rechts abgestiegen wird, ist nicht festgelegt. 
 + \\ 
 +Doch die Reihenfolge ist festgelegt: L-R-N (Links, Rechts, Mitte), siehe [[https://www2.cs.fau.de/teaching/WS2017/AuD/slides/secure/aud-12.pdf|WS 2017/2018 - Folie 12-52]] => nur Preorder ist richtig, so kommt man dann auch am Ende der Aufgabe auf die 10 Antworten = 10 Punkte.
  
 **d)** Richtig **d)** Richtig
Zeile 21: Zeile 23:
 nach Definition ist eine Funktion genau dann linear rekursiv, wenn sie in jedem Zweig einer Fallunterscheidung höchstens einmal aufgerufen wird. \\ 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:\\ 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 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. \\ 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. \\ Da jetzt mit Sicherheit Fall 1 vorliegt, kommt es ebenfalls zu keinem rekursiven Funktionsaufruf. \\
Zeile 39: 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 50: Zeile 52:
 {{:pruefungen:bachelor:aud:02-12-graph.png|:pruefungen:bachelor:aud:02-12-graph.png}} {{:pruefungen:bachelor:aud:02-12-graph.png|:pruefungen:bachelor:aud:02-12-graph.png}}
  
-==Als Reihung== +==Als Reihung (eingebettet in Array; auch Adjazenzfeld genannt)== 
-^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^  +| | | | | | | | S | S | A | A | B | C | D | D | 
-| 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 |+| | S | A | B | C | D | E | A | B | C | D | D | E | C | E | 
 +| Array-Indizes: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |  
 +| Array-Werte: ^ 6 ^ 8 ^ 10 ^ 11 ^ 12 ^ 14 ^ 1 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5 ^ 3 ^ 5 ^
  
 **b)** **b)**
Zeile 106: Zeile 110:
  return false;  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; 
  }  }
 +
 + // 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;
  }  }
  
Zeile 167: Zeile 171:
 </code> </code>
 **b)** **b)**
 +Nach dem Postorder-Prinzip:
 <code java> <code java>
 private void erzeugeHalde(Knoten k) { private void erzeugeHalde(Knoten k) {
Zeile 239: Zeile 244:
 <code> <code>
 OPS: OPS:
- meth: Tabelle x String -> Tabelle+ filter: Tabelle x String -> Tabelle
  
 AXS: AXS:
Zeile 418: Zeile 423:
 <code> <code>
 = 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 426: Zeile 431:
  
 q.e.d. q.e.d.
 +
 +oder
 +
 +{{:pruefungen:bachelor:aud:induction-1.png?400|}}