Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
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:12] – 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 166: | Zeile 167: | ||
**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), | ||
+ | } | ||
+ | </ | ||
+ | <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; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Programmcode zum selber testen: {{: | ||
+ | |||
+ | ==== Aufgabe 6 - Graphen ==== | ||
- | === Aufgabe 6 - Graphen (15P) === | ||
**a)** | **a)** | ||
- | | | + | |
- | ^ [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | + | ^ |
- | ^ 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 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 231: | 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 251: | 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. |