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 Überarbeitung | ||
pruefungen:bachelor:aud:loesungss14 [22.03.2018 11:03] – Evren | pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:54] (aktuell) – Verbesserung Aufgabe 5c,d dom | ||
---|---|---|---|
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)** Nichts rotieren, da Balancfaktoren stimmen: | + | |
- | < | + | (ii) ^ |
- | | + | {{: |
- | / \ | + | |
- | A(-1) Y(-1) | + | (iii) ^ |
- | | + | {{: |
- | B(0) Z(0) | + | |
- | </ | + | |
- | \\ | + | |
- | **(iii)** | + | |
- | C einfügen und anschließend Knoten (V) nach rechts rotieren | + | |
- | < | + | |
- | | + | |
- | / | + | |
- | W(2!) Y(-1) V(0) Y(-1) | + | |
- | / | + | |
- | | + | |
- | / | + | |
- | | + | |
- | </ | + | |
\\ | \\ | ||
**c)** \\ | **c)** \\ | ||
**(i)** pre-order: E -> N -> J -> H -> O -> O -> D \\ | **(i)** pre-order: E -> N -> J -> H -> O -> O -> D \\ | ||
- | **(ii)** in-order: J -> N -> H -> O -> E -> D -> O \\ | + | **(ii)** in-order: J -> N -> O -> H -> E -> D -> O \\ |
**(iii)** post-order: J -> O -> H -> N -> D -> O -> E \\ | **(iii)** post-order: J -> O -> H -> N -> D -> O -> E \\ | ||
\\ | \\ | ||
Zeile 95: | Zeile 81: | ||
====3) Graphalgorithmen==== | ====3) Graphalgorithmen==== | ||
- | **a)** | + | **a)** |
- | {A, B, C, D, E} | + | {A, B, C, D, E} \\ |
- | {F, G, H} | + | {A, B, D, E} \\ |
- | {A, B, C} | + | {A, B, C, E} \\ |
- | {A, B, E} | + | {A, B, C, D} \\ |
+ | {F, G, H} \\ | ||
+ | {A, B, C} \\ | ||
+ | {A, B, E} \\ | ||
**b)** | **b)** | ||
Zeile 111: | Zeile 100: | ||
Endergebnis: | Endergebnis: | ||
- | **c)** | + | **c)** |
F --(7)--> B --(5)--> C --(6)--> D --(2)--> A \\ | F --(7)--> B --(5)--> C --(6)--> D --(2)--> A \\ | ||
Weglänge: 7 + 5 + 6 + 2 = 20 | Weglänge: 7 + 5 + 6 + 2 = 20 | ||
- | ** | + | **d)** \\ |
- | Falsche Aufgabe. Bei SS14 / 2 muss man ausschließlich Bäume zeichnen. | + | {{: |
- | ** | + | |
- | Loesung uebernommen aus dem Forum, eventuell gegenchecken | ||
- | https:// | ||
+ | ==== 4) Backtracking ==== | ||
+ | **a)** | ||
+ | <code java> | ||
+ | static boolean exists(boolean[][] brd, int r, int c) { | ||
+ | if (brd[r] == null || brd[r].length < 1) { // Zeilen null oder leer | ||
+ | return false; | ||
+ | } | ||
+ | if (r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { // Indizes ausserhalb der Grenzen | ||
+ | return false; | ||
+ | } | ||
+ | return true; | ||
+ | } | ||
+ | </ | ||
- | static boolean exists(boolean[][] brd, int r, int c) { | + | **b)** |
- | if(brd[r] == null || brd[r].length < 1) { | + | |
- | return false; | + | |
- | } | + | |
- | if(r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { | + | |
- | return false; | + | |
- | } | + | |
- | return true; | + | |
- | } | + | |
- | static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { | + | < |
- | int[][] | + | static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { |
- | for(int i = 0; i < brd.length; i++) { | + | int[][] = null; |
- | for(int j = 0; j < mrl; j++) { | + | |
- | if(exists(brd, | + | |
- | sol[i][j] = 0; | + | |
- | } else { | + | |
- | sol[i][j] = -1; | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | return sol; | + | |
- | } | + | |
- | static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { | + | for (int r = 0; r < brd.length; r++) { |
- | int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, | + | for (int c = 0; c < mrl; c++) { |
- | { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; | + | if (exists(brd, |
- | if(sol[r][c] >= 1) { | + | sol[r][c] = 0; |
- | return false; | + | } else { |
- | } | + | sol[c][c] = -1; // Felder mit -1 vorbelegen |
- | if(n == tf) { | + | } |
- | sol[r][c] = n; | + | } |
- | return true; | + | } |
- | } | + | return sol; |
- | sol[r][c] = n; | + | } |
- | for(int | + | </ |
- | if(exists(brd, | + | **c)** |
- | if(solve(brd, | + | < |
- | return true; | + | static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { |
- | } | + | // possible targets from (r,c) |
- | } | + | |
- | } | + | |
- | sol[r][c] = 0; | + | |
- | return false; | + | // |
- | } | + | if (n == tf) { |
- | ==== 4) Backtracking ==== | + | sol[r][c] = n; |
- | [[pruefungen:bachelor: | + | return true; |
+ | } | ||
+ | for (int j = 0; j < jumps.length; | ||
+ | |||
+ | // Wert setzen | ||
+ | sol[r][c] = n | ||
+ | |||
+ | // Brett brd und Loesungsfeld sol pruefen | ||
+ | | ||
+ | |||
+ | // Rekursion | ||
+ | | ||
+ | return true; | ||
+ | } | ||
+ | // Backtrack | ||
+ | sol[r][c] = 0; | ||
+ | | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | Alternative: | ||
** a) *** | ** a) *** | ||
Zeile 219: | Zeile 226: | ||
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; | ||
} | } | ||
</ | </ | ||
+ | [[pruefungen: | ||
==== 5) Haldensortierung ==== | ==== 5) Haldensortierung ==== | ||
\\ | \\ | ||
- | a) Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden. | + | a) |
+ | |||
+ | Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden. | ||
=> Kreuz bei Stelle 2, 5 und 6 | => Kreuz bei Stelle 2, 5 und 6 | ||
=> Resultat: { 6, 7, 5, 3, 1, 0, 2 } | => Resultat: { 6, 7, 5, 3, 1, 0, 2 } | ||
\\ | \\ | ||
- | b) Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\ | + | b) |
+ | |||
+ | Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\ | ||
\\ | \\ | ||
c) | c) | ||
- | void reheap(W[] w, Comparator< | + | <code java> |
- | int leftId = 2 * i + 1; | + | void reheap(W[] w, Comparator< |
- | int rightId = leftId + 1; | + | int leftId = 2 * i + 1; |
- | int kidId; | + | int rightId = leftId + 1; |
- | + | int kidId; | |
- | if(leftId <= k) { | + | |
- | if(rightId > k || c.compare(w[leftId], | + | // nur 1 Kind (linkes) vorhanden; pruefen, ob Indizes innerhalb des Arrays liegen |
- | kidId = leftId; | + | |
- | } else { | + | if (c.compare(w[leftId], |
- | kidId = rightId; | + | |
- | } | + | } |
- | if(c.compare(w[kidId], | + | |
- | swap(w, i, kidId); | + | // 2 Kinder vorhanden, pruefen, ob rechtes Kind innerhalb des Arrays liegt |
- | reheap(w, c, kidId, k); | + | if (rightId <= k) { |
- | } | + | // groesseres der beiden Kinder in kidId speichern |
- | } | + | |
- | } | + | |
+ | // Schauen, ob Kind groesser ist, als aktuelles Element, falls ja, dann tauschen | ||
+ | | ||
+ | swap(w, kidId, i); | ||
+ | reheap(w, c, kidId, k); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
\\ | \\ | ||
d) | d) | ||
- | void heapSort(W[] w, Comparator< | + | < |
- | int n = w.length; | + | void heapSort(W[] w, Comparator< |
- | + | int n = w.length; | |
- | // Phase 1: Max-Heap-Eigenschaft herstellen | + | |
- | // (siehe Teilaufgabe a) | + | |
- | for(int i = n / 2 - 1; i >= 0; i--) { | + | |
- | reheap(w, | + | |
- | } | + | |
- | + | ||
- | // Phase 2: jeweils Maximum entnehmen und sortierte Liste am Ende aufbauen | + | |
- | // (siehe Teilaufgabe b) | + | |
- | for(int i = n - 1; i > 0; i--) { | + | |
- | swap(w, 0, i); | + | |
- | reheap(w, | + | |
- | } | + | |
- | } | + | |
| | ||
+ | // Phase 1: Halde aufbauen | ||
+ | for (int i = n / 2; i >= 0; i--) { | ||
+ | reheap(w, c, i, n - 1); | ||
+ | } | ||
+ | |||
+ | // Phase 2: Maximum entnehmen und sortierte Liste am Ende aufbauen | ||
+ | for (int i = n - 1; i > 0; i--) { | ||
+ | // Maximum an das Ende der Halde tauschen | ||
+ | swap(w, 0, i); | ||
+ | |||
+ | // Nach vorne getauschtes Element einsickern lassen und Haldeneigenschaft wiederherstellen | ||
+ | reheap(w, c, 0, i - 1); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
==== 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< | ||
for(char c : s.toCharArray()) { | for(char c : s.toCharArray()) { | ||
- | if(map.get(c) | + | Node n = map.get(c); |
- | map.put(c, new Node(c, 1)); | + | if(n != null) { |
+ | //variable frequenz updaten | ||
+ | n.f++; | ||
} else { | } else { | ||
- | map.get(c).f += 1; | + | //neuer node in die map |
+ | map.put(c, new Node(c,1)); | ||
} | } | ||
} | } | ||
Zeile 332: | Zeile 355: | ||
} | } | ||
} | } | ||
+ | </ |