MINT lernen

Übung — AFB II (Zusammenhänge herstellen)

Zehn Aufgaben zum Nachverfolgen von Algorithmen — mit gestuften Tipps.

Dein Fortschritt:
0 / 0 Aufgaben
2

Aufgabenblock — AFB II

Zehn Aufgaben aus dem ganzen Kapitel: Abläufe nachverfolgen, Zwischenstände bestimmen, Algorithmen vergleichen — mit gestuften Tipps, wenn du nicht weiterkommst.

A1
Operationen auf DynArray
AFB II

Die Reihung l = [10, 20, 30] erlebt nacheinander insertAt(0, 5), append(40), delete(2).

a) Welchen Wert liefert danach getLength()? b) Welchen Wert liefert getItem(2)?

Ansatz: Nach jeder Operation die ganze Reihung notieren.
Weg: [5, 10, 20, 30] → [5, 10, 20, 30, 40] → delete(2) entfernt 20.
Lösung: a) 4 b) 30
Vollständige Lösung
Nach dem Einfügen vorn steht 20 an Index 2 und wird gelöscht: [5, 10, 30, 40]. Hinweis: Wer den Index vor dem Einfügen verwendet, löscht fälschlich 30.
A2
Maximum mit Index
AFB II

Der Algorithmus „Index des Maximums“ (Start pos = 0, ersetzen bei getItem(i) > getItem(pos)) läuft auf l = [7, 3, 12, 12, 5].

a) Wie oft wird pos ersetzt? b) Welchen Index liefert der Algorithmus?

Ansatz: Tracetabelle mit i, getItem(i), getItem(pos) anlegen.
Weg: Nur bei i = 2 ist 12 > 7; bei i = 3 ist 12 > 12 falsch.
Lösung: a) 1 b) 2
Vollständige Lösung
pos wird nur bei i = 2 ersetzt. Die zweite 12 an Index 3 ersetzt nicht, weil der Vergleich echt größer verlangt. Rückgabe: Index 2 (erstes Maximum).
A3
Löschen in der Vorwärts-Schleife
AFB II

Eine Vorwärts-for-Schleife löscht alle Einsen aus l = [1, 1, 5, 1] mit delete(i).

a) Welche Länge hat l danach? b) Wie viele Einsen stehen noch darin?

Ansatz: Nach jedem delete die Reihung neu aufschreiben und i trotzdem erhöhen.
Weg: i = 0 löscht → [1, 5, 1]; i = 1 prüft 5; i = 2 löscht → [1, 5]; Ende.
Lösung: a) 2 b) 1
Vollständige Lösung
Die zweite Eins rückt auf Index 0 und wird übersprungen. Ergebnis [1, 5] — falsch; richtig wäre [5].
A4
Stapel teilweise leeren
AFB II

Die Zahlen 1, 2, 3, 4, 5 werden in dieser Reihenfolge auf einen leeren Stapel gelegt. Danach wird dreimal pop() aufgerufen.

a) Welchen Wert liefert das dritte pop()? b) Welchen Wert liefert danach top()?

Ansatz: Oben liegt die 5.
Weg: pop liefert 5, 4, 3; darunter bleiben 1 und 2.
Lösung: a) 3 b) 2
Vollständige Lösung
Die pop-Aufrufe liefern 5, 4, 3. Im Stapel bleiben 1 (unten) und 2 (oben); top() liefert 2.
A5
Klammertiefe
AFB II

Der Ausdruck ( [ ] ( { } ) ) wird mit dem Stapel-Algorithmus geprüft.

a) Wie viele Klammern liegen höchstens gleichzeitig im Stapel? b) Wie viele liegen nach dem vierten Zeichen darin?

Ansatz: Öffnend = push, schließend = pop.
Weg: Höhen: 1, 2, 1, 2, 3, 2, 1, 0.
Lösung: a) 3 b) 2
Vollständige Lösung
Nach ( ( { liegen drei Klammern im Stapel — die tiefste Verschachtelung. Nach dem vierten Zeichen (zweite runde Klammer) sind es zwei.
A6
Rotation einer Schlange
AFB II

Die Schlange q = [4, 7, 2, 9] (vorn links) wird sechsmal rotiert: jeweils q.enqueue(q.dequeue()).

a) Welche Zahl steht danach vorn? b) Wie viele weitere Rotationen braucht es, bis 4 wieder vorn steht?

Ansatz: Nach 4 Rotationen ist alles wie am Anfang.
Weg: 6 = 4 + 2 → wie nach 2 Rotationen: [2, 9, 4, 7].
Lösung: a) 2 b) 2
Vollständige Lösung
Nach sechs Rotationen lautet q = [2, 9, 4, 7]. Die 4 steht an Position 3; nach zwei weiteren Rotationen ist sie vorn.
A7
Rundlauf
AFB II

Programm A braucht 3 Takte, B 4 Takte; A steht vorn. Die Zeitscheibe ist 2 Takte.

a) Nach welchem Takt ist A fertig? b) Nach welchem Takt ist B fertig?

Ansatz: Nicht fertige Programme hinten wieder anstellen.
Weg: A 0–2 (Rest 1), B 2–4 (Rest 2), A 4–5 fertig, B 5–7 fertig.
Lösung: a) 5 b) 7
Vollständige Lösung
Ablauf: A, B, A, B. A ist nach Takt 5 fertig, B nach Takt 7. Ohne Rundlauf wäre A nach 3 und B nach 7 fertig — der Rundlauf verzögert hier A.
A8
Schlange filtern
AFB II

Aus q = [3, 12, 5, 20, 8] werden mit einem Durchlauf alle Werte größer als 10 entfernt.

a) Wie viele Elemente hat q danach? b) Welche Summe haben sie?

Ansatz: n = 5 Rotationen, nur Werte ≤ 10 wieder anstellen.
Weg: Übrig bleiben 3, 5, 8.
Lösung: a) 3 b) 16
Vollständige Lösung
Wieder angestellt werden 3, 5 und 8 — in unveränderter Reihenfolge. Summe 16.
A9
Gleiche Eingabe, andere Ausgabe
AFB II

In einen leeren Stapel und eine leere Schlange werden 1, 2, 3, 4 eingefügt; danach wird bei beiden dreimal entnommen.

a) Was liefert das dritte Entnehmen beim Stapel? b) … bei der Schlange?

Ansatz: Stapel liefert von hinten, Schlange von vorn.
Weg: Stapel: 4, 3, 2 · Schlange: 1, 2, 3.
Lösung: a) 2 b) 3
Vollständige Lösung
Der Stapel liefert 4, 3, 2, die Schlange 1, 2, 3. Übrig bleibt beim Stapel die 1, bei der Schlange die 4.
A10
Aufwand beim Zählen
AFB II

Die Methode anzahl(Stack s) lädt s komplett auf einen Hilfsstapel um und danach zurück. s enthält 6 Elemente.

a) Wie oft wird insgesamt push aufgerufen? b) Wie oft pop?

Ansatz: Jedes Element wird zweimal bewegt.
Weg: Umladen: 6 pop + 6 push; Zurückladen: 6 pop + 6 push.
Lösung: a) 12 b) 12
Vollständige Lösung
Jedes der 6 Elemente wird zweimal umgeladen, jeweils mit einem pop und einem push: 12 und 12 Aufrufe.