Algorithmen mit Schlangen: Abituraufgaben – Informatik Grundkurs

Dein Fortschritt:

0 / 0 Aufgaben

Rundlauf im Betriebssystem

AFB I–II

Ein Betriebssystem verteilt die Rechenzeit nach dem Rundlauf-Verfahren mit einer Zeitscheibe von 2 Takten. In der Schlange stehen in dieser Reihenfolge P1 (4 Takte), P2 (2 Takte) und P3 (3 Takte).

Stellen Sie den Ablauf in einer Tabelle dar (Zeitraum, rechnendes Programm, Restzeit danach, Schlange danach).
Geben Sie die Fertigstellungszeiten der drei Programme und ihren Mittelwert an.

Hinweise

Hinweis zu Aufgabe a)

Ein Programm, das nicht fertig ist, wird hinten wieder angestellt.

Hinweis zu Aufgabe b)

Lesen Sie ab, wann die Restzeit jeweils 0 wird.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Zeit	rechnet	Rest	Schlange danach
0–2	P1	2	P2, P3, P1
2–4	P2	0	P3, P1
4–6	P3	1	P1, P3
6–8	P1	0	P3
8–9	P3	0	—

Erwartungshorizont zu Aufgabe b)

P2: 4, P1: 8, P3: 9 Takte; Mittelwert (4 + 8 + 9) : 3 = 7 Takte.

Große Aufträge aussortieren

AFB II–III

Eine Queue<Integer> q enthält Seitenzahlen von Druckaufträgen. Die Hilfsmethode int anzahl(Queue<Integer> q) liefert die Anzahl der Elemente und lässt q unverändert.

Implementieren Sie die Methode void entferneGroesser(Queue<Integer> q, int grenze), die alle Aufträge mit mehr als grenze Seiten entfernt. Die übrigen sollen ihre Reihenfolge behalten.
Erweitern Sie die Methode so, dass sie die entfernten Aufträge in einer neuen Schlange sammelt und diese zurückgibt.
Analysieren Sie, was passiert, wenn statt der Zählschleife while (!q.isEmpty()) verwendet wird.

Hinweise

Hinweis zu Aufgabe a)

n einmal bestimmen, dann n-mal entnehmen und nur die passenden wieder anstellen.

Hinweis zu Aufgabe b)

Rückgabetyp ändern und im else-Fall anstellen.

Hinweis zu Aufgabe c)

Unterscheiden Sie: Es gibt einen Auftrag ≤ grenze — oder alle sind größer.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

public void entferneGroesser(Queue<Integer> q, int grenze) {
    int n = anzahl(q);
    for (int i = 0; i < n; i++) {
        int s = q.dequeue();
        if (s <= grenze) {
            q.enqueue(s);
        }
    }
}

Erwartungshorizont zu Aufgabe b)

public Queue<Integer> entferneGroesser(Queue<Integer> q, int grenze) {
    Queue<Integer> gross = new Queue<Integer>();
    int n = anzahl(q);
    for (int i = 0; i < n; i++) {
        int s = q.dequeue();
        if (s <= grenze) {
            q.enqueue(s);
        } else {
            gross.enqueue(s);
        }
    }
    return gross;
}

Erwartungshorizont zu Aufgabe c)

Bleibt mindestens ein Auftrag mit höchstens grenze Seiten übrig, wird er immer wieder angestellt; die Schlange wird nie leer — Endlosschleife. Nur wenn alle Aufträge zu groß sind, leert sich die Schlange und die Schleife endet (dann zufällig mit richtigem Ergebnis). Die Anzahl der Durchläufe muss deshalb vorab feststehen.