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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws11 [27.03.2016 15:37] – Marcel[Inf] | pruefungen:bachelor:aud:loesungws11 [24.01.2019 21:56] (aktuell) – LasagneAlForno | ||
---|---|---|---|
Zeile 12: | Zeile 12: | ||
**c)** 2. Antwort ist richtig: Preorder. Postorder müsste auch stimmen, denn die Reihenfolge, | **c)** 2. Antwort ist richtig: Preorder. Postorder müsste auch stimmen, denn die Reihenfolge, | ||
+ | \\ | ||
+ | Doch die Reihenfolge ist festgelegt: L-R-N (Links, Rechts, Mitte), siehe [[https:// | ||
**d)** Richtig | **d)** Richtig | ||
Zeile 39: | Zeile 41: | ||
==Adjazenzmatrix== | ==Adjazenzmatrix== | ||
^ ^ S ^ A ^ B ^ C ^ D ^ E ^ | ^ ^ S ^ A ^ B ^ C ^ D ^ E ^ | ||
- | ^ S | - | + | + | - | - | - | | + | ^ S | 0 | 1 | 1 | 0 | 0 | 0 | |
- | ^ A | - | - | - | + | + | - | | + | ^ A | 0 | 0 | 0 | 1 | 1 | 0 | |
- | ^ B | - | - | - | - | + | - | | + | ^ B | 0 | 0 | 0 | 0 | 1 | 0 | |
- | ^ C | - | - | - | - | - | + | | + | ^ C | 0 | 0 | 0 | 0 | 0 | 1 | |
- | ^ D | - | - | - | + | - | + | | + | ^ D | 0 | 0 | 0 | 1 | 0 | 1 | |
- | ^ E | - | - | - | - | - | - | | + | ^ E | 0 | 0 | 0 | 0 | 0 | 0 | |
==Graphische Darstellung== | ==Graphische Darstellung== | ||
Zeile 50: | Zeile 52: | ||
{{: | {{: | ||
- | ==Als Reihung== | + | ==Als Reihung |
- | ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^ | + | | | | | | | | | S | S | A | A | B | C | D | D | |
- | | 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 | | + | | | S | A | B | C | D | E | A | B | C | D | D | E | C | E | |
+ | | Array-Indizes: | ||
+ | | Array-Werte: | ||
**b)** | **b)** | ||
Zeile 142: | Zeile 146: | ||
<code java> | <code java> | ||
- | private void versickern(Knoten k) { | + | private |
- | Knoten groesser = null; | + | Knoten groesser = null; |
- | if(links != null && rechts != null) { | + | if (k.links != null && |
- | groesser = (links.wert > rechts.wert) | + | 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; |
+ | } | ||
- | vertausche(k, | + | vertausche(k, |
- | versickern(groesser); | + | versickern(groesser); |
- | } | + | |
+ | } | ||
</ | </ | ||
**b)** | **b)** | ||
+ | Nach dem Postorder-Prinzip: | ||
<code java> | <code java> | ||
- | private void erzeugeHalde(Knoten k) { | + | private |
- | if(k.left != null) | + | if (k.links != null) |
- | erzeugeHalde(k.left); | + | erzeugeHalde(k.links); |
- | if(k.right != null) | + | if (k.rechts |
- | erzeugeHalde(k.right); | + | erzeugeHalde(k.rechts); |
- | versickern(k); | + | versickern(k); |
- | } | + | } |
</ | </ | ||
**c)** | **c)** | ||
<code java> | <code java> | ||
- | public Knoten inListeSortieren() { | + | public |
- | // 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; | ||
- | } | ||
</ | </ | ||
Zeile 239: | Zeile 251: | ||
< | < | ||
OPS: | OPS: | ||
- | meth: Tabelle x String -> | + | filter: Tabelle x String -> |
AXS: | AXS: | ||
Zeile 426: | Zeile 438: | ||
q.e.d. | q.e.d. | ||
+ | |||
+ | oder | ||
+ | |||
+ | {{: |