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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws10 [17.02.2013 21:30] – Dawodopruefungen:bachelor:aud:loesungws10 [30.07.2013 11:11] – Dawodo
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: Die Variable k in Funktion f muss mit 1 initialisiert sein, dem neutralen Element der Multiplikation.
  
 **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 142: Zeile 143:
 **a)** 96 oder kleiner **a)** 96 oder kleiner
  
-**b)** +**b)** 2. Antwort ist richtig: Von Hinten nach Vorne
-  * von Vorne nach Hinten: Falsch +
-  * von Hinten nach Vorne: Richtig+
  
 **c)** **c)**
Zeile 241: Zeile 240:
 ==== Aufgabe 5 - ADT ==== ==== 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, d, b), v) = createPost(s, d, v) **c)** setSeen(createPost(s, d, b), v) = createPost(s, d, v)
Zeile 252: Zeile 253:
  
 <code> <code>
-revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F)) +revoke(id_1, publish(P, id_2, F)) = revoke(id_1, F) falls id_1 = id_2 
-revoke(id_1, publish(P, id_1, F)) = F+ = publish(P, id_2, revoke(id_1, F)) sonst
 </code> </code>
 +Hinweis: getPost(id_1, revoke(id_1, F)) muss noPost liefern. \\
 +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 "weitersuchen".
  
 **f)**  **f)** 
  
 <code> <code>
-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, id_2, markSeen(id_1, F)) sonst
-</code> +
- +
-<code> +
-markSeen(id_1, publish(P, id_2, F)) = publish(P, id_2, markSeen(id_1, F)) +
-markSeen(id_1, publish(P, id_1, F)) = publish(setSeen(P, true), id_1, F)+
 </code> </code>
  
Zeile 300: Zeile 298:
  
 ==== Aufgabe 7 - wp-Kalkül==== ==== 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:
 +<code>
 +for(int i = 0; i < n; i++) {
 + // Code
 +}
 +</code>
 +entspricht
 +<code>
 +int i = 0;
 +while(i < n) {
 + // Code
 + i++;
 +}
 +</code>
  
 **a)** **a)**
Zeile 331: Zeile 345:
  
 wp(A, I) = wp(A, I) =
-wp("if (a[i] > 0) {s = s + a[i];} else {s = s - a[i]}", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =+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) =
 [(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) ∧ 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 + 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)] =
Zeile 366: Zeile 380:
 **d)** **d)**
  
-(unsicher) 
 <code> <code>
 V = n - i V = n - i