Aufgabenblock — AFB III
Begründen statt nur nachverfolgen: Strukturen vergleichen, Aussagen allgemein beweisen und eigene Verfahren entwickeln — erst selbst formulieren, dann die Musterlösung aufklappen.
Entwickle eine Idee, wie man mit zwei Stapeln ein und aus eine Schlange nachbauen kann, und beurteile den Aufwand von enqueue und dequeue.
Hinweis: Ein Stapel dreht die Reihenfolge um — zweimal umdrehen ergibt die ursprüngliche Reihenfolge.
ein. Woher nimmt dequeue das älteste Element?aus leer ist, wird ein vollständig nach aus umgeladen.Musterlösung anzeigen (zählt als erledigt)
Musterlösung: enqueue(x) ist ein ein.push(x). Für dequeue wird, falls aus leer ist, der ganze Stapel ein Element für Element auf aus umgeladen; dadurch liegt das älteste Element oben, und aus.pop() liefert es. Ist aus nicht leer, genügt direkt aus.pop(). Einzelne dequeue-Aufrufe können teuer sein (alles umladen), aber jedes Element wird insgesamt nur einmal umgeladen — im Mittel ist der Aufwand pro Operation konstant.
Beurteile, ob beim Nachbau eines Stapels mit einer dynamischen Reihung das oberste Element am Anfang (Index 0) oder am Ende liegen sollte.
Hinweis: Beide Varianten funktionieren — es geht um den Aufwand.
insertAt(0, x) bzw. delete(0) nach?Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Liegt das oberste Element am Ende, entsprechen push und pop den Operationen append und delete(getLength() - 1); kein Element rückt nach. Liegt es an Index 0, verschiebt jedes push und pop alle übrigen Elemente. Beide Varianten sind korrekt, „oben = Ende“ ist deutlich effizienter.
Begründe allgemein, dass jeder nicht leere Binärbaum mit n Knoten genau n + 1 leere Teilbäume hat.
Hinweis: Zähle Plätze für Teilbäume und wer sie belegt.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Jeder der n Knoten hat zwei Plätze für Teilbäume, zusammen 2n. Jeder Knoten außer der Wurzel ist Kind genau eines Knotens und belegt genau einen Platz: n − 1 Plätze sind besetzt. Auf allen übrigen Plätzen sitzt ein leerer Baum: 2n − (n − 1) = n + 1. Deshalb ruft eine rekursive Traversierung sich 2n + 1-mal auf.