Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Both sides previous revision Vorhergehende Überarbeitung
pruefungen:bachelor:aud:loesungss14 [31.07.2019 11:30]
dom Anpassungen Aufgabe 4
pruefungen:bachelor:aud:loesungss14 [31.07.2019 11:54] (aktuell)
dom Verbesserung Aufgabe 5c,d
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>
-       //​vorsicht! hier sind nicht alle faelle abgedeckt! was passiert bei rightId > w.length - 1 ? ggf mit Vorlesungsfolie 13 S.39 von ws18/19 gegenchecken!!! +void reheap(W[] w, Comparator<​W>​ c, int i, int k) { 
- void reheap(W[] w, Comparator<​W>​ c, int i, int k) { +    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 (leftId <= k && rightId > k) { 
- if(rightId > k || c.compare(w[leftId],​ w[rightId]) > 0) { +        if (c.compare(w[leftId],​ w[i]) > 0) { // Falls Kind groesser, dann tauschen 
- kidId = leftId; +            ​swap(w, ​leftId, i)
- } else { +        } 
- kidId = rightId; +    ​} else { 
- } +        // 2 Kinder vorhanden, pruefen, ob rechtes Kind innerhalb des Arrays liegt 
- if(c.compare(w[kidId],​ w[i]) > 0) { +        if (rightId <= k) { 
- swap(w, i, kidId); +            // groesseres der beiden Kinder in kidId speichern 
- reheap(w, c, kidId, k); +            ​kidId = c.compare(w[leftId],​ w[rightId]) > 0 ? leftId : rightId; 
- + 
- +            // Schauen, ob Kind groesser ist, als aktuelles Element, falls ja, dann tauschen 
- }+            ​if (c.compare(w[kidId],​ w[i]) > 0) { 
 +                swap(w, kidId, i); 
 +                reheap(w, c, kidId, k); 
 +            } 
 +        ​
 +    
 +}
 </​code>​ </​code>​
 \\ \\
 d) d)
- void heapSort(W[] w, Comparator<​W>​ c) { +<​code=java>​ 
- int n = w.length; +void heapSort(W[] w, Comparator<​W>​ c) { 
-  +    int n = w.length;
- // Phase 1: Max-Heap-Eigenschaft herstellen +
- //          (siehe Teilaufgabe a) +
- for(int i = n / 2 - 1; i >= 0; i--) { +
- reheap(w,​ c, i, n-1); // Beide Grenzen inklusiv +
-+
-  +
- // 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,​ c, 0, i - 1); +
-+
- }+
         ​         ​
 +    // 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);
 +    }
 +
 +</​code>​
 +
 ====   6) Bäume und Rekursion==== ​   ====   6) Bäume und Rekursion==== ​  
 <code java>  <code java>