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:loesungws15 [05.04.2017 17:11] – uv35imat | pruefungen:bachelor:aud:loesungws15 [24.07.2019 16:09] – Korrektur Aufgabe 7c) + Formatierung angepasst dom | ||
---|---|---|---|
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: "(stimmt hier nicht auch 1?)") => wenn man bei der linearen Suche ("< oder " |
- | * Denke ich nicht | + | * 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 3) unsicher, ob das hier eine Rolle spielt | ||
+ | * zu 4) scheidet aus, weil 2 richtig ist | ||
** d) ** 3 | ** d) ** 3 | ||
Zeile 21: | 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 | ||
+ | * 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 40: | Zeile 45: | ||
* C 3 (P)-> 4 | * C 3 (P)-> 4 | ||
* D 3 (P)-> 4 (S)-> 0 | * D 3 (P)-> 4 (S)-> 0 | ||
- | * E 0 (P)-> 1 (S)-> 4 (S)-> 2 | + | * E 0 (S)-> 1 (P)-> 4 (S)-> 2 |
==== Aufgabe 3 Binäre Suche ==== | ==== Aufgabe 3 Binäre Suche ==== | ||
Zeile 104: | 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 140: | Zeile 145: | ||
long an = a(n-1); | long an = a(n-1); | ||
for(int i = 1; i < n; i++){ | for(int i = 1; i < n; i++){ | ||
- | an+= a(i)*a(i-1); | + | an+= a(i)*a(n-i); |
} | } | ||
return an; | return an; | ||
Zeile 180: | Zeile 185: | ||
</ | </ | ||
==== 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; | + | |
- | } | + | |
} | } | ||
} | } | ||
- | + | } | |
- | } | + | |
} | } | ||
- | + | } | |
- | public static void main(String[] args){ | + | |
+ | // 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[i][j] = false; | ||
+ | am[j][i] = false; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Code zum selber testen: | ||
+ | < | ||
+ | public static void main(String[] args){ | ||
// | // | ||
GraphWS15 g = new GraphWS15(); | GraphWS15 g = new GraphWS15(); | ||
Zeile 257: | Zeile 288: | ||
==== Aufgabe 8 ADT ==== | ==== Aufgabe 8 ADT ==== | ||
< | < | ||
+ | |||
+ | ** a) ** | ||
+ | * collect(Node(g, | ||
+ | * collect(Edge(g, | ||
+ | |||
+ | ** b) ** | ||
+ | * path(Node(g, | ||
+ | * path(Edge(g, | ||
+ | |||
+ | ** c) ** | ||
+ | * isRoot(Edge(g, | ||
+ | false sonst | ||
+ |