Aufgabenblock — AFB III
Begründen statt nur nachverfolgen: Algorithmen beurteilen, Strukturen vergleichen und eigene Ideen entwickeln — erst selbst formulieren, dann die Musterlösung aufklappen.
Begründe, warum eine Schleife von getLength() - 1 abwärts beim Löschen kein Element überspringt.
Hinweis: Überlege, welche Elemente nach einem delete(i) ihre Position ändern.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Nach delete(i) rücken nur die Elemente hinter Index i nach vorn. Bei einer Rückwärts-Schleife sind genau diese schon geprüft. Die noch ungeprüften Elemente mit kleinerem Index behalten ihre Position, und i wird als Nächstes um 1 verringert — so wird jedes Element genau einmal geprüft.
Begründe mit einem Gegenbeispiel, warum man die Korrektheit eines Klammerausdrucks nicht durch Zählen der Klammern prüfen kann.
Hinweis: Suche einen falschen Ausdruck mit gleich vielen öffnenden wie schließenden Klammern.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Beim Ausdruck )( gibt es je eine öffnende und eine schließende Klammer, trotzdem wird eine Klammer geschlossen, bevor sie geöffnet wurde. Bei ([)] stimmen die Anzahlen jeder Art, aber die zuletzt geöffnete eckige Klammer wird nach der runden geschlossen. Zählen erfasst weder Reihenfolge noch Verschachtelung; der Stapel merkt sich, welche Klammer als Nächstes geschlossen werden muss.
Ein Stapel soll mit einer dynamischen Reihung nachgebaut werden. Beurteile, ob das oberste Element am Anfang (Index 0) oder am Ende der Reihung liegen sollte.
Hinweis: Beide Varianten funktionieren — es geht um den Aufwand.
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); dabei rückt kein Element nach. Liegt es an Index 0, verschiebt jedes insertAt(0, x) und jedes delete(0) alle übrigen Elemente. Beide Varianten sind korrekt, die Variante „oben = Ende“ ist aber deutlich effizienter und deshalb vorzuziehen.