Eine Paketstation verwalten
AFB I–IIEine Paketstation hat zwölf Fächer, die für die Kundschaft mit den Nummern 1 bis 12 beschriftet sind. Die Steuerung speichert in einer Reihung belegt mit 12 Wahrheitswerten, ob ein Fach belegt ist. Das Fach mit dem Schild 1 gehört zum Index 0.
Beim Start werden folgende Anweisungen ausgeführt:
boolean[] belegt = new boolean[12]; belegt[4] = true; belegt[11] = true;
boolean[] belegt mit 12 Elementen- Beschreiben Sie, welchen Zustand die Reihung nach diesen drei Anweisungen hat und welche Fächer (Schildnummern) belegt sind.
- Anschließend werden
belegt[0] = true;,belegt[4] = false;undbelegt[7] = belegt[11];ausgeführt. Stellen Sie den Inhalt der Reihung danach als Kästchenfolge mit Indizes dar. - Ein Kollege schreibt für das Fach mit dem Schild 12 die Anweisung
belegt[12] = true;. Erläutern Sie, was beim Ausführen passiert, und geben Sie allgemein an, wie man aus einer Schildnummernrden Index erhält. - Implementieren Sie eine Methode
boolean istFrei(boolean[] belegt, int nr), die für eine Schildnummernrzurückgibt, ob das Fach frei ist. Für ungültige Nummern (kleiner als 1 oder größer als die Anzahl der Fächer) sollfalsezurückgegeben werden.
Hinweise
Hinweis zu Aufgabe a)
boolean-Reihung nach new?Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
belegt[nr - 1] auswerten. „Frei“ ist das Gegenteil von „belegt“.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
new boolean[12] erzeugt 12 Plätze mit dem Standardwert false (frei). Danach sind belegt[4] und belegt[11] true, alle anderen false. Belegt sind also die Fächer mit den Schildern 5 und 12 (Index + 1), wie in der Abbildung.
Erwartungshorizont zu Aufgabe b)
Index 0 bis 11: true, false, false, false, false, false, false, true, false, false, false, true. belegt[0] wird belegt (Schild 1), belegt[4] wieder frei, belegt[7] erhält den Wert von belegt[11], also true (Schild 8). Belegt: Schilder 1, 8 und 12. Darstellung als 12 Kästchen mit Indizes 0 bis 11 unter den Kästchen.
Erwartungshorizont zu Aufgabe c)
Die Reihung hat die Indizes 0 bis 11; belegt[12] liegt außerhalb. Das Programm übersetzt, bricht aber beim Ausführen mit einer ArrayIndexOutOfBoundsException ab. Weil die Zählung der Kundschaft bei 1 und die der Indizes bei 0 beginnt, gilt allgemein: Index = nr − 1. Richtig ist belegt[11] = true;.
Erwartungshorizont zu Aufgabe d)
boolean istFrei(boolean[] belegt, int nr) {
if (nr < 1 || nr > belegt.length) {
return false;
}
return !belegt[nr - 1];
}Bewertet werden: Prüfung beider Grenzen mit belegt.length (nicht fest 12), Umrechnung nr − 1, Rückgabe der Negation. Eine Lösung mit if (belegt[nr - 1]) return false; else return true; ist gleichwertig.
Sitzplätze im Fernbus
AFB II–IIIEin Fernbus hat 52 Sitzplätze. Für jede Fahrt speichert das Buchungssystem in einer Reihung sitz mit 52 ganzen Zahlen die Kundennummer der Person, die den Platz gebucht hat; 0 bedeutet frei. Der Platz mit der Nummer p (1 bis 52) hat den Index p − 1.
Ein Auszubildender testet das System mit diesem Pseudocode (Index ab 0):
sitz ← neue Reihung mit 52 ganzen Zahlen, alle 0 sitz[0] ← 4711 sitz[1] ← 815 reserve ← sitz reserve[1] ← 0 sitz[2] ← reserve[0] + 1
- Analysieren Sie den Pseudocode: Geben Sie den Inhalt von
sitz[0],sitz[1]undsitz[2]am Ende an und erklären Sie das Ergebnis fürsitz[1]. - Eine ganze Zahl belegt 4 Byte. Schätzen Sie den Speicherbedarf für die Sitzplatzreihungen aller Fahrten eines Jahres ab, wenn das Unternehmen täglich 120 Fahrten anbietet.
- Entwerfen Sie ein Struktogramm für einen Algorithmus
umbuchen(sitz, von, nach), der die Buchung vom Platzvonauf den Platznach(Platznummern 1 bis 52) verlegt. Er sollwahrzurückgeben, wenn das gelungen ist, undfalsch, wenn eine Platznummer ungültig ist,vonfrei ist odernachschon belegt ist. - Das Unternehmen möchte zusätzlich eine Warteliste für ausgebuchte Fahrten führen und dafür ebenfalls eine statische Reihung verwenden. Erörtern Sie diesen Vorschlag.
Hinweise
Hinweis zu Aufgabe a)
reserve ← sitz bei Reihungen — Kopie der Werte oder zweiter Name?Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
reserve ← sitz legt keine zweite Reihung an; beide Namen verweisen auf dieselbe Reihung. Daher setzt reserve[1] ← 0 auch sitz[1] auf 0 — die Buchung von Kunde 815 ist gelöscht. Am Ende: sitz[0] = 4711, sitz[1] = 0, sitz[2] = 4712.
Erwartungshorizont zu Aufgabe b)
Pro Fahrt \(52\cdot4=208\) Byte. Pro Jahr \(120\cdot365=43\,800\) Fahrten, also \(43\,800\cdot208=9\,110\,400\) Byte \(\approx 9\) MB. Der Bedarf wächst linear mit der Zahl der Fahrten; für heutige Rechner ist er gering. (Zusätzlicher Verwaltungsaufwand pro Reihung darf vernachlässigt werden.)
Erwartungshorizont zu Aufgabe c)
Wichtig: Gültigkeit der Nummern vor dem ersten Zugriff prüfen; Reihenfolge kopieren → alten Platz freigeben (umgekehrt ginge die Kundennummer verloren). Gleichwertige Lösungen mit nacheinander geprüften Fehlerfällen sind zulässig.
Erwartungshorizont zu Aufgabe d)
Dafür: Reihungen sind einfach, der Zugriff über den Index ist schnell; eine Obergrenze (z. B. 20 Plätze) lässt sich betrieblich begründen. Dagegen: Die Länge einer Warteliste ist vorher unbekannt; ist die Reihung zu klein, müssen Interessenten abgewiesen oder muss eine größere Reihung angelegt und umkopiert werden, ist sie zu groß, bleibt Speicher ungenutzt. Beim Nachrücken der ersten Person müssten alle anderen Einträge um einen Platz verschoben werden. Fazit: Für die Sitzplätze passt die feste Länge, für die Warteliste eignet sich eine Struktur mit veränderlicher Länge (dynamische Reihung oder Schlange, Kapitel 4) besser. Bewertet wird die begründete Abwägung, nicht das Ergebnis.