Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch   (Übersicht)

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
pruefungen:bachelor:aud:loesungss14 [22.03.2018 11:04] – Evrenpruefungen: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) ^ 
-\\ +{{: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 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 115: Zeile 104:
 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. +{{:pruefungen:bachelor:aud:floyd.png|}}
-**+
  
-Loesung uebernommen aus dem Forum, eventuell gegenchecken 
-https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14 
  
 +==== 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;
 +}
 +</code>
  
- 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) { +<code=java> 
- int[][] sol = new int[brd.length][mrl]; +static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { 
- for(int i = 0; i < brd.length; i++) { +    int[][] = null; 
- for(int j = 0; j < mrl; j++) { +    int[][] sol = new int[brd.length][mrl];
- 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) { +    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, r, c) && brd[r][c]) { // Diese Felder duerfen betreten werden 
- 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 k = 0; k < jumps.length; k++) { +</code> 
- if(exists(brd, jumps[k][0], jumps[k][1])) { +**c)** 
- if(solve(brd, sol, tf, jumps[k][0], jumps[k][1], n + 1)) { +<code=java> 
- return true; +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 } }; 
- sol[r][c] = 0; +     
- return false; +    //Basisfall, letzter Wert muss hier noch gesetzt werden 
- } +    if (n == tf) { 
-==== 4) Backtracking ==== +        sol[r][c] = n; 
-[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]+        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 219: 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 ====   
  
 \\ \\
-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<W> c, int i, int k) { +<code java> 
- int leftId = 2 * i + 1; +void reheap(W[] w, Comparator<W> c, int i, int k) { 
- 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], w[rightId]) > 0) { +    // nur 1 Kind (linkes) vorhanden; pruefen, ob Indizes innerhalb des Arrays liegen 
- kidId = leftId; +    if (leftId <= k && rightId > k) { 
- } else { +        if (c.compare(w[leftId], w[i]) > 0) { // Falls Kind groesser, dann tauschen 
- kidId = rightId; +            swap(w, leftId, i); 
- } +        } 
- if(c.compare(w[kidId], w[i]) > 0) { +    } else { 
- 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 
- } +            kidId = c.compare(w[leftId], w[rightId]) > 0 ? leftId : rightId; 
- }+ 
 +            // Schauen, ob Kind groesser ist, als aktuelles Element, falls ja, dann tauschen 
 +            if (c.compare(w[kidId], w[i]) > 0) { 
 +                swap(w, kidId, i); 
 +                reheap(w, c, kidId, k); 
 +            } 
 +        } 
 +    } 
 +} 
 +</code>
 \\ \\
 d) d)
- void heapSort(W[] w, Comparator<W> c) { +<code=java> 
- int n = w.length; +void heapSort(W[] w, Comparator<W> c) { 
-  +    int n = w.length;
- // Phase 1: Max-Heap-Eigenschaft herstellen +
- //          (siehe Teilaufgabe a) +
- for(int i = n / 2 - 1; i >= 0; i--) { +
- reheap(w, c, i, n-1); // Beide Grenzen inklusiv +
- } +
-  +
- // 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, c, 0, i - 1); +
- } +
- }+
                  
 +    // 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);
 +    }
 +} 
 +</code>
 +
 ====   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 355:
  }  }
  }  }
 +</code>