MINT lernen

Datenstruktur wählen

Zwei Abituraufgaben zur Wahl der passenden Datenstruktur.

Dein Fortschritt:
0 / 0 Aufgaben
1

Eine Navigations-App

AFB I–II

Eine Navigations-App bietet drei Funktionen: (1) eine Liste von Zwischenzielen, in die man unterwegs an beliebiger Stelle einen Tankstopp einfügen kann; (2) einen Zurück-Knopf, der zur zuletzt angezeigten Ansicht wechselt; (3) Verkehrsmeldungen, die in der Reihenfolge ihres Eingangs angesagt werden.

  1. Ordnen Sie jeder Funktion eine geeignete Datenstruktur zu.
  2. Erläutern Sie Ihre Zuordnung für die Funktionen (1) und (3).

Hinweise

Hinweis zu Aufgabe a)
Fragen Sie jeweils: Welches Element wird als Nächstes gebraucht?
Hinweis zu Aufgabe b)
Nennen Sie jeweils das Prinzip und die Operationen, die gebraucht werden.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

(1) dynamische Reihung, (2) Stapel, (3) Schlange.

Erwartungshorizont zu Aufgabe b)

(1) Zwischenziele werden gezielt an einer Position eingefügt und über ihre Position angesprochen — das kann nur die dynamische Reihung (insertAt, getItem). (3) Die zuerst eingegangene Meldung wird zuerst angesagt (FIFO) — Eingang mit enqueue, Ansage mit dequeue.

2

Bestellsystem der Cafeteria

AFB II–III

In der Schul-Cafeteria werden Bestellungen über Tablets aufgegeben und in der Reihenfolge des Eingangs zubereitet. Jede Bestellung hat eine Nummer. Neu gewünscht ist, dass Bestellungen storniert werden können, solange sie noch nicht zubereitet werden.

  1. Vergleichen Sie Stapel, Schlange und dynamische Reihung hinsichtlich ihrer Eignung für das Bestellsystem mit Stornierung.
  2. Entwerfen Sie eine Methode stornieren(Queue<Integer> q, int nr), die eine Bestellung aus einer Schlange entfernt, ohne die Reihenfolge der übrigen zu ändern. Die Hilfsmethode anzahl darf verwendet werden.
  3. Beurteilen Sie, ob das System auf eine dynamische Reihung umgestellt werden sollte.

Hinweise

Hinweis zu Aufgabe a)
Zwei Kriterien: Reihenfolge der Zubereitung und Entfernen mitten aus der Warteschlange.
Hinweis zu Aufgabe b)
Ein Durchlauf mit n Rotationen genügt.
Hinweis zu Aufgabe c)
Wie oft wird storniert, wie oft zubereitet? Was ist fehleranfälliger?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Stapel: ungeeignet, weil die neueste Bestellung zuerst zubereitet würde. Schlange: Reihenfolge passt (FIFO); Stornieren ist nur durch vollständigen Durchlauf mit Wiederanstellen möglich. Dynamische Reihung: Reihenfolge lässt sich nachbilden (append, getItem(0)/delete(0)), Stornieren direkt über Suche und delete(i).

Erwartungshorizont zu Aufgabe b)
public void stornieren(Queue<Integer> q, int nr) {
    int n = anzahl(q);
    for (int i = 0; i < n; i++) {
        int b = q.dequeue();
        if (b != nr) {
            q.enqueue(b);
        }
    }
}
Erwartungshorizont zu Aufgabe c)

Für die Reihung spricht der direkte Zugriff beim Stornieren und die Möglichkeit, die Position einer Bestellung anzuzeigen. Für die Schlange spricht, dass sie die FIFO-Regel erzwingt: Niemand kann versehentlich vorgezogen werden, der Quelltext zum Zubereiten ist kürzer. Da Stornierungen selten sind und mit einem Durchlauf erledigt werden können, ist die Schlange vertretbar; wird häufig storniert oder die Position angezeigt, ist die Reihung vorzuziehen.