Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | |||
pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:30] – Anpassungen Aufgabe 4 dom | pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:54] (aktuell) – Verbesserung Aufgabe 5c,d dom | ||
---|---|---|---|
Zeile 240: | Zeile 240: | ||
\\ | \\ | ||
- | a) Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden. | + | a) |
+ | |||
+ | Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden. | ||
=> Kreuz bei Stelle 2, 5 und 6 | => Kreuz bei Stelle 2, 5 und 6 | ||
=> Resultat: { 6, 7, 5, 3, 1, 0, 2 } | => Resultat: { 6, 7, 5, 3, 1, 0, 2 } | ||
\\ | \\ | ||
- | b) Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\ | + | b) |
+ | |||
+ | Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\ | ||
\\ | \\ | ||
c) | c) | ||
<code java> | <code java> | ||
- | // | + | void reheap(W[] w, Comparator< |
- | void reheap(W[] w, Comparator< | + | int leftId = 2 * i + 1; |
- | int leftId = 2 * i + 1; | + | int rightId = leftId + 1; |
- | int rightId = leftId + 1; | + | int kidId; |
- | int kidId; | + | |
- | + | // nur 1 Kind (linkes) vorhanden; pruefen, ob Indizes innerhalb des Arrays liegen | |
- | if(leftId <= k) { | + | |
- | if(rightId > k || c.compare(w[leftId], | + | if (c.compare(w[leftId], |
- | kidId = leftId; | + | |
- | } else { | + | } |
- | kidId = rightId; | + | |
- | } | + | // 2 Kinder vorhanden, pruefen, ob rechtes Kind innerhalb des Arrays liegt |
- | if(c.compare(w[kidId], | + | if (rightId <= k) { |
- | swap(w, i, kidId); | + | // groesseres der beiden Kinder in kidId speichern |
- | reheap(w, c, kidId, k); | + | |
- | } | + | |
- | } | + | // Schauen, ob Kind groesser ist, als aktuelles Element, falls ja, dann tauschen |
- | } | + | |
+ | swap(w, kidId, i); | ||
+ | reheap(w, c, kidId, k); | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | } | ||
</ | </ | ||
\\ | \\ | ||
d) | d) | ||
- | void heapSort(W[] w, Comparator< | + | < |
- | int n = w.length; | + | void heapSort(W[] w, Comparator< |
- | + | int n = w.length; | |
- | // Phase 1: Max-Heap-Eigenschaft herstellen | + | |
- | // (siehe Teilaufgabe a) | + | |
- | for(int i = n / 2 - 1; i >= 0; i--) { | + | |
- | reheap(w, | + | |
- | } | + | |
- | + | ||
- | // Phase 2: jeweils Maximum entnehmen und sortierte Liste am Ende aufbauen | + | |
- | // (siehe Teilaufgabe b) | + | |
- | for(int i = n - 1; i > 0; i--) { | + | |
- | swap(w, 0, i); | + | |
- | reheap(w, | + | |
- | } | + | |
- | } | + | |
| | ||
+ | // Phase 1: Halde aufbauen | ||
+ | for (int i = n / 2; i >= 0; i--) { | ||
+ | reheap(w, c, i, n - 1); | ||
+ | } | ||
+ | |||
+ | // Phase 2: Maximum entnehmen und sortierte Liste am Ende aufbauen | ||
+ | for (int i = n - 1; i > 0; i--) { | ||
+ | // Maximum an das Ende der Halde tauschen | ||
+ | swap(w, 0, i); | ||
+ | |||
+ | // Nach vorne getauschtes Element einsickern lassen und Haldeneigenschaft wiederherstellen | ||
+ | reheap(w, c, 0, i - 1); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
==== 6) Bäume und Rekursion==== | ==== 6) Bäume und Rekursion==== | ||
<code java> | <code java> |