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 09:27] – 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
  
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 118: Zeile 121:
  return lin(1, 2, 3, n);  return lin(1, 2, 3, n);
 } }
 +private static int lin(int a, int b, int c, int steps) { ...
 </code> </code>
  
Zeile 125: Zeile 129:
 f(2) = 3 \\ f(2) = 3 \\
  
-Aus dem gegebenen Aufruf und dieser Basisfälle lässt sich schließen: \\ +Aus dem gegebenen Aufruf (mit 1,2,3)  und dieser Basisfälle lässt sich schließen: \\ 
-a = 1 = f(0) -> f(n - 3) \\ +a = 1 = f(0)  -->  entspricht f(n - 3) \\ 
-b = 2 = f(1) -> f(n - 2) \\ +b = 2 = f(1)  -->  entspricht f(n - 2) \\ 
-c = 3 = f(2) -> f(n - 1) \\+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.
  
 Somit wissen wir: \\ Somit wissen wir: \\
Zeile 157: Zeile 163:
  return a;  return a;
  
- lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);+ return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
 } }
 </code> </code>
Zeile 167: Zeile 173:
 f(0) = lin(1, 2, 3, 0) \\ f(0) = lin(1, 2, 3, 0) \\
 Das Ergebnis steht in Variable a. Das Ergebnis steht in Variable a.
 +
  
 **c)** **c)**
Zeile 176: Zeile 183:
  
  while(n > 0) {  while(n > 0) {
- int fn = 1 + (((c - b) * a) % 100)+ int fn = 1 + (((c - b) * a) % 100);
  a = b;  a = b;
  b = c;  b = c;
Zeile 188: Zeile 195:
  
  
-==Aufgabe 6 - Suchbäume==+==== Aufgabe 6 - Suchbäume ====
  
 **a)** **a)**
Zeile 226: Zeile 233:
   * Rotation an Knoten: 64   * Rotation an Knoten: 64
  
-  * **Einfachrotation**, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind+  * **Einfachrotation** gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind
  
 **e)** **e)**
Zeile 232: Zeile 239:
 {{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}} {{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}}
  
-==Aufgabe 7 - Heap==+==== 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 255: 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 282: Zeile 289:
  
  
-==Aufgabe 8 (wp)==+==== Aufgabe 8 - wp-Kalkül ====
  
 **a)** **a)**