Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Ü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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws08 [16.02.2013 08:43] – Dawodopruefungen:bachelor:aud:loesungws08 [11.05.2019 10:23] – SpeedyGonzalez
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7553-Frage-zur-Klausur-vom-19-02-2009-Aufgabe-8b]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7553-Frage-zur-Klausur-vom-19-02-2009-Aufgabe-8b]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7085-19-02-2009-Aufgabe-1]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7085-19-02-2009-Aufgabe-1]]
Zeile 7: Zeile 7:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung]]
  
-====Lösungsversuch====+===== Lösungsversuch =====
  
-==Aufgabe 1 - Wissensfragen==+==== Aufgabe 1 - Wissensfragen ====
 **a)** Falsch, es muss sortiert sein **a)** Falsch, es muss sortiert sein
  
-**b)** 3 - eine Schleife korrekt ist+**b)** Nummer 3: eine Schleife korrekt ist
  
 **c)** Richtig **c)** Richtig
Zeile 28: Zeile 28:
 **i)** 1 - kontextsensitiven Grammatiken **i)** 1 - kontextsensitiven Grammatiken
  
-==Aufgabe 2 - Graphen==+==== Aufgabe 2 - Graphen ==== 
 **a)**  **a)** 
 ^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^ ^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^
Zeile 49: Zeile 50:
 ^ F | 10 | A -> B -> E -> F | ^ F | 10 | A -> B -> E -> F |
  
-==Aufgabe 3 - Java==+==== Aufgabe 3 - Java ====
  
 **a)** **a)**
Zeile 75: Zeile 76:
 {{:pruefungen:bachelor:aud:test-07-08_2.java.txt|:pruefungen:bachelor:aud:test-07-08_2.java.txt}} {{:pruefungen:bachelor:aud:test-07-08_2.java.txt|:pruefungen:bachelor:aud:test-07-08_2.java.txt}}
  
-==Aufgabe 4 - ADT==+==== Aufgabe 4 - ADT ====
 **a)** **a)**
-  contains(x, create) = false +<code> 
-  contains(x, append(x, L)) = 1 + contains(x, L) +contains(x, create) = false 
-  contains(x, append(y, L)) = contains(x, L)+contains(x, append(x, L)) = true 
 +contains(x, append(y, L)) = contains(x, L) 
 +</code>
  
 **b)** **b)**
-A -> D -> create +A -> D
  
 **c)** **c)**
 +<code>
 +append(head(append(D, create), append(A, create)) = 
 +A1
 += append(head(prepend(D, create), append(A, create)) = 
 +A1
 += append(head(prepend(D, create), prepend(A, create)) = 
 +A3
 += append(D, prepend(A, create)) = 
 +A2
 += prepend(A, append(D, create)) = 
 +A1
 += prepend(A, prepend(D, create))
 +</code>
  
-  append(head(append(D, create), append(A, create)) =  +==== Aufgabe 5 - Pseudo-Zufallszahlen ====
-  A1 +
-  = append(head(prepend(D, create), append(A, create)) =  +
-  A1 +
-  = append(head(prepend(D, create), prepend(A, create)) =  +
-  A3 +
-  = append(D, prepend(A, create)) =  +
-  A2 +
-  = prepend(A, append(D, create)) =  +
-  A1 +
-  = prepend(A, prepend(D, create)) +
- +
- +
-==Aufgabe 5 - Pseudo-Zufallszahlen==+
 **a)** **a)**
 <code java> <code java>
Zeile 114: Zeile 117:
 **Vorüberlegungen:**\\  **Vorüberlegungen:**\\ 
  
-f(n - 1) ^= c, da f(2) = 2 + 1 = 3 ist; analog:\\  +<code java> 
-f(n - 2) ^= b\\  +public static int f(int n) { 
-f(n - 3) ^= a+ return lin(1, 2, 3, n); 
 +} 
 +private static int lin(int a, int b, int c, int steps) { ... 
 +</code> 
 + 
 +Die Basisfälle der Funktion sind für n < 3 gegeben: \\ 
 +f(0) = 1 \\ 
 +f(1) = 2 \\ 
 +f(2) = 3 \\ 
 + 
 +Aus dem gegebenen Aufruf (mit 1,2,3)  und dieser Basisfälle lässt sich schließen: \\ 
 +a = 1 = f(0)  -->  entspricht f(n - 3) \\ 
 +b = 2 = f(1)  -->  entspricht f(n - 2) \\ 
 +c = 3 = f(2)  -->  entspricht f(n - 1) \\ 
 + 
 +Das Wichtige an dieser Aufgabe ist sich bewusst zu machen, wie die Werte im angegebenem Aufruf, mit den Basisfällen bzw. f(n-3), f(n-2), f(n-1) in der angegebenen Formel korrespondieren. Das Ziel ist ja diese Werte der Formel in Java-Code auszudrücken.
  
-lin (a, b, c) ^= lin (f(n - 3), f(n - 2), f(n - 1), steps)+Somit wissen wir: \\ 
 +lin(a, b, c, steps) -> lin(f(n - 3), f(n - 2), f(n - 1), steps)
  
-Wir starten also am Basisfall n < 3 ( => Bottom-Up ), weshalb nur noch der "sonst"-Teil beachtet werden muss. +Wir starten also am Basisfall n < 3 (=> Bottom-Up), weshalb nur noch der "sonst"-Teil beachtet werden muss.
  
 **Nächster "step": n + 1** **Nächster "step": n + 1**
  
-lin (f(n - 2), f(n - 1), f(n), steps - 1)  **(*)**+lin(f(n - 2), f(n - 1), f(n), steps - 1)  **(*)**
  
-f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden. f(n) berechnet sich wie in Aufgabe a) und sieht mit a, b, c dann so aus:+f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden.\\ 
 +f(n) berechnet sich wie in Aufgabe a), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c:
  
-f(n) = 1 + (((c - b) * a) % 100)+f(n) = 1 + (((c - b) * a) % 100)   **(* *)**
  
-Das in **(*)** eingesetzt ergibt dann+**(* *)** in **(*)** eingesetzt ergibt:
  
 lin(b, c, 1 + (((c - b) * a) % 100), steps - 1) lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
Zeile 140: Zeile 160:
  
 private static int lin(int a, int b, int c, int steps) { private static int lin(int a, int b, int c, int steps) {
-    if (steps == 0) { + if (steps == 0) 
-        return a; + return a; 
-    } else { + 
-        lin(b, c, 1 + (((c - b) * a) % 100), steps - 1); + return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
-    }+
 } }
 </code> </code>
Zeile 150: Zeile 169:
 **Warum steht das Ergebnis gerade in a?** **Warum steht das Ergebnis gerade in a?**
  
-Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift: f(0) = lin(1, 2, 3, 0). Da n = 0 < 3, greift der sonst-Fall und das Ergebnis muss n + 1 = 0 + 1 = 1 sein. Und die 1 steht in a.+Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift:\\ 
 +f(0) = 1 \\ 
 +f(0) = lin(1, 2, 3, 0) \\ 
 +Das Ergebnis steht in Variable a. 
  
 **c)** **c)**
 <code java> <code java>
 public static int f(int n) { public static int f(int n) {
- int a = 1, b = 2, c = 3; + int a = 1; 
- while (n > 0) { + int b = 2; 
- int tmp = a;+ int c = 3; 
 + 
 + while(n > 0) { 
 + int fn = 1 + (((c - b) * a) % 100);
  a = b;  a = b;
  b = c;  b = c;
- c = 1 + (((b-a)*tmp)%100);+ c = fn;
  n--;  n--;
  }  }
 +
  return a;  return a;
 } }
 </code> </code>
-==Aufgabe 6 - Suchbäume==+ 
 + 
 +==== Aufgabe 6 - Suchbäume ==== 
 **a)** **a)**
 <code> <code>
Zeile 172: Zeile 202:
     /  \     /  \
   23 42   23 42
- /      / \+ /     /  \
 7     32  64 7     32  64
-            \+             \
              81              81
 </code> </code>
Zeile 189: Zeile 219:
  
 **c)** **c)**
 +
 +Verwendete Definitionen:\\
 +  * Höhe eines Blatts: 0
 +  * Daraus folgt die Höhe des leeren Baums: -1
 +  * Balancefaktor: (Höhe des linken Teilbaums) - (Höhe des rechten Teilbaums)
  
 {{:pruefungen:bachelor:aud:ws08-6-c.png|:pruefungen:bachelor:aud:ws08-6-c.png}} {{:pruefungen:bachelor:aud:ws08-6-c.png|:pruefungen:bachelor:aud:ws08-6-c.png}}
Zeile 196: Zeile 231:
 {{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}} {{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}}
  
-  * Rotation an: 64+  * Rotation an Knoten: 64
  
-  * **Einfachrotation**, da die Vorzeichen der Balancewerte von 81 und 64 gleich sind+  * **Einfachrotation** gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind
  
 **e)** **e)**
-... 
  
-==Aufgabe 7 - Heap==+{{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}} 
 + 
 +==== Aufgabe 7 - Heap ====
  
 **a)**  **a)** 
-Der Wert jedes Knotens muss größer, als der seiner Kinder sein.+Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.
  
 **b)** **b)**
Zeile 226: Zeile 262:
 <code java> <code java>
 public int parentIndex (int childIndex) { public int parentIndex (int childIndex) {
- return (childIndex - 1) / 2;+ return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2;
 } }
 </code> </code>
Zeile 253: Zeile 289:
  
  
-==Aufgabe 8 (wp)==+==== Aufgabe 8 - wp-Kalkül ====
  
 **a)** **a)**