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 Überarbeitung | ||
pruefungen:bachelor:aud:loesungws15 [07.04.2017 14:49] – vrochri | pruefungen:bachelor:aud:loesungws15 [23.03.2020 10:40] (aktuell) – kat04 | ||
---|---|---|---|
Zeile 9: | Zeile 9: | ||
** b) ** 2 und 3 | ** b) ** 2 und 3 | ||
- | ** c) ** 2 | + | ** c) ** 2 || Ziemlich sicher, dass auch 1 richtig ist. |
* zu 1) (2. Meinung: " | * zu 1) (2. Meinung: " | ||
* zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt. | * zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt. | ||
Zeile 23: | Zeile 23: | ||
* "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": | * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": | ||
- | ** g) ** 2 | + | ** g) ** 2 |
* unsicher | * unsicher | ||
* Ich denke 4 müsste stimmen | * Ich denke 4 müsste stimmen | ||
* Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), | * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), | ||
+ | * Meiner Meinung nach: 3 und 4 sind richtig! Da 1 die definition von gross Omega und 2 von gross Theta ist, wobei die 3 und 4 mit den Rechenregeln des O Kalkuels, bzw 3 bei genauerem Nachdenken ueber den Logarithmus richtig sein muessen. T(n) = T(0.666 * n) = T(c * n) = T(n) + w mit c als Konstante > 1 ist. | ||
==== Aufgabe 2 Streuspeicherung ==== | ==== Aufgabe 2 Streuspeicherung ==== | ||
Zeile 108: | Zeile 109: | ||
<code java> | <code java> | ||
- | void sort(String[] a) { | + | void sortierenDurchEinfuegen(String[] a) { |
- | String | + | String |
- | + | ||
- | for (int n = 1; n < a.length; n++) { | + | for (int n = 1; n < a.length; n++) { |
- | temp | + | tmp = a[n]; // entnommenes Element merken |
- | | + | int i = n - 1; |
- | while (i >= 0 && | + | while (i >= 0 && |
- | a[i + 1] = a[i]; | + | a[i + 1] = a[i]; |
- | i--; | + | i--; |
- | } | + | |
- | + | ||
- | a[i + 1] = temp; // entnommenes Element | + | |
- | // einsetzen | + | |
} | } | ||
+ | |||
+ | a[i + 1] = tmp; // entnommenes Element | ||
+ | // einsetzen | ||
} | } | ||
+ | } | ||
Zeile 157: | Zeile 158: | ||
<code java> | <code java> | ||
long aDP(int n){ | long aDP(int n){ | ||
- | if(mem == null || n >= mem.length){ | + | if(mem == null || n >= mem.length){ |
+ | // Bemerkung: n > mem.length reicht, da mem mit n+1 initialisiert wird | ||
long[] oldMem=mem; | long[] oldMem=mem; | ||
mem=new long[n+1]; | mem=new long[n+1]; | ||
Zeile 184: | Zeile 186: | ||
</ | </ | ||
==== Aufgabe 7 Graphen ==== | ==== Aufgabe 7 Graphen ==== | ||
+ | |||
+ | **a)** | ||
<code java> | <code java> | ||
- | public class GraphWS15 | + | void sammle(boolean[][] am, int k, Set< |
+ | if (!bes.contains(k)) { | ||
+ | verb.add(k); | ||
+ | bes.add(k); | ||
+ | for (int i = 0; i < am[k].length; | ||
+ | if (am[k][i]) { | ||
+ | sammle(am, i, verb, bes); | ||
+ | } | ||
+ | } | ||
- | void sammle(boolean[][] am, int k, Set< | + | |
- | if (!bes.contains(k)) { | + | if (am[i][k]) { |
- | verb.add(k); | + | sammle(am, i, verb, bes); |
- | bes.add(k); | + | } |
- | for (int i = 0; i < am[k].length; i++) { | + | } |
- | if (am[k][i]){ | + | } |
- | sammle(am, i, verb, bes); | + | } |
- | } | + | </ |
- | } | + | |
- | for (int i = 0; i < am.length; i++) { | + | **b)** |
- | if (am[i][k]){ | + | |
- | sammle(am, | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | List< | + | < |
+ | List< | ||
// Ergebnisliste: | // Ergebnisliste: | ||
List< | List< | ||
+ | |||
// Menge besuchter Knoten: | // Menge besuchter Knoten: | ||
Set< | Set< | ||
+ | |||
// Ermittle alle Teilgraphen mittels Hilfsmethode sammle: | // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: | ||
for (int k = 0; k < am.length; k++) { | for (int k = 0; k < am.length; k++) { | ||
- | if (!bk.contains(k)){ | + | if (!bk.contains(k)) { |
// falls k noch nicht besucht => sammle mit k verbundene Knoten | // falls k noch nicht besucht => sammle mit k verbundene Knoten | ||
Set< | Set< | ||
- | sammle(am, | + | sammle(am, |
ergebnis.add(verb); | ergebnis.add(verb); | ||
+ | |||
+ | //einfacher waere hier statt den letzten drei zeilen folgendes: | ||
+ | // | ||
} | } | ||
} | } | ||
- | |||
return ergebnis; | return ergebnis; | ||
} | } | ||
+ | </ | ||
- | void itg(boolean[][] am, Set< | + | **c)** |
- | for (int i=0; | + | |
- | for (int j=0;j<am[i].length; | + | < |
- | if (am[i][j]){ | + | void itg(boolean[][] am, Set< |
- | if (vs.contains(i) | + | for (int i = 0; i < am.length; i++) { |
- | // ok | + | for (int j = 0; j < am.length; j++) { |
- | } | + | if (am[i][j]) { |
- | else { | + | if (!vs.contains(i) |
- | am[i][j] = false; | + | |
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | // alte Loesung: | ||
+ | void itg(boolean[][] am, Set< | ||
+ | for (int i = 0; i < am.length; i++) { | ||
+ | for (int j = 0; j < am.length; j++) { | ||
+ | if (am[i][j]) { | ||
+ | if (!(vs.contains(i) && vs.contains(j))) | ||
+ | | ||
+ | am[j][i] = false; | ||
} | } | ||
} | } | ||
- | } | + | } |
- | + | ||
} | } | ||
- | } | + | } |
- | + | </ | |
- | public static void main(String[] args){ | + | |
+ | Code zum selber testen: | ||
+ | < | ||
+ | public static void main(String[] args){ | ||
// | // | ||
GraphWS15 g = new GraphWS15(); | GraphWS15 g = new GraphWS15(); | ||
Zeile 269: | Zeile 297: | ||
* path(Node(g, | * path(Node(g, | ||
* path(Edge(g, | * path(Edge(g, | ||
+ | |||
+ | ** c) ** | ||
+ | * isRoot(Edge(g, | ||
+ | false sonst | ||