MINT lernen

Abituraufgaben: Datenstrukturen im Abitur

Stapel und Schlangen in zwei Anwendungen — mit Struktogramm und Ablaufdarstellung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Browser-Verlauf

AFB I–II

Ein Browser speichert besuchte Seiten, damit man mit „Zurück“ zur vorigen Seite gelangt. Dafür nutzt er einen Stapel verlauf vom Inhaltstyp Zeichenkette. Die aktuell angezeigte Seite steht in aktuell.

Beim Öffnen einer neuen Seite wird aktuell auf den Stapel gelegt und die neue Seite wird aktuell. Bei „Zurück“ wird die oberste Seite vom Stapel die aktuelle Seite.

  1. Wenden Sie die Vorgänge an: Start auf „start.de“, dann öffnen „a.de“, öffnen „b.de“, Zurück, öffnen „c.de“, Zurück, Zurück. Geben Sie nach jedem Schritt aktuell und den Stapel an.
  2. Begründen Sie, warum ein Stapel für die Zurück-Funktion geeignet ist.
  3. Entwerfen Sie ein Struktogramm für zurueck(). Ist der Stapel leer, bleibt die aktuelle Seite erhalten.

Hinweise

Hinweis zu Aufgabe a)
Stapel als Liste von unten nach oben notieren.
Hinweis zu Aufgabe b)
Welche Seite will man bei „Zurück“ sehen — die zuletzt oder die zuerst besuchte?
Hinweis zu Aufgabe c)
isEmpty() vor pop() abfragen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
Schrittaktuellverlauf (unten → oben)
Startstart.deleer
öffnen a.dea.destart.de
öffnen b.deb.destart.de, a.de
Zurücka.destart.de
öffnen c.dec.destart.de, a.de
Zurücka.destart.de
Zurückstart.deleer
Erwartungshorizont zu Aufgabe b)

„Zurück“ führt immer zur zuletzt besuchten Seite. Das entspricht dem LIFO-Prinzip: Die zuletzt abgelegte Seite wird zuerst entnommen. Zugriff auf andere Positionen ist nicht nötig.

Erwartungshorizont zu Aufgabe c)
2

Einlass beim Schulkonzert

AFB II–III

Beim Schulkonzert stehen Gäste in einer Schlange q vom Inhaltstyp Gast. Die Klasse Gast bietet istVIP(): Wahrheitswert. VIP-Gäste sollen vorgezogen werden, ohne dass sich die Reihenfolge innerhalb der VIPs oder innerhalb der übrigen Gäste ändert.

  1. Entwerfen Sie ein Struktogramm für vipsNachVorn(q: Queue vom Inhaltstyp Gast). Nutzen Sie nur die Operationen der Schlange und zwei Hilfsschlangen.
  2. Stellen Sie den Ablauf für die Schlange G1, V1, G2, V2 (V = VIP) dar, indem Sie den Inhalt der drei Schlangen nach jeder Schleife angeben.
  3. Beurteilen Sie, ob eine dynamische Reihung diese Aufgabe einfacher lösen würde.

Hinweise

Hinweis zu Aufgabe a)
Erst q vollständig auf zwei Hilfsschlangen verteilen, dann in der richtigen Reihenfolge zurückschreiben.
Hinweis zu Aufgabe b)
Nach der ersten Schleife ist q leer.
Hinweis zu Aufgabe c)
Denken Sie an insertAt und an die Anzahl der Verschiebungen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
Erwartungshorizont zu Aufgabe b)

Nach Schleife 1: q leer, v = V1, V2, n = G1, G2. Nach Schleife 2: q = V1, V2, v leer. Nach Schleife 3: q = V1, V2, G1, G2, n leer.

Erwartungshorizont zu Aufgabe c)

Mit einer DynArray könnte man VIPs in einem Durchlauf nach vorn verschieben (delete + insertAt an der nächsten VIP-Position). Das ist kürzer zu schreiben, aber fehleranfälliger (Indizes verschieben sich) und aufwendiger, weil jedes Einfügen vorne viele Elemente verschiebt. Die Lösung mit Schlangen bleibt beim FIFO-Prinzip und ist gut prüfbar. Begründetes Urteil erwartet.