Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungws11 [16.03.2018 20:26] – Evrenpruefungen:bachelor:aud:loesungws11 [24.01.2019 21:56] (aktuell) – LasagneAlForno
Zeile 53: Zeile 53:
  
 ==Als Reihung (eingebettet in Array; auch Adjazenzfeld genannt)== ==Als Reihung (eingebettet in Array; auch Adjazenzfeld genannt)==
-| Bezeichnungen: | S | A | B | C | D | E | S->A | S->B | A->C | A->D | B->D | C->E | D->C | D->E |+| | | | | | | | S | S | A | A | B | C | D | D | 
 +| | S | A | B | C | D | E | A | B | C | D | D | E | C | E |
 | Array-Indizes: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |  | Array-Indizes: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 
 | Array-Werte: ^ 6 ^ 8 ^ 10 ^ 11 ^ 12 ^ 14 ^ 1 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5 ^ 3 ^ 5 ^ | Array-Werte: ^ 6 ^ 8 ^ 10 ^ 11 ^ 12 ^ 14 ^ 1 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5 ^ 3 ^ 5 ^
Zeile 145: Zeile 146:
  
 <code java> <code java>
-private void versickern(Knoten k) { +private static void versickern(Knoten k) { 
- Knoten groesser = null;+ Knoten groesser = null;
  
- if(links != null && rechts != null) { + if (k.links != null && k.rechts != null) { 
- groesser = (links.wert > rechts.wert) ? links : rechts;+ if (k.links.wert > k.rechts.wert) { 
 + groesser = k.links; 
 + } else { 
 + groesser = k.rechts; 
 + }
  
- } else if(links != null) { + } else if (k.links != null) { // hier ist es wichtig, ein "else if" statt einem if zu verwenden! 
- groesser = links;+ groesser = k.links;
  
- } else if(rechts != null) { + } else if (k.rechts != null) { 
- groesser = rechts; + groesser = k.rechts; 
- }+ }
  
- if(groesser == null) { + if (groesser == null) { 
- return; + return; 
- }+ }
  
- if(k.wert > groesser.wert) + if (k.wert > groesser.wert) { 
- return;+ return; // fertig :) 
 + }
  
- vertausche(k, groesser);         + vertausche(k, groesser); 
- versickern(groesser); + versickern(groesser); // normalerweise würde man versickern(k) rekursiv aufrufen, aber die vertausche-Methode tauscht laut Aufgabenstellung nicht die Knoten, sondern nur deren Werte! 
-}+ 
 + }
 </code> </code>
 **b)** **b)**
 Nach dem Postorder-Prinzip: Nach dem Postorder-Prinzip:
 <code java> <code java>
-private void erzeugeHalde(Knoten k) { +private static void erzeugeHalde(Knoten k) { 
- if(k.left != null) + if (k.links != null) 
- erzeugeHalde(k.left);+ erzeugeHalde(k.links);
  
- if(k.right != null) + if (k.rechts != null) 
- erzeugeHalde(k.right);+ erzeugeHalde(k.rechts);
  
- versickern(k); + versickern(k); 
-} +}
 </code> </code>
 **c)** **c)**
 <code java> <code java>
-public Knoten inListeSortieren() { + public static Knoten inListeSortieren() { 
- // Kann leere Halde nicht sortieren + // Kann leere Halde nicht sortieren 
- if (wurzel == null) + if (wurzel == null) { 
- return null;+ return null; 
 + } 
 +  
 + // Max-Heap-Eigenschaft herstellen 
 + erzeugeHalde(wurzel);
  
- // Max-Heap-Eigenschaft herstellen + // Wurzel entnehmen und zum Kopf unserer Liste machen 
- erzeugeHalde(wurzel);+ Knoten kopf = entferneMax(); 
 + Knoten schlepp = kopf;
  
- // Wurzel entnehmen und zum Kopf unserer Liste machen + // Wiederholt Wurzel entnehmen und an Liste anhängen 
- Knoten kopf = entferneMax(); + while (wurzel != null) { 
- Knoten schlepp = kopf; + schlepp.rechts = entferneMax(); 
- + schlepp = schlepp.rechts; 
- // Wiederholt Wurzel entnehmen und an Liste anhängen + } 
- while(wurzel != null) { +  
- schlepp.rechts = entferneMax(); + // Kopf unserer Liste zurückgeben 
- schlepp = schlepp.rechts;+ return kopf;
  }  }
- 
- // Kopf unserer Liste zurückgeben 
- return kopf; 
-} 
 </code> </code>
  
Zeile 430: Zeile 438:
  
 q.e.d. q.e.d.
 +
 +oder
 +
 +{{:pruefungen:bachelor:aud:induction-1.png?400|}}