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:loesungss11 [20.03.2018 21:07] – Evren | pruefungen:bachelor:aud:loesungss11 [21.03.2018 10:23] – Evren | ||
---|---|---|---|
Zeile 68: | Zeile 68: | ||
</ | </ | ||
- | **c)** | ||
- | * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein. | ||
- | * Mathematisch: | ||
- | * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y) | ||
- | |||
- | **d)** | ||
- | <code java> | ||
- | void sanitize() { | ||
- | int smallest = getSmallest(); | ||
- | |||
- | // aktueller Knoten der kleinste -> fertig | ||
- | if(data == smallest) | ||
- | return; | ||
- | |||
- | if(left != null && left.data == smallest) { | ||
- | swap(this, | ||
- | left.sanitize(); | ||
- | } else { | ||
- | swap(this, | ||
- | right.sanitize(); | ||
- | } | ||
- | } | ||
- | </ | ||
?? oder vielleicht so: ?? | ?? oder vielleicht so: ?? | ||
\\ | \\ | ||
- | <code java > | + | <code java> |
boolean isSearchTree() { | boolean isSearchTree() { | ||
if (this.left == null && this.right == null) { | if (this.left == null && this.right == null) { | ||
Zeile 117: | Zeile 94: | ||
Zum Testen: https:// | Zum Testen: https:// | ||
+ | |||
+ | |||
+ | **c)** | ||
+ | * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein. | ||
+ | * Mathematisch: | ||
+ | * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y) | ||
+ | |||
+ | **d)** | ||
+ | <code java> | ||
+ | void sanitize() { | ||
+ | int smallest = getSmallest(); | ||
+ | |||
+ | // aktueller Knoten der kleinste -> fertig | ||
+ | if(data == smallest) | ||
+ | return; | ||
+ | |||
+ | if(left != null && left.data == smallest) { | ||
+ | swap(this, | ||
+ | left.sanitize(); | ||
+ | } else { | ||
+ | swap(this, | ||
+ | right.sanitize(); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
**e)** | **e)** | ||
Zeile 222: | Zeile 224: | ||
} | } | ||
} | } | ||
+ | </ | ||
+ | alternativ: | ||
+ | \\ | ||
+ | <code java> | ||
+ | void resize(int h) { | ||
+ | urls.ensureCapacity(h); | ||
+ | ips.ensureCapacity(h); | ||
+ | } | ||
</ | </ | ||
Zeile 272: | Zeile 282: | ||
<code java> | <code java> | ||
- | public static long getPrimeDPHelper(int n, long primes[]) { | + | public static long getPrimeDPHelper(int n, long primes[]) |
- | if(n <= 0) | + | // ArrayIndexOutOfBoundsException detection (falls getPrimeDPHelper(..) falsch aufgerufen wird) |
+ | if (n >= primes.length) { | ||
+ | throw new ArrayIndexOutOfBoundsException(" | ||
+ | } | ||
+ | |||
+ | | ||
return 2; | return 2; | ||
// Geforderte Primzahl wurde noch nicht berechnet | // Geforderte Primzahl wurde noch nicht berechnet | ||
- | if(primes[n] == 0) { | + | if (primes[n] == 0) { |
// Berechne den vorherige Primzahl | // Berechne den vorherige Primzahl | ||
long p = getPrimeDPHelper(n - 1, primes); | long p = getPrimeDPHelper(n - 1, primes); | ||
Zeile 308: | Zeile 323: | ||
| 0 | 11 | 16 | 3 | 7 | 7 | [17] | | | 0 | 11 | 16 | 3 | 7 | 7 | [17] | | ||
| 0 | 11 | 16 | 3 | 7 | 7 | 17 | | | 0 | 11 | 16 | 3 | 7 | 7 | 17 | | ||
+ | |||
+ | alternativ: | ||
+ | |||
+ | ^ Kara ^ A ^ B ^ C ^D ^E ^ Klee ^ | ||
+ | | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ||
+ | | | ∞ | 18< | ||
+ | | | 13< | ||
+ | | | 11< | ||
+ | | | [11< | ||
+ | | | | [16< | ||
+ | | | | | | | | [17< | ||
+ | | | | | | | | | | ||
+ | |||
+ | Indizes rückwärts (von unten nach oben) durchgehen : [17< | ||
+ | |||
+ | => umdrehen: Klara -> C -> E -> A -> Klee | ||
**b)** | **b)** |