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 ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss15 [29.03.2016 12:36] – MergeSort & isDAG aus Forumsbeitrag hinzugefügt Marcel[Inf] | pruefungen:bachelor:aud:loesungss15 [26.07.2017 13:17] – Verbesserung 1c ab21ajus | ||
---|---|---|---|
Zeile 2: | Zeile 2: | ||
* [[https:// | * [[https:// | ||
- | * [[https:// | + | * [[https:// |
- | * [[https:// | + | * [[https:// |
- | * [[https:// | + | * [[https:// |
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
Zeile 11: | Zeile 11: | ||
* a) 1 und 4 | * a) 1 und 4 | ||
* b) 1 und 2 | * b) 1 und 2 | ||
- | * c) 2 und 3 | + | * c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit* |
- | * d) 1 und 4 (unsicher!). | + | * Erneuter Edit von jemand anderem: 4 ist nicht richtig, der Laufzeitaufwand bei Prim ist O(n*log n + e). Ausserdem ist 3 sehr wohl richtig: Das steht exakt so in der Vorlesung, Kruskal hat O(e*log e). |
+ | |||
+ | * d) 1 und 4 (zu 2: Interfaces weder implementieren noch erben von Object => siehe JLS: http:// | ||
* e) 3 und 4 | * e) 3 und 4 | ||
* f) 1 | * f) 1 | ||
- | * g) 2und 3 | + | * g) 2 und 3 |
* h) 1 und 4 | * h) 1 und 4 | ||
==== Aufgabe 2 - Bäume (9) ==== | ==== Aufgabe 2 - Bäume (9) ==== | ||
+ | |||
+ | [[https:// | ||
==== Aufgabe 3 - Graphen (18) ==== | ==== Aufgabe 3 - Graphen (18) ==== | ||
+ | a) Endergebnis: | ||
+ | |||
b) A-> | b) A-> | ||
Zeile 45: | Zeile 51: | ||
==== Aufgabe 4 - Rekursion (11) ==== | ==== Aufgabe 4 - Rekursion (11) ==== | ||
+ | |||
+ | Live auf ideone.com mit AuD-Beispiel: | ||
+ | |||
+ | <code java> | ||
+ | // Rückgabe pms ist Potenzmenge von s ab index idx | ||
+ | List< | ||
+ | if (idx >= s.length) { | ||
+ | // Basisfall | ||
+ | pms.add(new ArrayList< | ||
+ | } else { | ||
+ | // aktuelles Kopfelement bestimmen | ||
+ | T kopf = s[idx]; | ||
+ | |||
+ | // Potenzmenge der Restliste bestimmen | ||
+ | List< | ||
+ | |||
+ | // Ergebnisse zusammenführen | ||
+ | for (List< | ||
+ | List< | ||
+ | mitKopf.add(kopf); | ||
+ | |||
+ | pms.add(ohneKopf); | ||
+ | pms.add(mitKopf); | ||
+ | } | ||
+ | } | ||
+ | return pms; | ||
+ | }</ | ||
==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ==== | ==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ==== | ||
<code java> | <code java> | ||
Zeile 64: | Zeile 97: | ||
return true; | return true; | ||
}</ | }</ | ||
- | ==== Aufgabe 6 - Dynamische Programmierung (17) ==== | + | ==== Aufgabe 6 - Dynamische Programmierung (17) ==== |
+ | a) Verschachtelte Rekursion | ||
+ | |||
+ | b, c) | ||
+ | <code java> | ||
+ | class DynProg { | ||
+ | |||
+ | private int[] dp; | ||
+ | |||
+ | public DynProg(int max) { | ||
+ | dp = new int[max]; | ||
+ | } | ||
+ | |||
+ | int fDP(int n) { // Dynamische Programmierung | ||
+ | int fn = 1; // Basisfall n < 3 trivial | ||
+ | |||
+ | // fn schon einmal berechnet? | ||
+ | if (n <= dp.length && dp[n-1] != 0) { | ||
+ | fn = dp[n-1]; | ||
+ | } else if (n >= 3) { // fn muss noch berechnet werden | ||
+ | if (n <= dp.length) { | ||
+ | fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1; | ||
+ | dp[n-1] = fn; | ||
+ | } else { | ||
+ | fn = f(n); | ||
+ | } | ||
+ | } | ||
+ | return fn; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | d) | ||
+ | |||
+ | Hier sind viele Varianten denkbar. | ||
+ | <code java> | ||
+ | public static int fIter(int n) { // Iterativ | ||
+ | int k = 1; // Zähler | ||
+ | int fk = 1; | ||
+ | |||
+ | int z = 2; | ||
+ | for (; k<=n; k++) { | ||
+ | if (z == 0) { | ||
+ | fk++; | ||
+ | z = 2 * fk - 1; | ||
+ | } | ||
+ | else { | ||
+ | z--; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return fk; | ||
+ | } | ||
+ | </ | ||
==== Aufgabe 7 - Sortieren (16) ==== | ==== Aufgabe 7 - Sortieren (16) ==== | ||
Mit System.out.println() Aufrufen zum Testen: | Mit System.out.println() Aufrufen zum Testen: |