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:loesungss10 [16.02.2013 21:12] – Dawodopruefungen:bachelor:aud:loesungss10 [28.03.2016 11:56] (aktuell) – Marcel[Inf]
Zeile 1: Zeile 1:
-==forums-einträge==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8083-Klausur-05-08-2010]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8083-Klausur-05-08-2010]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8048-Klausuren-Wissensfragen]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8048-Klausuren-Wissensfragen]]
Zeile 9: Zeile 9:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8882-Wiisensfragen-05-08-2010]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8882-Wiisensfragen-05-08-2010]]
  
-==== Lösungsversuch ====+===== Lösungsversuch =====
  
  
-=== Aufgabe 1 - Wissensfragen (12P) ===+==== Aufgabe 1 - Wissensfragen ====
 **a)** O(n²) **a)** O(n²)
  
Zeile 26: Zeile 26:
 **e)** Richtig **e)** Richtig
  
-**f)** 2. und 3. Antwort sind richtig+**f)** 2. und 3. Antwort sind richtig (RuntimeException oder Unterklassen oder Error oder Unterklassen müssen nicht deklariert werden.)
  
-=== Aufgabe 2 - AVL-Bäume (10P) ===+==== Aufgabe 2 - AVL-Bäume ====
  
 **a)** **a)**
Zeile 54: Zeile 54:
  
 <code> <code>
-               42 +              42 
-             /    \+            /    \
           23      50           23      50
-         /   \       \+        /    \      \
        5     37     69        5     37     69
 </code> </code>
 +
 +(Der Balancefaktor bei 69 ist 0. 0 passt sowohl zu positivem als auch negativem Vorzeichen, folglich würde hier auch eine Einfachrotation reichen.)
  
 **e)** **e)**
Zeile 70: Zeile 72:
 Insgesamt ergibt sich somit ein Aufwand von O(log n) Insgesamt ergibt sich somit ein Aufwand von O(log n)
  
-=== Aufgabe 3 - Schreibtischlauf (10P) ===+==== Aufgabe 3 - Schreibtischlauf ====
  
 Java Datei zum selbst testen: {{:pruefungen:bachelor:aud:walkthrough.java.txt|:pruefungen:bachelor:aud:walkthrough.java.txt}} Java Datei zum selbst testen: {{:pruefungen:bachelor:aud:walkthrough.java.txt|:pruefungen:bachelor:aud:walkthrough.java.txt}}
Zeile 78: Zeile 80:
   - : [a, d, c, d] [a, b, a, d]   - : [a, d, c, d] [a, b, a, d]
  
-=== Aufgabe 4 - Streuspeicherung (12P) ===+==== Aufgabe 4 - Streuspeicherung ====
  
 **a)** **a)**
Zeile 111: Zeile 113:
 iii) iii)
  
-**O(n)**, da nun alle Werte in einer einzigen Liste verkettet sind+O(n), da nun alle Werte in einer einzigen Liste verkettet sind
  
 **c)**  **c)** 
Zeile 135: Zeile 137:
 Lastfaktor = 9/13 = 0,69 Lastfaktor = 9/13 = 0,69
  
-===Aufgabe 5 - Sortieren===+==== Aufgabe 5 - Sortieren ====
  
 **a)** **a)**
Zeile 153: Zeile 155:
 iv) iv)
  
-Zeile 6: <code java> for(int i = 0; i < n − 1 - j; ++i ) {</code>+Zeile 6: <code java> for(int i = 0; i < n − 1 - j; ++i) {</code>
  
 Beobachtung beim BubbleSort Verfahren: \\ Beobachtung beim BubbleSort Verfahren: \\
Zeile 159: Zeile 161:
  
 Am Beispiel: Am Beispiel:
-{**3**,1,2} -> {1,**3**,2} -> {1,2,**3**} \\+{**3**,2,1} -> {2,**3**,1} -> {2,1,**3**} \\ 
 +Zumindest Element **3** steht nun an seiner finalen Position.
  
 Man kann somit Schritt für Schritt die hintere Grenze für die innere Schleife dekrementieren. Man kann somit Schritt für Schritt die hintere Grenze für die innere Schleife dekrementieren.
Zeile 166: Zeile 169:
  
 **b)** **b)**
-^ T | 4 8 1 5 |||| 7 2 6 3 ||| + 
-^ T | 4 8 | 1 5 || 7 2 6 3 ||| +^ T | 4 8 1 5 |||| 7 2 6 3 |||| 
-^ T | 4 | 8 || 1 5 | 7 2 6 3 ||| +^ T | 4 8 || 1 5 || 7 2 6 3 |||| 
-^ M | __4 8__ | 1 5 || 7 2 6 3 ||| +^ T | 4 | 8 | 1 5 || 7 2 6 3 |||| 
-^ T | 4 8 | 1 | 5 | 7 2 6 3 ||| +^ M | __4 8__ || 1 5 || 7 2 6 3 |||| 
-^ M | 4 8 | __1 5__ || 7 2 6 3 ||| +^ T | 4 8 || 1 | 5 | 7 2 6 3 |||| 
-^ M | 1 4 5 8 ||| 7 2 6 3 ||| +^ M | 4 8 || __1 5__ || 7 2 6 3 |||| 
-^ T | 1 4 5 8 ||| 7 2 | 6 3 || +^ M | __1 4 5 8__ |||| 7 2 6 3 |||| 
-^ T | 1 4 5 8 ||| 7 | 2 | 6 3 || +^ T | 1 4 5 8 |||| 7 2 || 6 3 || 
-^ M | 1 4 5 8 ||| __2 7__ | 6 3 || +^ T | 1 4 5 8 |||| 7 | 2 | 6 3 || 
-^ T | 1 4 5 8 ||| 2 7 | 6 | 3 || +^ M | 1 4 5 8 |||| __2 7__ || 6 3 || 
-^ M | 1 4 5 8 ||| 2 7 | __3 6__ || +^ T | 1 4 5 8 |||| 2 7 || 6 | 3 | 
-^ M | 1 4 5 8 ||| 2 3 6 7 ||| +^ M | 1 4 5 8 |||| 2 7 || __3 6__ || 
-^ M | 1 2 3 4 5 6 7 8||||||+^ M | 1 4 5 8 |||| __2 3 6 7__ |||| 
 +^ M | __1 2 3 4 5 6 7 8__||||||||
  
 **c)** **c)**
  
 +<code java>
 +public static int[] mergesort(int[] m) {
 + if(m.length <= 1)
 + return m;
 +
 + int nLeft = m.length / 2;
 + int nRight = m.length - nLeft;
 +
 + int[] left = new int[nLeft];
 + int[] right = new int[nRight];
 +
 + for(int i = 0; i < nLeft; ++i) {
 + left[i] = m[i];
 + }
 +
 + for(int i = 0; i < nRight; ++i) {
 + right[i] = m[nLeft + i];
 + }
 +
 + return merge(mergesort(left), mergesort(right));
 +}
 +</code>
  
 +<code java>
 +public static int[] merge(int[] left, int[] right) {
 + int[] result = new int[left.length + right.length];
 +
 + int i = 0;
 + int j = 0;
 + int k = 0;
 +
 + while(i < left.length && j < right.length) {
 + if(left[i] <= right[j]) {
 + result[k] = left[i++];
 + } else {
 + result[k] = right[j++];
 + }
 +
 + ++k;
 + }
 +
 + while(i < left.length) {
 + result[k] = left[i];
 +
 + ++i;
 + ++k;
 + }
 +
 + while(j < right.length) {
 + result[k] = right[j];
 +
 + ++j;
 + ++k;
 + }
 +
 + return result;
 +}
 +</code>
 +
 +Programmcode zum selber testen: {{:pruefungen:bachelor:aud:mergesort.java.txt|:pruefungen:bachelor:aud:mergesort.java.txt}}
 +
 +==== Aufgabe 6 - Graphen ====
  
-=== Aufgabe 6 - Graphen (15P) === 
 **a)** **a)**
-|    Ingolstadt ^ Hof ^ Würzburg ^ Nürnberg ^ Regensburg ^ AK Deggendorf ^ AD Holledau ^ Passau ^ München ^  + 
-^ [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  +^    Ingolstadt ^ Hof ^ Würzburg ^ Nürnberg ^ Regensburg ^ AK Deggendorf ^ AD Holledau ^ Passau ^ München ^  
-^ 0 | ∞ | ∞ | 90 | ∞ | ∞ | [20] | ∞ | ∞ |  +| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  
-^ 0 | ∞ | ∞ | 90 | 90 | ∞ | 20 | ∞ | [70] |  +| 0 | ∞ | ∞ | 90 | ∞ | ∞ | [20] | ∞ | ∞ |  
-^ 0 | ∞ | ∞ | [90] | 90 | 210 | 20 | ∞ | 70 |  +| 0 | ∞ | ∞ | 90 | 90 | ∞ | 20 | ∞ | [70] |  
-^ 0 | 225 | 205 | 90 | [90] | 210 | 20 | ∞ | 70 |  +| 0 | ∞ | ∞ | [90] | 90 | 210 | 20 | ∞ | 70 |  
-^ 0 | 225 | 205 | 90 | 90 | [160] | 20 | ∞ | 70 |  +| 0 | 225 | 205 | 90 | [90] | 210 | 20 | ∞ | 70 |  
-^ 0 | 225 | 205 | 90 | 90 | 160 | 20 | 210 | 70 |  +| 0 | 225 | 205 | 90 | 90 | [160] | 20 | ∞ | 70 |  
-^ Ergebnis: | 225 | 205 | 90 | 90 | 160 | 20 | 210 | 70 | +| 0 | 225 | [205] | 90 | 90 | 160 | 20 | 210 | 70 | 
 +| 0 | 225 | 205 | 90 | 90 | 160 | 20 | [210] | 70 | 
 +| 0 | [225] | 205 | 90 | 90 | 160 | 20 | 210 | 70 | 
 +| Ergebnis: | 225 | 205 | 90 | 90 | 160 | 20 | 210 | 70 | 
  
 **b)** **b)**
-|   von ^ nach ^+ 
 +^ von ^ nach ^
 ^ Ingolstadt | AD Holledau | ^ Ingolstadt | AD Holledau |
 ^ AD Holledau | München | ^ AD Holledau | München |
Zeile 207: Zeile 275:
 ^ Nürnberg | Würzburg | ^ Nürnberg | Würzburg |
 ^ Nürnberg | Hof | ^ Nürnberg | Hof |
 +
 +Es sind auch leichte Abwandlungen hiervon gültig.
  
 **c)** **c)**
-AD Holledau <-> Passau 
  
-===Aufgabe 7 - UML===+(Scheinbar nicht mehr Stoff aktueller Semester) 
 + 
 +Ein Euler-Pfad ist ein Pfad, der jede Kante exakt einmal enthält. 
 +Mögliche Lösung: AD Holledau <-> Passau 
 + 
 +==== Aufgabe 7 - UML ====
 **a)** **a)**
-{{:pruefungen:bachelor:aud:screenshot1.png|:pruefungen:bachelor:aud:screenshot1.png}} 
  
-{{:pruefungen:bachelor:aud:screenshot6.png|:pruefungen:bachelor:aud:screenshot6.png}}+{{:pruefungen:bachelor:aud:05-08-2010-7-uml-pic00.png|:pruefungen:bachelor:aud:05-08-2010-7-uml-pic00.png}} 
 + 
 +{{:pruefungen:bachelor:aud:05-08-2010-7-uml-pic01.png|:pruefungen:bachelor:aud:05-08-2010-7-uml-pic01.png}}
  
 **b)** **b)**
  
 +(Scheinbar nicht mehr Stoff aktueller Semester)
  
-===Aufgabe 8 - Rekursion und Iteration===+==== Aufgabe 8 - Rekursion und Iteration ====
 **a)** **a)**
-kaskadenartige Rekursion+ 
 +Kaskadenartige Rekursion, da mehrere rekursive Aufrufe im Rumpf vorkommen.(auf Schleife achten)
  
 **b)** **b)**
-Es werden keine Zwischenwerte gespeichert, es wird immer wieder identische Zwischenergebnisse berechnet.  + 
 +Es werden keine Zwischenwerte gespeichert und somit immer wieder identische Zwischenergebnisse mehrfach berechnet.
  
 **c)** **c)**
Zeile 231: Zeile 309:
 private static int [ ] maxKnown = new int [MAX] ; private static int [ ] maxKnown = new int [MAX] ;
 // Gehen Sie davon aus , dass alle maxKnown [i] vorab mit −1 // Gehen Sie davon aus , dass alle maxKnown [i] vorab mit −1
-// korrekt initialisiert wurden .+// korrekt initialisiert wurden. 
 private static int knapsack (Item [ ] items , int capacity) { private static int knapsack (Item [ ] items , int capacity) {
  if(maxKnown[capacity]!= -1) {  if(maxKnown[capacity]!= -1) {
- return (maxKnown[capacity];+ return maxKnown[capacity];
  }  }
 +
  int maxValue = 0 ;  int maxValue = 0 ;
  for (int i = 0 ; i < items . length ; ++i ) {  for (int i = 0 ; i < items . length ; ++i ) {
  int spaceLeft = capacity − items [i].size;  int spaceLeft = capacity − items [i].size;
  if(spaceLeft >= 0 ) {  if(spaceLeft >= 0 ) {
- int value = knapsack (items, spaceLeft) + items [i].value;+ int value = knapsack(items, spaceLeft) + items[i].value; 
  if(value > maxValue) {  if(value > maxValue) {
- maxValue = valuee ;+ maxValue = value;
  }   }
  }  }
  }  }
 +
  maxKnown[capacity] = maxValue;  maxKnown[capacity] = maxValue;
  return maxValue;  return maxValue;
Zeile 251: Zeile 333:
 </code> </code>
  
-===Aufgabe 9 - WP-Kalkül===+==== Aufgabe 9 - wp-Kalkül ==== 
 **a)** **a)**
 +
 <code> <code>
-wp(’if (a <= b) {a = -(2*b+a); b -= 1-a;} else {b = -b-a-1;}’, b < 0) +wp("if (a ≤ b) {a = -(2*b + a); b -= 1 - a;} else {b = -b - a - 1;}", b < 0) = 
-= [a <= b ∧ wp("a = -(2b+a), b-=1-a;" b <0)] ∨ [a > b ∧ wp("b=-b-a-1", b < 0] +[(a ≤ b) ∧ wp("a = -(2*b + a); b = b - (1 - a);" b < 0)] ∨ [¬(a ≤ b) ∧ wp("b = -b - a - 1", b < 0)] = 
-= [a <= b ∧ wp("a=-(2b+a);" b-1+a <0)] ∨ [a > b ∧ -b-a-1 < 0]  +[(a ≤ b) ∧ wp("a = -(2*b + a);" b - (1 - a) < 0)] ∨ [(a > b) ∧ (-b - a - 1 < 0)] = 
-= [a <= b ∧ b-1 +(-(2b+a))<0] ∨ [a > b ∧ --a-1 < 0]  +[(a ≤ b) ∧ (b - (1 - (-(2*b + a))) < 0)] ∨ [(a > b) ∧ (-b - a - 1 < 0)] = 
-= [a <= b ∧ -b-a-1 < 0] ∨ [a>b ∧-b-a-1 <0] +[(a ≤ b) ∧ (b -1 -2*b - a < 0)] ∨ [(a > b) ∧ (-b - a - 1 < 0)] = 
-= -a-b-1 <0+[(a ≤ b) ∧ (-b - a - 1 < 0)] ∨ [(a > b) ∧ (-b - a - 1 < 0)] = 
 +(-b - a - 1 < 0)
 </code> </code>
  
 **b) i)** **b) i)**
  
-**lo:** falsch, da kein k vorkommt+<code> 
 +**LO:** Falsch, schon vor der Schleife ungültig: 
 + k = 1, kf = 1, kfs = 1 
 + kfs = kf! - 1 
 + 1 = 1 - 1 
 + 1 = 0
  
-**lu:** falsch, summenbildung fehlt+**RO:** Richtig, Summe wird bis zum momentanen k gebildet
  
-**ro:** richtig, summe wird bis zum momentanen k gemacht, wie im code!+**LU:** Falsch, schon vor der Schleife ungültig: 
 + k = 1, kf = 1, kfs = 1 
 + kf = kfs + k! 
 + 1 = 1 + 1! 
 + 1 = 2
  
-**ru:** falsch, es wird bis n-1 summiert, egal wie oft die schleife durchlaufen wird+**RU:** Falsch, es wird bis n-1 summiert, egal wie oft die schleife durchlaufen wird 
 + Alternativ: Schon vor der Schleife ungültig: 
 + k = 1, kf = 1, kfs = 1 
 + ... ∧ kf = (k + 1)! ∧ ... 
 + ... ∧ 1 = (1 + 1)! ∧ ... 
 + ... ∧ 1 = 2 ∧ ... 
 +</code>
  
 **b) ii)** **b) ii)**
 <code> <code>
-wp("kf *= k, kfs = kfs + kf, k = k+1", kfs = ∑i! ∧  kf = (k-1)  ∧  1 <= k <= n) +Zu zeigen: (I ∧ b) => wp(A,I) 
-= wp("kf = kf*k, kfs = kfs + kf, k = k+1" kfs = ∑i! ∧ kf = k! ∧ 1 <= k ü 1 <= n)  + 
-= wp("kf = kf*k, kfs = kfs + kf, k = k+1" kfs + kf = ∑i! ∧ kf = k! 1 <= k+1 <=n) +wp("kf *= k; kfs += kf; k++;", kfs = ∑ i! ∧ kf = (k-1)! ∧ 1 <= k <= n) = 
-= kfs + kf * k = ∑ i kf * k = k! ∧ 1 <= k + 1 <= n  +wp("kf = kf * k; kfs = kfs + kf; k = k + 1;", kfs = ∑ i! ∧ kf = (k-1)! ∧ 1 <= k <= n) = 
-= kfs = ∑i! - kf*k ∧ kf = (k-1)! ∧ 0 <= k <= n-1 +wp("kf = kf * k; kfs = kfs + kf;", kfs = ∑ i! ∧ kf = (k + 1-1)! ∧ 1 <= k + 1 <= n) = 
-<-- b ∧ I = ∑i! ∧ kf= (k-1)! ∧ 1 <= k <= n+wp("kf = kf * k;", kfs + kf = ∑ i! ∧ kf = (k + 1 - 1)! ∧ 1 <= k + 1 <= n) = 
 +(kfs + kf * k = ∑ i! ∧ kf * k = (k + 1 - 1)! ∧ 1 <= k + 1 <= n) = 
 +(kfs = ∑ i! - kf * k ∧ kf = (k - 1)! ∧ 0 <= k <= n - 1) 
 + 
 +{I ∧ b} => wp(A,I) = 
 +{(kfs = ∑ i! ∧ kf = (k-1)! ∧ 1 <= k <= n) ∧ k ≤ n - 1} => (kfs = ∑ i! - kf * k ∧ kf = (k - 1)! ∧ 0 <= k <= n - 1) = 
 +¬(kfs = ∑ i!) ∨ ¬(kf = (k-1)!) ∨ ¬(1 <= k <= n) ∨ ¬(k ≤ n - 1) ∨ (kfs = ∑ i! - kf * k ∧ kf = (k - 1)! ∧ 0 <= k <= n - 1) = 
 +(kfs ≠ ∑ i!) ∨ (kf ≠ (k-1)!) ∨ (n < k < 1) ∨ (k > n - 1) ∨ (kfs = ∑ i! - kf * k ∧ kf = (k - 1)! ∧ 0 <= k <= n - 1) = 
 +...
 </code> </code>
 +
 +**b) ii)**
 +V = (n - 1) - k
 +
 +k wird sukzessive erhöht, während (n-1) von der Eingabe abhängig, aber im Programm selbst konstant ist.
 +V ist damit monoton fallend. Durch die Abbruchbedingung der Schleife ist V nach unten durch die 0 beschränkt.