Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch
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:loesungss14 [22.03.2018 09:53] – Evren | pruefungen:bachelor:aud:loesungss14 [03.04.2019 18:00] – Nico Hambauer | ||
---|---|---|---|
Zeile 5: | Zeile 5: | ||
**b)** 1te, 2te | **b)** 1te, 2te | ||
- | **c)**2te (O(n log n)) | + | **c)** 2te (O(n log n)) |
**d)** 2te, 3te Antwort | **d)** 2te, 3te Antwort | ||
Zeile 42: | Zeile 42: | ||
**b)** \\ | **b)** \\ | ||
- | **(i)** A schon vorhanden, Balancfaktoren stimmen auch => gar nichts machen | + | (i) ^ |
+ | {{: | ||
+ | |||
+ | (ii) ^ | ||
+ | {{: | ||
+ | |||
+ | (iii) ^ | ||
+ | {{: | ||
\\ | \\ | ||
- | **(ii)** | + | **c)** \\ |
+ | **(i)** pre-order: E -> N -> J -> H -> O -> O -> D \\ | ||
+ | **(ii)** | ||
+ | **(iii)** post-order: J -> O -> H -> N -> D -> O -> E \\ | ||
+ | \\ | ||
+ | **d)** \\ | ||
+ | **(i)** E anstelle von F ?? | ||
< | < | ||
- | X(0) | + | E |
- | | + | / \ |
- | A(-1) Y(-1) | + | B G |
- | | + | / |
- | | + | A |
+ | \ | ||
+ | D | ||
</ | </ | ||
\\ | \\ | ||
- | **(iii)** | + | **(ii)** C anstelle von B ?? |
- | C einfügen und anschließend Knoten (V) nach rechts rotieren | + | |
< | < | ||
- | X(1) X(0) | + | A |
- | / \ / | + | \ |
- | | + | C |
- | / | + | \ |
- | V(1) | + | D |
- | / | + | \ |
- | C(0) | + | E |
</ | </ | ||
- | \\ | ||
- | **c)** \\ | ||
- | **(i)** pre-order: E -> N -> J -> H -> O -> O -> D \\ | ||
- | **(ii)** in-order: J -> N -> H -> O -> E -> D -> O \\ | ||
- | **(iii)** post-order: J -> O -> H -> N -> D -> O -> E \\ | ||
+ | ====3) Graphalgorithmen==== | ||
- | ** | + | **a)** \\ |
- | Falsche Aufgabe. Bei SS14 / 2 muss man ausschließlich Bäume zeichnen. | + | {A, B, C, D, E} \\ |
- | ** | + | {A, B, D, E} \\ |
+ | {A, B, C, E} \\ | ||
+ | {A, B, C, D} \\ | ||
+ | {F, G, H} \\ | ||
+ | {A, B, C} \\ | ||
+ | {A, B, E} \\ | ||
+ | |||
+ | **b)** | ||
+ | ^ A ^ B ^ C ^ D ^ E ^ | ||
+ | | ∞ | [0] | ∞ | ∞ | ∞ | | ||
+ | | ∞ | | 5< | ||
+ | | 16< | ||
+ | | 14< | ||
+ | | [13< | ||
+ | |||
+ | Endergebnis: | ||
+ | |||
+ | **c)** \\ | ||
+ | F --(7)--> B --(5)--> C --(6)--> D --(2)--> A \\ | ||
+ | Weglänge: 7 + 5 + 6 + 2 = 20 | ||
+ | |||
+ | **d)** \\ | ||
+ | {{: | ||
+ | ==== 4) Backtracking ==== | ||
Loesung uebernommen aus dem Forum, eventuell gegenchecken | Loesung uebernommen aus dem Forum, eventuell gegenchecken | ||
https:// | https:// | ||
+ | <code java> | ||
static boolean exists(boolean[][] brd, int r, int c) { | static boolean exists(boolean[][] brd, int r, int c) { | ||
if(brd[r] == null || brd[r].length < 1) { | if(brd[r] == null || brd[r].length < 1) { | ||
Zeile 93: | Zeile 126: | ||
for(int i = 0; i < brd.length; i++) { | for(int i = 0; i < brd.length; i++) { | ||
for(int j = 0; j < mrl; j++) { | for(int j = 0; j < mrl; j++) { | ||
- | if(exists(brd, | + | if(exists(brd, |
sol[i][j] = 0; | sol[i][j] = 0; | ||
} else { | } else { | ||
Zeile 103: | Zeile 136: | ||
} | } | ||
+ | //Achtung die folgende Implementierung enthaelt fehler! Lieber die Implementierung aus | ||
+ | //<< | ||
static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { | static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { | ||
int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, | int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, | ||
Zeile 124: | Zeile 159: | ||
return false; | return false; | ||
} | } | ||
- | ==== 4) Backtracking ==== | + | </ |
[[pruefungen: | [[pruefungen: | ||
Zeile 175: | Zeile 211: | ||
if (exists(brd, | if (exists(brd, | ||
sol[r][c] = n; | sol[r][c] = n; | ||
- | + | if (solve(brd, sol, tf, jump[0], jump[1], n + 1)) { | |
- | boolean res = solve(brd, sol, tf, jump[0], jump[1], n + 1); | + | |
- | if (res) { | + | |
return true; | return true; | ||
} | } | ||
- | |||
sol[r][c] = 0; | sol[r][c] = 0; | ||
} | } | ||
- | |||
} | } | ||
- | |||
return false; | return false; | ||
} | } | ||
Zeile 200: | Zeile 231: | ||
\\ | \\ | ||
c) | c) | ||
+ | <code java> | ||
void reheap(W[] w, Comparator< | void reheap(W[] w, Comparator< | ||
int leftId = 2 * i + 1; | int leftId = 2 * i + 1; | ||
Zeile 217: | Zeile 249: | ||
} | } | ||
} | } | ||
+ | </ | ||
\\ | \\ | ||
d) | d) | ||
Zeile 237: | Zeile 270: | ||
| | ||
==== 6) Bäume und Rekursion==== | ==== 6) Bäume und Rekursion==== | ||
- | LinkedList< | + | <code java> |
+ | LinkedList< | ||
assert s != null : new IllegalArgumentException(); | assert s != null : new IllegalArgumentException(); | ||
HashMap< | HashMap< | ||
Zeile 244: | Zeile 278: | ||
map.put(c, | map.put(c, | ||
} else { | } else { | ||
- | map.get(c).f += 1; | + | int value = map.get(c).f += 1; |
+ | map.put(c, value); | ||
} | } | ||
} | } | ||
Zeile 288: | Zeile 323: | ||
} | } | ||
} | } | ||
+ | </ |