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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss10 [16.02.2013 21:38] – Dawodo | pruefungen:bachelor:aud:loesungss10 [28.03.2016 11:52] – Marcel[Inf] | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forums-einträge== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 9: | Zeile 9: | ||
* [[https:// | * [[https:// | ||
- | ==== Lösungsversuch ==== | + | ===== Lösungsversuch |
- | === Aufgabe 1 - Wissensfragen | + | ==== 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 |
- | === Aufgabe 2 - AVL-Bäume | + | ==== Aufgabe 2 - AVL-Bäume |
**a)** | **a)** | ||
Zeile 54: | Zeile 54: | ||
< | < | ||
- | 42 | + | |
- | | + | / \ |
23 50 | 23 50 | ||
- | / | + | |
| | ||
</ | </ | ||
Zeile 70: | Zeile 70: | ||
Insgesamt ergibt sich somit ein Aufwand von O(log n) | Insgesamt ergibt sich somit ein Aufwand von O(log n) | ||
- | === Aufgabe 3 - Schreibtischlauf | + | ==== Aufgabe 3 - Schreibtischlauf |
Java Datei zum selbst testen: {{: | Java Datei zum selbst testen: {{: | ||
Zeile 78: | Zeile 78: | ||
- : [a, d, c, d] [a, b, a, d] | - : [a, d, c, d] [a, b, a, d] | ||
- | === Aufgabe 4 - Streuspeicherung | + | ==== Aufgabe 4 - Streuspeicherung |
**a)** | **a)** | ||
Zeile 111: | Zeile 111: | ||
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 135: | ||
Lastfaktor = 9/13 = 0,69 | Lastfaktor = 9/13 = 0,69 | ||
- | ===Aufgabe 5 - Sortieren=== | + | ==== Aufgabe 5 - Sortieren |
**a)** | **a)** | ||
Zeile 153: | Zeile 153: | ||
iv) | iv) | ||
- | Zeile 6: <code java> for(int i = 0; i < n − 1 - j; ++i ) {</ | + | Zeile 6: <code java> for(int i = 0; i < n − 1 - j; ++i) {</ |
Beobachtung beim BubbleSort Verfahren: \\ | Beobachtung beim BubbleSort Verfahren: \\ | ||
Zeile 159: | Zeile 159: | ||
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 174: | ||
^ 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 180: | ||
^ 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 217: | ||
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 233: | ||
} | } | ||
- | while(j < left.length) { | + | while(j < right.length) { |
result[k] = right[j]; | result[k] = right[j]; | ||
Zeile 245: | Zeile 246: | ||
Programmcode zum selber testen: {{: | Programmcode zum selber testen: {{: | ||
- | === Aufgabe 6 - Graphen | + | ==== Aufgabe 6 - Graphen ==== |
**a)** | **a)** | ||
+ | |||
^ Ingolstadt ^ Hof ^ Würzburg ^ Nürnberg ^ Regensburg ^ AK Deggendorf ^ AD Holledau ^ Passau ^ München ^ | ^ Ingolstadt ^ Hof ^ Würzburg ^ Nürnberg ^ Regensburg ^ AK Deggendorf ^ AD Holledau ^ Passau ^ München ^ | ||
| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ||
Zeile 260: | Zeile 263: | ||
**b)** | **b)** | ||
+ | |||
^ von ^ nach ^ | ^ von ^ nach ^ | ||
^ Ingolstadt | AD Holledau | | ^ Ingolstadt | AD Holledau | | ||
Zeile 269: | Zeile 273: | ||
^ 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)** | ||
- | {{: | + | {{: |
- | {{: | + | {{: |
**b)** | **b)** | ||
+ | (Scheinbar nicht mehr Stoff aktueller Semester) | ||
- | ===Aufgabe 8 - Rekursion und Iteration=== | + | ==== Aufgabe 8 - Rekursion und Iteration |
**a)** | **a)** | ||
- | kaskadenartige | + | |
+ | Kaskadenartige | ||
**b)** | **b)** | ||
- | Es werden keine Zwischenwerte gespeichert, es wird immer wieder identische Zwischenergebnisse berechnet. | + | |
+ | Es werden keine Zwischenwerte gespeichert | ||
**c)** | **c)** | ||
Zeile 294: | Zeile 307: | ||
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 | + | 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, |
if(value > maxValue) { | if(value > maxValue) { | ||
- | maxValue = valuee | + | maxValue = value; |
} | } | ||
} | } | ||
} | } | ||
+ | |||
maxKnown[capacity] = maxValue; | maxKnown[capacity] = maxValue; | ||
return maxValue; | return maxValue; | ||
Zeile 314: | Zeile 331: | ||
</ | </ | ||
- | ===Aufgabe 9 - WP-Kalkül=== | + | ==== Aufgabe 9 - wp-Kalkül ==== |
**a)** | **a)** | ||
+ | |||
< | < | ||
- | 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(" | + | [(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 ≤ 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) | ||
</ | </ | ||
**b) i)** | **b) i)** | ||
- | **lo:** falsch, da kein k vorkommt | + | < |
+ | **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 | + | **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: | ||
+ | k = 1, kf = 1, kfs = 1 | ||
+ | ... ∧ kf = (k + 1)! ∧ ... | ||
+ | ... ∧ 1 = (1 + 1)! ∧ ... | ||
+ | ... ∧ 1 = 2 ∧ ... | ||
+ | </ | ||
**b) ii)** | **b) ii)** | ||
< | < | ||
- | 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) = |
- | < | + | wp("kf = kf * k;", |
+ | (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 | ||
+ | (kfs ≠ ∑ i!) ∨ (kf ≠ (k-1)!) ∨ (n < k < 1) ∨ (k > n - 1) ∨ (kfs = ∑ i! - kf * k ∧ kf = (k - 1)! ∧ 0 <= k <= n - 1) = | ||
+ | ... | ||
</ | </ | ||
+ | |||
+ | **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. |