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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss14 [22.03.2018 12:36] – Evrenpruefungen:bachelor:aud:loesungss14 [28.05.2019 14:50] – Dbadtf_385
Zeile 42: Zeile 42:
  
 **b)** \\ **b)** \\
-**(i)** A schon vorhanden, Balancfaktoren stimmen auch => gar nichts machen ?? +(i) ^ 
-\\ +{{:pruefungen:bachelor:aud:binbaum1.png?200|}} 
-**(ii)** Nichts rotieren, da Balancfaktoren stimmen: + 
-<code> +(ii) ^ 
-            X(0) +{{:pruefungen:bachelor:aud:binbaum2.png?200|}} 
-           / \ + 
-        A(-1) Y(-1) +(iii) ^  
-           \   \ +{{:pruefungen:bachelor:aud:binbaum3.png?200|}}
-          B(0)  Z(0) +
-</code> +
-\\ +
-**(iii)** +
-C einfügen und anschließend Knoten (W) nach rechts rotieren ?? +
-<code> +
-           X(1)                        X(0) +
-           /  \                        /  \ +
-        W(2!)  Y(-1)                 V(0) Y(-1) +
-         /      \        ==>         / \    \      AVL-Eigenschaften wiederhergestellt +
-       V(1)     Z(0)              C(0) W(0)  Z(0) +
-       / +
-     C(0) +
-</code>+
 \\ \\
 **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 97: Zeile 83:
 **a)** \\ **a)** \\
 {A, B, C, D, E} \\ {A, B, C, D, E} \\
 +{A, B, D, E} \\
 +{A, B, C, E} \\
 +{A, B, C, D} \\
 {F, G, H} \\ {F, G, H} \\
 {A, B, C} \\ {A, B, C} \\
Zeile 116: Zeile 105:
  
 **d)** \\ **d)** \\
 +{{:pruefungen:bachelor:aud:floyd.png|}}
 ==== 4) Backtracking ==== ==== 4) Backtracking ====
  
Zeile 122: Zeile 111:
 https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14 https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14
  
 +<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 137: 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, i, j)) {+ if(exists(brd, i, j)) { //Hier noch mit &&brd[i][j] verunden
  sol[i][j] = 0;  sol[i][j] = 0;
  } else {  } else {
Zeile 147: Zeile 136:
  }  }
  
 +        //Achtung die folgende Implementierung enthaelt fehler! Lieber die Implementierung aus 
 +        //<<Code zum Selber Testen>> verwenden oder weiter scrollen
  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 168: Zeile 159:
  return false;  return false;
  }  }
 +</code>
  
 [[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]] [[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]
Zeile 219: Zeile 211:
  if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {  if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {
  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 244: Zeile 231:
 \\ \\
 c) c)
 +<code java>
 +       //vorsicht! hier sind nicht alle faelle abgedeckt! was passiert bei rightId > w.length - 1 ? ggf mit Vorlesungsfolie 13 S.39 von ws18/19 gegenchecken!!!
  void reheap(W[] w, Comparator<W> c, int i, int k) {  void reheap(W[] w, Comparator<W> c, int i, int k) {
  int leftId = 2 * i + 1;  int leftId = 2 * i + 1;
Zeile 261: Zeile 250:
  }  }
  }  }
 +</code>
 \\ \\
 d) d)
Zeile 281: Zeile 271:
                  
 ====   6) Bäume und Rekursion====    ====   6) Bäume und Rekursion====   
- LinkedList<Node> count(String s) {+<code java>  
 +LinkedList<Node> count(String s) {
  assert s != null : new IllegalArgumentException();  assert s != null : new IllegalArgumentException();
  HashMap<Character, Node> map = new HashMap<>();  HashMap<Character, Node> map = new HashMap<>();
  for(char c : s.toCharArray()) {  for(char c : s.toCharArray()) {
- if(map.get(c) == null) { + 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 326:
  }  }
  }  }
 +</code>