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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss14 [22.03.2018 10:08] – Evrenpruefungen:bachelor:aud:loesungss14 [31.07.2019 09:30] – Anpassungen Aufgabe 4 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) ^ 
-\\ +{{: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 (V) 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 93: Zeile 79:
 </code> </code>
  
 +====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} \\
  
-Loesung uebernommen aus dem Forum, eventuell gegenchecken +**b)** 
-https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14+^ A ^ B ^ C ^ D ^ E ^ 
 +| ∞ | [0] | ∞ | ∞ | ∞ |   
 +| ∞ | | 5<sub>B</sub> | ∞ | [3<sub>B</sub>] | 
 +| 16<sub>E</sub> | | [5<sub>B</sub>] | 18<sub>E</sub> | 
 +| 14<sub>C</sub> | | | [11<sub>C</sub>] | 
 +| [13<sub>D</sub>] | | | | |
  
 +Endergebnis: 13 | 0 | 5 | 11 | 3
  
- static boolean exists(boolean[][] brd, int r, int c) { +**c)** \\ 
- if(brd[r] == null || brd[r].length < 1) { +F --(7)--> B --(5)--> C --(6)--> D --(2)--> A \\ 
- return false; +Weglänge: 7 + 5 + 6 + 2 = 20 
- } + 
- if(r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { +**d)** \\ 
- return false; +{{:pruefungen:bachelor:aud:floyd.png|}}
- } +
- return true; +
- }+
  
- static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { 
- int[][] sol = new int[brd.length][mrl]; 
- for(int i = 0; i < brd.length; i++) { 
- for(int j = 0; j < mrl; j++) { 
- if(exists(brd, i, j)) { 
- 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) { 
- int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, 
- { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; 
- if(sol[r][c] >= 1) { 
- return false; 
- } 
- if(n == tf) { 
- sol[r][c] = n; 
- return true; 
- } 
- sol[r][c] = n; 
- for(int k = 0; k < jumps.length; k++) { 
- if(exists(brd, jumps[k][0], jumps[k][1])) { 
- if(solve(brd, sol, tf, jumps[k][0], jumps[k][1], n + 1)) { 
- return true; 
- } 
- } 
- } 
- sol[r][c] = 0; 
- return false; 
- } 
 ==== 4) Backtracking ==== ==== 4) Backtracking ====
-[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]+**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; 
 +} 
 +</code> 
 + 
 +**b)** 
 + 
 +<code=java> 
 +static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { 
 +    int[][] = null; 
 +    int[][] sol = new int[brd.length][mrl]; 
 + 
 +    for (int r = 0; r < brd.length; r++) { 
 +        for (int c = 0; c < mrl; c++) { 
 +            if (exists(brd, r, c) && brd[r][c]) { // Diese Felder duerfen betreten werden 
 +                sol[r][c] = 0; 
 +            } else { 
 +                sol[c][c] = -1; // Felder mit -1 vorbelegen 
 +            } 
 +        } 
 +    } 
 +    return sol; 
 +} 
 +</code> 
 +**c)** 
 +<code=java> 
 +static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { 
 +    // possible targets from (r,c) 
 +    int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 },  
 +                    { r - 2, c + 1 }, { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; 
 +     
 +    //Basisfall, letzter Wert muss hier noch gesetzt werden 
 +    if (n == tf) { 
 +        sol[r][c] = n; 
 +        return true; 
 +    } 
 +    for (int j = 0; j < jumps.length; j++) { 
 + 
 +        // Wert setzen 
 +        sol[r][c] = n  
 + 
 +        // Brett brd und Loesungsfeld sol pruefen 
 +        if (exists(brd, jumps[j][0], jumps[j][1]) && sol[jumps[j][0]][jumps[j][1]] == 0) { 
 + 
 +            // Rekursion 
 +            if (solve(brd, sol, tf, jumps[j][0], jumps[j][1], n + 1)) { 
 +                return true; 
 +            } 
 +            // Backtrack 
 +            sol[r][c] = 0; 
 +        }         
 +    }         
 +    return false; 
 +} 
 +</code> 
 + 
 + 
 + 
 + 
 +Alternative:
  
 ** a) *** ** a) ***
Zeile 198: Zeile 226:
  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;
  }  }
 </code> </code>
 +[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]
  
 ====   5) Haldensortierung ====    ====   5) Haldensortierung ====   
Zeile 223: Zeile 247:
 \\ \\
 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 240: Zeile 266:
  }  }
  }  }
 +</code>
 \\ \\
 d) d)
Zeile 260: Zeile 287:
                  
 ====   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 311: Zeile 342:
  }  }
  }  }
 +</code>