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 [07.04.2017 14:49] – vrochri | pruefungen:bachelor:aud:loesungws15 [07.04.2019 13:28] – Nico Hambauer | ||
---|---|---|---|
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 217: | Zeile 218: | ||
sammle(am, | sammle(am, | ||
ergebnis.add(verb); | ergebnis.add(verb); | ||
+ | //einfacher waere hier statt den letzten drei zeilen folgendes: | ||
+ | // | ||
} | } | ||
Zeile 228: | Zeile 231: | ||
for (int j=0; | for (int j=0; | ||
if (am[i][j]){ | if (am[i][j]){ | ||
- | if (vs.contains(i) && vs.contains(j)){ | + | if |
- | // ok | + | |
- | } | + | am[j][i] = false; |
- | else { | + | |
- | am[i][j] = false; | + | |
} | } | ||
} | } | ||
Zeile 269: | Zeile 270: | ||
* path(Node(g, | * path(Node(g, | ||
* path(Edge(g, | * path(Edge(g, | ||
+ | |||
+ | ** c) ** | ||
+ | * isRoot(Edge(g, | ||
+ | false sonst | ||