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 Überarbeitung | ||
pruefungen:bachelor:aud:loesungss10 [16.02.2013 22:18] – Dawodo | pruefungen:bachelor:aud:loesungss10 [28.03.2016 11:56] (aktuell) – 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 | ||
- | / | + | |
| | ||
</ | </ | ||
+ | |||
+ | (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 | + | ==== Aufgabe 3 - Schreibtischlauf |
Java Datei zum selbst testen: {{: | Java Datei zum selbst testen: {{: | ||
Zeile 78: | Zeile 80: | ||
- : [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 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 ) {</ | + | Zeile 6: <code java> for(int i = 0; i < n − 1 - j; ++i) {</ |
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: {{: | Programmcode zum selber testen: {{: | ||
- | === Aufgabe 6 - Graphen | + | ==== 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: | ||
- | ===Aufgabe 7 - UML=== | + | ==== Aufgabe 7 - UML ==== |
**a)** | **a)** | ||
- | {{: | + | {{: |
- | {{: | + | {{: |
**b)** | **b)** | ||
- | Eventuell | + | (Scheinbar |
- | ===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 | + | 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, |
if(value > maxValue) { | if(value > maxValue) { | ||
Zeile 325: | Zeile 333: | ||
</ | </ | ||
- | ===Aufgabe 9 - WP-Kalkül=== | + | ==== Aufgabe 9 - wp-Kalkül |
**a)** | **a)** | ||
Zeile 342: | Zeile 350: | ||
< | < | ||
- | **LO:** Falsch, | + | **LO:** Falsch, |
- | 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, | + | **LU:** Falsch, |
- | 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 ∧ ... | ||
</ | </ | ||
**b) ii)** | **b) ii)** | ||
< | < | ||
- | Zu zeigen: | + | Zu zeigen: |
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: | ||
</ | </ | ||
- | old: | + | **b) ii)** |
- | + | V = (n - 1) - k | |
- | < | + | |
- | wp(" | + | |
- | = 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 | + | |
- | </ | + | |
+ | 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. |