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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:30] – Anpassungen Aufgabe 4 dompruefungen: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>
-       //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>