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 22:18] – 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 173: Zeile 176:
 ^ 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 ||||
-^ M | 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 ||
 ^ T | 1 4 5 8 |||| 7 | 2 | 6 3 || ^ T | 1 4 5 8 |||| 7 | 2 | 6 3 ||
Zeile 179: Zeile 182:
 ^ T | 1 4 5 8 |||| 2 7 || 6 | 3 | ^ T | 1 4 5 8 |||| 2 7 || 6 | 3 |
 ^ M | 1 4 5 8 |||| 2 7 || __3 6__ || ^ M | 1 4 5 8 |||| 2 7 || __3 6__ ||
-^ M | 1 4 5 8 |||| 2 3 6 7 |||| +^ M | 1 4 5 8 |||| __2 3 6 7__ |||| 
-^ M | 1 2 3 4 5 6 7 8||||||||+^ M | __1 2 3 4 5 6 7 8__||||||||
  
 **c)** **c)**
Zeile 216: Zeile 219:
   
  while(i < left.length && j < right.length) {  while(i < left.length && j < right.length) {
- if(left[i] < right[j]) {+ if(left[i] <= right[j]) {
  result[k] = left[i++];  result[k] = left[i++];
  } else {  } else {
Zeile 232: Zeile 235:
  }  }
   
- while(j < left.length) {+ while(j < right.length) {
  result[k] = right[j];  result[k] = right[j];
   
Zeile 245: Zeile 248:
 Programmcode zum selber testen: {{:pruefungen:bachelor:aud:mergesort.java.txt|:pruefungen:bachelor:aud:mergesort.java.txt}} Programmcode zum selber testen: {{:pruefungen:bachelor:aud:mergesort.java.txt|:pruefungen:bachelor:aud:mergesort.java.txt}}
  
-=== Aufgabe 6 - Graphen (15P) ===+==== Aufgabe 6 - Graphen ====
  
 **a)** **a)**
Zeile 272: 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+(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===+==== Aufgabe 7 - UML ====
 **a)** **a)**
  
-{{:pruefungen:bachelor:aud:screenshot1.png|:pruefungen:bachelor:aud:screenshot1.png}}+{{:pruefungen:bachelor:aud:05-08-2010-7-uml-pic00.png|:pruefungen:bachelor:aud:05-08-2010-7-uml-pic00.png}}
  
-{{:pruefungen:bachelor:aud:screenshot6.png|:pruefungen:bachelor:aud:screenshot6.png}}+{{:pruefungen:bachelor:aud:05-08-2010-7-uml-pic01.png|:pruefungen:bachelor:aud:05-08-2010-7-uml-pic01.png}}
  
 **b)** **b)**
  
-Eventuell nicht mehr Stoff aktueller Semester?+(Scheinbar nicht mehr Stoff aktueller Semester)
  
-===Aufgabe 8 - Rekursion und Iteration===+==== Aufgabe 8 - Rekursion und Iteration ====
 **a)** **a)**
  
-Kaskadenartige Rekursion, da mehrere rekursive Aufrufe im Rumpf vorkommen.+Kaskadenartige Rekursion, da mehrere rekursive Aufrufe im Rumpf vorkommen.(auf Schleife achten)
  
 **b)** **b)**
Zeile 305: Zeile 313:
 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];
  }  }
  
Zeile 312: Zeile 320:
  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) {
Zeile 325: Zeile 333:
 </code> </code>
  
-===Aufgabe 9 - WP-Kalkül===+==== Aufgabe 9 - wp-Kalkül ====
  
 **a)** **a)**
Zeile 342: Zeile 350:
  
 <code> <code>
-**LO:** Falsch, da kein k vorkommt +**LO:** Falsch, schon vor der Schleife ungültig: 
- kfs = 1, kf = 1 + k = 1, kf = 1, kfs = 1 
- kf! - 1 = 0+ kfs = kf! - 1 
 + 1 = 1 - 1 
 + 1 = 0
  
-**RO:** Richtig, Summe wird bis zum momentanen k gemacht, wie im code!+**RO:** Richtig, Summe wird bis zum momentanen k gebildet
  
-**LU:** Falsch, Summenbildung fehlt +**LU:** Falsch, schon vor der Schleife ungültig: 
- kfs = 1, kf = 1 + k = 1, kf = 1, kfs = 1 
- kfs + k! = 2+ 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
- kfs = 1, kf = 1 + Alternativ: Schon vor der Schleife ungültig: 
- (k + 1)! = 2+ k = 1, kf = 1, kfs = 1 
 + ... ∧ kf = (k + 1)! ∧ ... 
 + ... ∧ 1 = (1 + 1)! ∧ ... 
 + ... ∧ 1 = 2 ∧ ...
 </code> </code>
  
 **b) ii)** **b) ii)**
 <code> <code>
-Zu zeigen: {I ∧ b} => wp(A,I)+Zu zeigen: (I ∧ b) => wp(A,I)
  
 wp("kf *= k; kfs += kf; k++;", kfs = ∑ i! ∧ kf = (k-1)! ∧ 1 <= k <= n) = wp("kf *= k; kfs += kf; k++;", kfs = ∑ i! ∧ kf = (k-1)! ∧ 1 <= k <= n) =
Zeile 375: Zeile 390:
 </code> </code>
  
-old: +**b) ii)** 
- +V = (n - 1) - k
-<code> +
-wp("kf *= k, kfs = kfs + kf, k = k+1", kfs = ∑i! ∧  kf = (k-1)  ∧  1 <= k <= n) +
-= 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) +
-= kfs + kf * k = ∑ i kf * k = k! ∧ 1 <= k + 1 <= n  +
-= kfs = ∑i! - kf*k ∧ kf = (k-1)! ∧ 0 <= k <= n-1 +
-<-- b ∧ I = ∑i! ∧ kf= (k-1)! ∧ 1 <= k <= n +
-</code> +
  
 +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.