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.
Eine Arztpraxis verwaltet ihre Warteliste als Stapel. Beurteile diese Entscheidung.
Hinweis: Wer wird bei einem Stapel als Nächstes aufgerufen?
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Bei einem Stapel würde immer die zuletzt angekommene Person zuerst aufgerufen (LIFO). Wer früh gekommen ist, könnte beliebig lange warten, solange neue Patienten eintreffen — das widerspricht dem Gerechtigkeitsempfinden und der Praxisordnung. Geeignet ist eine Schlange: Wer zuerst kommt, wird zuerst aufgerufen (FIFO). Die Entscheidung ist daher abzulehnen.
Zeige, dass eine Schlange mit n Elementen nach genau n Rotationen q.enqueue(q.dequeue()) wieder genauso aussieht wie vorher.
Hinweis: Verfolge, wohin das vorderste Element nach einer Rotation wandert.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Eine Rotation entnimmt das vorderste Element und stellt es hinten an; alle anderen rücken eine Position nach vorn, die Reihenfolge bleibt zyklisch erhalten. Nach k Rotationen steht das Element, das anfangs an Position k stand, vorn. Nach n Rotationen hat jedes Element genau einmal den Weg nach hinten gemacht, und das ursprünglich vorderste steht wieder vorn — die Schlange ist unverändert.
Erkläre, warum while (!q.isEmpty()) { x = q.dequeue(); q.enqueue(x); } nicht terminiert, sobald q ein Element enthält.
Hinweis: Wie verändert ein Durchlauf die Länge der Schlange?
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: In jedem Durchlauf wird ein Element entnommen und sofort wieder angestellt; die Länge der Schlange bleibt gleich. Ist sie zu Beginn nicht leer, bleibt sie es für immer, und die Bedingung !q.isEmpty() ist stets wahr. Deshalb muss die Anzahl der Durchläufe vorher feststehen.
Begründe, warum man bei der Maximumsuche mit getItem(0) und nicht mit 0 startet.
Hinweis: Denke an eine Reihung mit ausschließlich negativen Werten.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Startet man mit 0, ist bei einer Reihung wie [−5, −2, −9] kein Element größer als 0; der Algorithmus liefert 0, obwohl dieser Wert gar nicht vorkommt. Mit getItem(0) ist der Startwert immer ein echtes Element; danach kann das Maximum nur durch vorhandene Werte ersetzt werden. (Voraussetzung: Die Reihung ist nicht leer.)
Vergleiche das Umladen in eine Hilfsstruktur und das Zurückladen bei Stapel und Schlange hinsichtlich der Reihenfolge.
Hinweis: Was passiert beim einmaligen Umladen, was beim zweiten?
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Beim Stapel kehrt jedes Umladen die Reihenfolge um: Im Hilfsstapel liegt das frühere unterste Element oben. Das Zurückladen dreht sie ein zweites Mal um, sodass der Originalzustand entsteht. Bei der Schlange bleibt die Reihenfolge bei jedem Umladen erhalten. In beiden Fällen ist die Struktur nach Umladen und Zurückladen unverändert — aus unterschiedlichen Gründen.
Entwickle eine Idee, wie man mit zwei Stapeln A und B eine Schlange nachbauen kann.
Hinweis: enqueue ist einfach. Beim dequeue muss das unterste Element von A nach oben.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: enqueue(x): x auf Stapel A legen. dequeue(): Ist B leer, werden alle Elemente von A nach B umgeladen — dadurch liegt das älteste Element oben auf B. Dann liefert B.pop() das vorderste Element der Schlange. Ist B nicht leer, wird direkt B.pop() aufgerufen. Die Schlange ist leer, wenn beide Stapel leer sind. So gilt insgesamt FIFO, obwohl beide Bausteine LIFO arbeiten.
Ein Betriebssystem stellt die Zeitscheibe beim Rundlauf auf 1 Takt. Beurteile diese Einstellung.
Hinweis: Bedenke: Jeder Wechsel kostet selbst Verwaltungszeit.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Vorteil: Jedes Programm kommt sehr schnell an die Reihe; interaktive Programme reagieren flüssig, kurze Programme werden nicht von langen blockiert. Nachteil: Nach jedem Takt wird gewechselt und wieder angestellt; in der Realität kostet jeder Wechsel Zeit, sodass ein großer Teil der Rechenzeit für Verwaltung verloren geht. Sinnvoll ist ein Mittelweg — so klein, dass alles flüssig wirkt, so groß, dass die Wechsel kaum ins Gewicht fallen.