MINT lernen

Übungen: Datenstrukturen im Abitur

DynArray, Stapel und Schlange: Operationen lesen, Strukturen wählen, Fehler finden.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Aufgaben von den Operationen der Prüfungsvorgaben (AFB I) bis zur Abschätzung des Aufwands (AFB III). Jede Übung meldet sofort zurück.

A1
Operationen mit Rückgabe
AFB I

Gib alle Operationen an, die einen Wert zurückgeben.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Prüfen“.
Nach den Prüfungsvorgaben liefern pop() und dequeue() den entnommenen Inhalt zurück. Einfügeoperationen haben keinen Rückgabetyp.
Frage: Welche Operationen haben in der Signatur einen Typ hinter dem Doppelpunkt?Warum? Nur diese liefern etwas zurück.
Hilfe: Auch isEmpty() liefert etwas: einen Wahrheitswert.
A2
Stimmt's? — DynArray
AFB I

Fünf Aussagen zur dynamischen Reihung. Ordne sie als richtig oder falsch ein.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

setItem ersetzt, insertAt schiebt — der häufigste Verwechsler in Prüfungen.
Frage: Was ist der größte gültige Index bei 5 Elementen?Warum? Die Zählung beginnt bei 0.
Hilfe: Unterscheide ersetzen (setItem) und einfügen (insertAt).
A3
LIFO und FIFO
AFB I

Erkläre die Prinzipien, indem du die Lücken füllst — ein Wort bleibt übrig.

Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.

Beim wird das Element entnommen, das hineingelegt wurde. Bei der wird immer das Element entnommen. Wer bei leerer Struktur entnimmt, riskiert einen .

Keine der beiden Strukturen sortiert ihre Inhalte — sie merken sich nur die Reihenfolge des Einfügens.
Frage: Wo liegt beim Tellerstapel der Teller, den du zuerst nimmst?Warum? LIFO: last in, first out.
Hilfe: FIFO: first in, first out — wie an der Kasse.
A4
Welche Struktur passt?
AFB I

Ordne jeder Anwendung die passende Datenstruktur zu.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Stapel
2Schlange
3dynamische Reihung
Brauchst du Zugriff auf beliebige Positionen, ist die dynamische Reihung die einzige der drei Strukturen, die das direkt erlaubt.
Frage: Wird immer nur vorne, oben oder beliebig zugegriffen?Warum? Das Zugriffsmuster entscheidet.
Hilfe: Rückgängig macht die letzte Aktion zuerst rückgängig.
A5
Länge nach Operationen
AFB I

Eine leere DynArray d erhält: append(4), append(7), insertAt(0, 1), delete(1), append(9), setItem(0, 5). Bestimme d.getLength().

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Inhalte: [4] → [4, 7] → [1, 4, 7] → [1, 7] → [1, 7, 9] → [5, 7, 9]. setItem ändert die Länge nicht.
Frage: Welche Operationen ändern die Länge?Warum? append und insertAt verlängern, delete verkürzt.
Hilfe: Zwei append, ein insertAt, ein delete.
A6
Einen Stapel umdrehen
AFB II

Der Inhalt eines Stapels s soll in umgekehrter Reihenfolge in s stehen. Dazu gibt es zwei Hilfsstapel h1 und h2. Stelle die Schritte in der richtigen Reihenfolge dar.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1h1 ← erzeuge Stack(), h2 ← erzeuge Stack()
2solange s nicht leer: h1.push(s.pop())
3solange h1 nicht leer: h2.push(h1.pop())
4solange h2 nicht leer: s.push(h2.pop())
Jedes Umschichten dreht die Reihenfolge um — dreimal umschichten ergibt insgesamt eine Umkehrung.
Frage: Wie oft muss man umschichten, damit die Reihenfolge am Ende umgedreht in s steht?Warum? Jedes Umschichten dreht die Reihenfolge um.
Hilfe: Erst anlegen, dann s → h1 → h2 → s.
A7
Schlange mit Rücklauf
AFB II

Eine leere Schlange q: enqueue(3), enqueue(8), enqueue(5), dann zweimal: x ← q.dequeue(), q.enqueue(x · 2). Ermittle die Werte.

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. head() am Ende:
  2. Letztes Element der Schlange:
  3. Summe aller Elemente am Ende:
[3, 8, 5] → 3 raus, 6 rein: [8, 5, 6] → 8 raus, 16 rein: [5, 6, 16]. Summe 27.
Frage: Welches Element kommt beim ersten dequeue heraus?Warum? FIFO: das zuerst eingefügte.
Hilfe: Nach zwei Runden sind 3 und 8 als 6 und 16 hinten angekommen.
A8
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.
A9
Alle Nullen löschen
AFB II

Kim will alle Nullen aus einer DynArray d entfernen. Überprüfe ihre Implementierung und markiere die fehlerhaften Zeilen.

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Test: [0, 0, 5] — mit Kims Code bleibt eine 0 stehen, weil i nach dem ersten Löschen auf 1 springt.
Frage: Welcher Index ist der letzte gültige?Warum? getLength() − 1.
Hilfe: Was steht nach delete(i) an Position i?
A10
Wie teuer ist das?
AFB III

Schätze ab, wie viele Elemente bei einer DynArray mit 1000 Elementen verschoben werden müssen.

Wähle für jede Zeile eine Stufe: 1 = keins, 2 = etwa 1, 3 = etwa 500, 4 = etwa 999, 5 = etwa 1000. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = keins5 = etwa 1000
append(x)
delete(999)
insertAt(0, x)
delete(0)
insertAt(500, x)
Einfügen und Löschen vorne sind teuer, weil alle anderen Elemente wandern. Deshalb eignet sich eine Schlange besser, wenn ständig vorne entnommen wird.
Frage: Welche Elemente liegen hinter der Position, an der eingefügt oder gelöscht wird?Warum? Nur diese werden verschoben.
Hilfe: Vorne einfügen verschiebt alle 1000, vorne löschen 999.