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

--- pruefungen:bachelor:aud:loesungws11 [28.03.2015 17:09] – frececroka
+++ pruefungen:bachelor:aud:loesungws11 [24.01.2019 21:56] (aktuell) – LasagneAlForno
@@ Zeile 11: / Zeile 11: @@
 **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
@@ 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. \\
 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. \\
 Da jetzt mit Sicherheit Fall 1 vorliegt, kommt es ebenfalls zu keinem rekursiven Funktionsaufruf. \\
@@ Zeile 39: / Zeile 41: @@
 ==Adjazenzmatrix==
 ^  ^ 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==
@@ Zeile 50: / Zeile 52: @@
 {{: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)**
@@ Zeile 142: / Zeile 146: @@
 <code java>
-private void versickern(Knoten k) {
+private static void versickern(Knoten k) {
-	Knoten groesser = null;
+		Knoten groesser = null;
-	if(links != null && rechts != null) {
+		if (k.links != null && k.rechts != null) {
-		groesser = (links.wert > rechts.wert) ? links : rechts;
+			if (k.links.wert > k.rechts.wert) {
+				groesser = k.links;
+			} else {
+				groesser = k.rechts;
+			}
-	} else if(links != null) {
+		} else if (k.links != null) { // hier ist es wichtig, ein "else if" statt einem if zu verwenden!
-		groesser = links;
+			groesser = k.links;
-	} else if(rechts != null) {
+		} else if (k.rechts != null) {
-		groesser = rechts;
+			groesser = k.rechts;
-	}
+		}
-	if(groesser == null) {
+		if (groesser == null) {
-		return;
+			return;
-	}
+		}
-	if(k.wert > groesser.wert)
+		if (k.wert > groesser.wert) {
-		return;
+			return; // fertig :)
+		}
-	vertausche(k, groesser);
+		vertausche(k, groesser);
-	versickern(groesser);
+		versickern(groesser); // normalerweise würde man versickern(k) rekursiv aufrufen, aber die vertausche-Methode tauscht laut Aufgabenstellung nicht die Knoten, sondern nur deren Werte!
-}
+	}
 </code>
 **b)**
+Nach dem Postorder-Prinzip:
 <code java>
-private void erzeugeHalde(Knoten k) {
+private static void erzeugeHalde(Knoten k) {
-	if(k.left != null)
+		if (k.links != null)
-		erzeugeHalde(k.left);
+			erzeugeHalde(k.links);
-	if(k.right != null)
+		if (k.rechts != null)
-		erzeugeHalde(k.right);
+			erzeugeHalde(k.rechts);
-	versickern(k);
+		versickern(k);
 }
 </code>
 **c)**
 <code java>
-public Knoten inListeSortieren() {
+	public static Knoten inListeSortieren() {
-	// Kann leere Halde nicht sortieren
+		// Kann leere Halde nicht sortieren
-	if (wurzel == null)
+		if (wurzel == null) {
-		return null;
+			return null;
+		}
+		// Max-Heap-Eigenschaft herstellen
+		erzeugeHalde(wurzel);
-	// Max-Heap-Eigenschaft herstellen
+		// Wurzel entnehmen und zum Kopf unserer Liste machen
-	erzeugeHalde(wurzel);
+		Knoten kopf = entferneMax();
+		Knoten schlepp = kopf;
-	// Wurzel entnehmen und zum Kopf unserer Liste machen
+		// Wiederholt Wurzel entnehmen und an Liste anhängen
-	Knoten kopf = entferneMax();
+		while (wurzel != null) {
-	Knoten schlepp = kopf;
+			schlepp.rechts = entferneMax();
+			schlepp = schlepp.rechts;
-	// Wiederholt Wurzel entnehmen und an Liste anhängen
+		}
-	while(wurzel != null) {
-		schlepp.rechts = entferneMax();
+		// Kopf unserer Liste zurückgeben
-		schlepp = schlepp.rechts;
+		return kopf;
 	}
-	// Kopf unserer Liste zurückgeben
-	return kopf;
-}
 </code>
@@ Zeile 239: / Zeile 251: @@
 <code>
 OPS:
-	meth: Tabelle x String		-> Tabelle
+	filter: Tabelle x String		-> Tabelle
 AXS:
@@ Zeile 426: / Zeile 438: @@
 q.e.d.
+oder
+{{:pruefungen:bachelor:aud:induction-1.png?400|}}