Datenstrukturen im Abitur: Übungen – Informatik Grundkurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — du klickst, ziehst, ordnest, rechnest und knobelst. Jede Übung gibt dir sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fährst du über ein unterstrichenes Arbeitswort, siehst du, was es genau von dir verlangt.

Der Büchertisch

AFB I

Auf einem Tisch wird ein Stapel b aus Büchern aufgebaut: unten links, oben rechts geschrieben. Zeichne den Ablauf von fünf Aufrufen nach: Lege die Steine so aneinander, dass die rechte Hälfte eines Steins zur linken Hälfte des nächsten passt. Zwei Steine gehören nicht dazu.

Lege die Steine zu einer Kette: Ein Klick auf einen Stein legt ihn an das offene Ende, ⟲ dreht ihn. Ein Klick auf einen gelegten Stein nimmt ihn zurück. Mit der Tastatur: Tab zum Stein, Enter anlegen, R drehen.

Vorrat

Jedes push legt oben auf, das pop() nimmt Bio wieder weg. Am Ende liegen Mathe, Physik, Kunst übereinander, und top() liefert das oberste Buch, Kunst. Die beiden Ablenker zeigen eine vertauschte Reihenfolge (Physik unter Mathe) und ein Buch, das ohne push nach oben gerutscht wäre.

Beginne beim Startstein: Welcher Zustand entsteht, wenn der Aufruf auf der rechten Hälfte ausgeführt wird?

Neue Bücher kommen immer rechts (oben) dazu, und pop() nimmt das rechte Buch weg. Ein Zustand, in dem die Reihenfolge anders ist, kann nicht entstehen.

Operation und Wirkung

AFB II

Erläutere die Operationen, indem du jede mit ihrer Wirkung verbindest.

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

Lesen (top, head, getItem) und Entnehmen (pop, dequeue, delete) sauber trennen.

Frage: Welche Operationen verändern die Struktur?Warum? Nur entnehmende und einfügende.

Hilfe: top liest, pop entnimmt.

Schlange aus zwei Stapeln

AFB II

Eine Schlange wird mit zwei Stapeln ein und aus nachgebaut: enqueue(x) legt x immer auf ein. Stelle den Ablauf von dequeue() auf: Bringe die Schritte in die richtige Reihenfolge.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1 Zu Beginn die beiden leeren Stapel ein und aus anlegen.

2 Prüfen, ob beide Stapel leer sind: Dann gibt es nichts zu entnehmen.

3 Nur wenn aus leer ist: alle Elemente mit pop() von ein nehmen und auf aus legen.

4 Das oberste Element von aus mit pop() entnehmen.

5 Das entnommene Element als Ergebnis von dequeue() zurückgeben.

Die Stapel müssen zuerst existieren, danach wird auf Elemente geprüft. Umgeladen wird nur, wenn aus leer ist: Dabei kehrt sich die Reihenfolge um, das älteste Element liegt dann oben auf aus. Erst dann kann pop() es entnehmen und zurückgeben.

Anlegen kommt vor Benutzen, und geprüft wird, bevor etwas entnommen wird. Das Umladen ist nur eine Vorbereitung.

Die Entnahme mit pop() muss nach dem Umladen stehen, denn erst dort liegt das älteste Element oben auf aus. Das Zurückgeben ist der letzte Schritt.