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:loesungws10 [17.02.2013 14:37] – Dawodo | pruefungen:bachelor:aud:loesungws10 [04.08.2019 15:15] – Bei unterrichteten Graphen müssen Kanten in der Mengenschreibweise eckige statt runder Klammern haben SpeedyGonzalez | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forum== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 6: | Zeile 6: | ||
- | ==== Lösungsversuch ==== | + | ===== Lösungsversuch |
- | === Aufgabe 1 - Wissensfragen | + | ==== Aufgabe 1 - Wissensfragen |
**a)** Falsch, alle Throwables können mit catch abgefangen werden, das heißt auch java.lang.Error und davon abgeleitete Klassen. \\ | **a)** Falsch, alle Throwables können mit catch abgefangen werden, das heißt auch java.lang.Error und davon abgeleitete Klassen. \\ | ||
Ob ein Abfangen sinnvoll ist oder unter Umständen fehlschlagen kann (beispielsweise bei einem OutOfMemoryError unter Umständen denkbar), ist an dieser Stelle nicht gefragt. | Ob ein Abfangen sinnvoll ist oder unter Umständen fehlschlagen kann (beispielsweise bei einem OutOfMemoryError unter Umständen denkbar), ist an dieser Stelle nicht gefragt. | ||
Zeile 20: | Zeile 20: | ||
* f ∈ O(log n) | * f ∈ O(log n) | ||
* g ∈ O(n log n); | * g ∈ O(n log n); | ||
+ | Hinweis: Hier ist ein kleiner Fehler in der Aufgabenstellung: | ||
**e)** Richtig, denn ohne wahlfreien Zugriff muss die verkettete Liste bis zum gesuchten Element durchlaufen werden. Dass sie sortiert ist, ändert daran nichts, da besser Suchverfahren wie Binary Search wahlfreien Zugriff voraussetzen. | **e)** Richtig, denn ohne wahlfreien Zugriff muss die verkettete Liste bis zum gesuchten Element durchlaufen werden. Dass sie sortiert ist, ändert daran nichts, da besser Suchverfahren wie Binary Search wahlfreien Zugriff voraussetzen. | ||
Zeile 34: | Zeile 35: | ||
Zusatzinfo: \\ | Zusatzinfo: \\ | ||
- | **Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? | + | **Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? |
**Antwort: | **Antwort: | ||
- | === Aufgabe 2 - Bäume | + | ==== Aufgabe 2 - Bäume |
**a)** | **a)** | ||
Zeile 68: | Zeile 69: | ||
X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r | X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r | ||
V = {A, B, C, D, E, F, G} | V = {A, B, C, D, E, F, G} | ||
- | E = {(A,B), (A,G), (B,D), (B,E), (B,F), (D,C)} | + | E = {[A,[A,G], [B,D], [B,E], [B,F], [D,C]} |
r = A | r = A | ||
</ | </ | ||
Zeile 96: | Zeile 97: | ||
<code java> | <code java> | ||
public boolean isUndirected(boolean[][] amx) { | public boolean isUndirected(boolean[][] amx) { | ||
- | for(int i = 0; i < amx.length; i++) { // Zeilen | + | for(int i = 0; i < amx.length; i++) { // Zeilen |
- | for(int j = 0; j < i; j++) { // Spalten | + | if(amx[i][i]) |
+ | return false; | ||
+ | for(int j = 0; j < i; j++) { | ||
if(amx[i][j] != amx[j][i]) | if(amx[i][j] != amx[j][i]) | ||
return false; | return false; | ||
Zeile 139: | Zeile 142: | ||
Programm zum selber Testen: {{: | Programm zum selber Testen: {{: | ||
- | === Aufgabe 3 === | + | ==== Aufgabe 3 - Sortieren ==== |
**a)** 96 oder kleiner | **a)** 96 oder kleiner | ||
- | **b)** | + | **b)** |
- | * von Vorne nach Hinten: Falsch | + | |
- | * von Hinten nach Vorne: Richtig | + | |
**c)** | **c)** | ||
Zeile 185: | Zeile 186: | ||
Programm zum selber Testen: {{: | Programm zum selber Testen: {{: | ||
- | === Aufgabe 4 === | + | ==== Aufgabe 4 - Rekursion ==== |
**a)** Kaskadenartige Rekursion | **a)** Kaskadenartige Rekursion | ||
Zeile 195: | Zeile 196: | ||
long[] result = new long[n+1]; | long[] result = new long[n+1]; | ||
long[][] dd = new long[n+1][n+1]; | long[][] dd = new long[n+1][n+1]; | ||
+ | // ^ eigentlich Speicherplatzverschwendung | ||
+ | // Besser: mit for-Schleife (mit i<=n): in dd[i] = new long[i+1]; | ||
for(int k = 0; k <= n; k++) { | for(int k = 0; k <= n; k++) { | ||
Zeile 239: | Zeile 242: | ||
Programm zum selber Testen: {{: | Programm zum selber Testen: {{: | ||
- | === Aufgabe 5 - ADT (11 Punkte) | + | ==== Aufgabe 5 - ADT ==== |
- | **a)** Ergebnis: 24.02.2011 | + | **a)** Ergebnis: 24.02.2011 |
+ | Regeln: P1 | ||
- | **b)** Ergebnis: 01.01.1970 | + | **b)** Ergebnis: 01.01.1970 |
+ | Regeln: F2, F2, F1, P2 | ||
**c)** setSeen(createPost(s, | **c)** setSeen(createPost(s, | ||
Zeile 252: | Zeile 257: | ||
< | < | ||
- | revoke(id_1, | + | revoke(id_1, |
- | revoke(id_1, | + | = publish(P, |
</ | </ | ||
+ | Hinweis: getPost(id_1, | ||
+ | Das bedeutet, dass alle Posts mit ID id_1 gelöscht werden müssen. Hat man einen Post mit gesuchter ID gefunden, darf man nach dessen Löschen nicht aufhören, sondern muss " | ||
**f)** | **f)** | ||
< | < | ||
- | revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F)) | + | markSeen(id_1, publish(P, id_2, F)) = publish(setSeen(P, true), id_2, F) falls id_1 = id_2 |
- | revoke(id_1, publish(P, id_1, F)) = F | + | = publish(P, |
</ | </ | ||
- | < | + | ==== Aufgabe 6 - Graphen ==== |
- | markSeen(id_1, | + | |
- | markSeen(id_1, | + | |
- | </ | + | |
- | + | ||
- | === Aufgabe 6 === | + | |
**a)** | **a)** | ||
Zeile 299: | Zeile 301: | ||
- | === Aufgabe 7 === | + | ==== Aufgabe 7 - wp-Kalkül==== |
+ | |||
+ | Anmerkung: \\ | ||
+ | Eine for-Schleife ist nicht direkt vom wp-Kalkül abgedeckt, lässt sich aber in eine äquivalente while-Schleife umformen: | ||
+ | < | ||
+ | for(int i = 0; i < n; i++) { | ||
+ | // Code | ||
+ | } | ||
+ | </ | ||
+ | entspricht | ||
+ | < | ||
+ | int i = 0; | ||
+ | while(i < n) { | ||
+ | // Code | ||
+ | i++; | ||
+ | } | ||
+ | </ | ||
**a)** | **a)** | ||
Zeile 319: | Zeile 337: | ||
< | < | ||
- | wp("n = a.length; s = 0; i = 0;", s = ∑ |a_j| ∧ i ≤ n) = | + | wp("n = a.length; s = 0; i = 0;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) = |
- | (0 = ∑ |a_j| ∧ 0 ≤ a.length) = | + | (0 = ∑{from 0 to 0 - 1} |a_j| ∧ 0 ≤ a.length) = |
(0 = 0 ∧ 0 ≤ a.length) = | (0 = 0 ∧ 0 ≤ a.length) = | ||
(true) | (true) | ||
Zeile 326: | Zeile 344: | ||
**c)** | **c)** | ||
+ | |||
< | < | ||
- | I∧b --> wp(A,I) | + | Zu zeigen: {I ∧ b} => wp(A, I) |
- | wp(" | + | |
- | --> | + | |
- | a[i] <= 0 ∧ wp("s = s-a[i], s = (Summenzeichen) ∧ i <= n)] | + | |
- | --> | + | wp(A, I) = |
- | kp wie das weiter funktioniert | + | wp("if (a[i] > 0) {s = s + a[i];} else {s = s - a[i]} i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) = |
- | Ende: (ai > 0 ∧ s = (Summenzeichen)|ai| ∧ i + 1 <= n)) (umgedrehtes | + | [(a[i] > 0) ∧ wp("s = s + a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp("s = s - a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] = |
+ | [(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp(s - a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] = | ||
+ | [(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] = | ||
- | I ∧ b => wp(a,I) | + | Überlegung: |
- | s = (Summenzeichen)|aj| ∧ i + 1 <= n ∧ i < n) --> s = (Summenzeichen)|aj| ∧ i + 1 <= n) | + | (a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] positiv, dann wird a[i] auf s addiert |
- | daraus sieht man: A --> A | + | (a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] negativ, dann wird -a[i] auf s addiert, also der Betrag von a[i] |
+ | |||
+ | Man kann somit vereinfachen: | ||
+ | = (s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n) | ||
+ | |||
+ | {I ∧ b} => wp(A, I) | ||
+ | {(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∧ (i < n)} => wp(A, I) = | ||
+ | ¬(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∨ ¬(i < n) ∨ wp(A, I) = | ||
+ | (s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i > n) ∨ (i ≥ n) ∨ wp(A, I) = | ||
+ | (s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ wp(A, I) = | ||
+ | (s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ [(s + |a[i]| = ∑{from 0 to i} |a_j|) | ||
+ | |||
+ | Überlegung: | ||
+ | (i ≥ n) und (i ≤ n - 1) decken für den Integer den Zahlenstrahl ab, das heißt: | ||
+ | Ist (i ≥ n) nicht erfüllt, dann ist (i ≤ n - 1) erfüllt und umgekehrt | ||
+ | |||
+ | (s + |a[i]| = ∑{from 0 to i} |a_j|) = | ||
+ | (s = ∑{from 0 to i} |a_j| - |a[i]|) = | ||
+ | (s = ∑{from 0 to i - 1} |a_j|) | ||
+ | |||
+ | und dies ist das Komplement zu | ||
+ | (s ≠ ∑{from 0 to i - 1} |a_j|) | ||
+ | |||
+ | Somit kann man schlussfolgern, | ||
</ | </ | ||
- | === Aufgabe 8 === | + | |
+ | **d)** | ||
+ | |||
+ | < | ||
+ | V = n - i | ||
+ | |||
+ | i = 0; n = a.length; | ||
+ | i++; in jedem Schleifendurchlauf | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 8 - UML ==== | ||
<code java> | <code java> | ||
- | class Firma{ | + | class Firma { |
- | + | ||
String name; | String name; | ||
Person geschaeftsfuehrer; | Person geschaeftsfuehrer; | ||
Person[] mitarbeiter; | Person[] mitarbeiter; | ||
- | Integer gibAnzahlMitarbeiter() { //Objekt vom Typ Integer, nicht der Datentyp int | + | Integer gibAnzahlMitarbeiter() { // Achtung: |
+ | // ... | ||
} | } | ||
- | |||
} | } | ||
class Person { | class Person { | ||
- | |||
String name; | String name; | ||
Integer gebJahr; | Integer gebJahr; | ||
Zeile 362: | Zeile 412: | ||
Person[] gibAlleUnterstelltenMitarbeiter() { | Person[] gibAlleUnterstelltenMitarbeiter() { | ||
+ | // ... | ||
} | } | ||
- | |||
} | } | ||
</ | </ |