MINT lernen

Algorithmen mit Schlangen

Zehn Übungen zu Durchlauf, Filter und Rundlauf-Verfahren.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn interaktive Übungen zum Klicken, Ziehen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung.

A1
Einmal ganz herum
AFB I

Die Schlange q hat n Elemente. Welche Programmteile besuchen jedes Element genau einmal und lassen q danach unverändert?

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Prüfen“.
Die while-Variante läuft endlos, weil die Schlange nie leer wird. Mit head() wächst die Schlange nur — das vorderste Element wird n-mal kopiert.
A2
Stimmt's? — Rundlauf
AFB I

Fünf Aussagen zum Rundlauf-Verfahren (Round Robin).

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

Rundlauf = Schlange + Zeitscheibe. Mehr steckt nicht dahinter.
A3
Lückentext Rundlauf
AFB I

Setze die Fachbegriffe ein — drei Wörter bleiben ü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 Rundlauf-Verfahren stehen alle rechenbereiten Programme in einer . Das Programm wird mit geholt und darf höchstens eine lang rechnen. Ist es danach nicht fertig, wird es mit hinten wieder angestellt.

Wer hier „oberste“ oder „push“ einsetzt, hat Stapel und Schlange vertauscht.
A4
Rundlauf von Hand
AFB II

Drei Programme stehen in dieser Reihenfolge in der Schlange: X braucht 3 Takte, Y 1 Takt, Z 2 Takte. Die Zeitscheibe ist 1 Takt.

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Y ist fertig nach Takt
  2. Z ist fertig nach Takt
  3. X ist fertig nach Takt
  4. Wie oft wird ein Programm nach seiner Zeitscheibe wieder angestellt?
Ablauf: X, Y, Z, X, Z, X. Wieder angestellt werden X nach Takt 1, Z nach Takt 3 und X nach Takt 4.
A5
Filtern in Ordnung bringen
AFB II

Die Methode entfernt alle Vorkommen von x aus der Schlange q; die übrigen behalten ihre Reihenfolge. Bringe die Zeilen in die richtige Reihenfolge.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1 int n = anzahl(q);
2 for (int i = 0; i < n; i++) {
3 String e = q.dequeue();
4 if (!e.equals(x)) { q.enqueue(e); }
5 }
Die Anzahl muss vor der Schleife feststehen: Während des Filterns wird die Schlange kürzer.
A6
Fehler in der Summe
AFB II

Die Methode soll die Summe aller Zahlen in q liefern und q unverändert lassen. Welche Zeilen sind falsch?

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Wird ein Element zu oft rotiert, stimmt nicht nur die Summe nicht — die Schlange beginnt danach mit einem anderen Element.
A7
Kleine oder große Zeitscheibe?
AFB II

Welche Wirkung gehört zu einer sehr kleinen, welche zu einer sehr großen Zeitscheibe?

Setze in jeder Zeile das passende Kreuz — hier ist es genau eins pro Zeile. Enter setzt und löscht.
Wirkungkleine Zeitscheibegroße Zeitscheibe
viele Wechsel zwischen den Programmen
kurze Programme warten lange auf lange Programme
verhält sich wie eine einfache Warteschlange
jedes Programm kommt schnell einmal an die Reihe
hoher Verwaltungsaufwand durch häufiges Wiederanstellen
Betriebssysteme wählen deshalb einen Mittelweg: klein genug, damit alles flüssig wirkt, groß genug, damit nicht die meiste Zeit mit Wechseln vergeht.
A8
Doppelt angestellt
AFB III

Die Schlange q = [2, 7, 4, 9, 6] (vorn links) durchläuft:

for (int i = 0; i < 5; i++) {
    int x = q.dequeue();
    if (x % 2 == 0) {
        q.enqueue(x);
        q.enqueue(x);
    }
}
Welche Summe haben die Zahlen in q danach?

Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Ungerade Zahlen verschwinden, gerade werden verdoppelt angestellt: [2, 2, 4, 4, 6, 6] — Summe 24. Die Schleife läuft fest 5-mal, deshalb werden die neu angestellten Zahlen nicht noch einmal bearbeitet.
A9
Abzählreim
AFB III

Vier Kinder stehen in der Schlange [Ana, Ben, Cem, Dea]. In jeder Runde werden zwei Kinder vorn entnommen und hinten wieder angestellt, das dritte scheidet aus. Spiele den Reim durch.

Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
    Mit einer Schlange lässt sich jeder Abzählreim ohne Index simulieren — rotieren heißt abzählen.
    A10
    Direkt oder mit Umweg?
    AFB III

    Welche Aufgaben erledigt eine einzige Schlangen-Operation, welche brauchen einen Durchlauf mit Hilfsschlange oder Anzahl?

    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).
    1eine Operation genügt
    2Durchlauf nötig
    Das hinterste Element ist die Falle: Man kann es anstellen, aber nicht ansehen — dafür muss die ganze Schlange einmal rotieren.