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
pruefungen:bachelor:aud:loesungws08 [16.02.2013 09:27] – Dawodopruefungen:bachelor:aud:loesungws08 [11.05.2019 12:09] (aktuell) – 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 142: Zeile 148:
 f(n) berechnet sich wie in Aufgabe a), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c: 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)  **(* *)**
  
-**(**)** in **(*)** eingesetzt ergibt:+**(* *)** in **(*)** eingesetzt ergibt:
  
 lin(b, c, 1 + (((c - b) * a) % 100), steps - 1) lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
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; 
 +        //Oder auch einfach nur 
 +        // return childIndex/2;
 } }
 </code> </code>
Zeile 282: Zeile 291:
  
  
-==Aufgabe 8 (wp)==+==== Aufgabe 8 - wp-Kalkül ====
  
 **a)** **a)**