MINT lernen

Abituraufgaben: Lineare Suche

Zwei Aufgaben im Abiturformat — von der Einlasskontrolle bis zur Hochwasserwarnung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Einlass im Schwimmbad

AFB I–II

Am Drehkreuz eines Schwimmbads wird jede Jahreskarte gescannt. Das Programm prüft, ob die Kartennummer x in der Reihung karten der gültigen Karten vorkommt. Die Reihung ist nicht sortiert; eine versehentlich doppelt ausgegebene Nummer steht zweimal darin. Zur Prüfung wird die lineare Suche verwendet, die den Index des ersten Vorkommens oder −1 liefert.

Ausschnitt der Reihung karten (Länge 8)
  1. Beschreiben Sie das Vorgehen der linearen Suche bei der Prüfung einer Kartennummer x und nennen Sie die beiden möglichen Arten von Rückgabewerten.
  2. Stellen Sie den Ablauf der Suche nach x = 7002 in einer Tracetabelle mit den Spalten i, karten[i] und karten[i] = x dar. Geben Sie außerdem die Rückgabewerte für x = 1187 und x = 1000 mit der jeweiligen Zahl der Vergleiche an.
  3. Implementieren Sie eine Methode static boolean istGueltig(int[] karten, int x), die genau dann true liefert, wenn x in karten vorkommt. Die Methode soll beim ersten Treffer abbrechen.
  4. Das Bad hat 12 000 Jahreskarten. Schätzen Sie ab, wie viele Vergleiche eine Prüfung im ungünstigsten Fall und bei einer gültigen Karte durchschnittlich benötigt, und wie sich beides ändert, wenn sich die Zahl der Karten verdoppelt.

Hinweise

Hinweis zu Aufgabe a)
Zwei Fälle unterscheiden: x wird gefunden oder nicht.
Hinweis zu Aufgabe b)
Die Tabelle endet mit dem ersten Vergleich, der wahr ist. Die Nummer 1187 steht zweimal in der Reihung.
Hinweis zu Aufgabe c)
Zählschleife über alle Indizes, im Rumpf ein Vergleich mit sofortigem return true; return false erst nach der Schleife.
Hinweis zu Aufgabe d)
Bei einer gültigen Karte ist jede Position etwa gleich wahrscheinlich — im Mittel liegt der Treffer in der Mitte.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Die Elemente werden ab Index 0 der Reihe nach mit x verglichen. Beim ersten Element, das gleich x ist, bricht die Suche ab und liefert dessen Index (Karte gültig). Ist nach dem letzten Element kein Treffer aufgetreten, liefert sie −1 (Karte ungültig). Rückgabewerte: ein gültiger Index 0 … 7 oder −1.

Erwartungshorizont zu Aufgabe b)
ikarten[i]karten[i] = x
04031falsch
11187falsch
25620falsch
32398falsch
41187falsch
57002wahr

Rückgabe 5 nach 6 Vergleichen. x = 1187: Rückgabe 1 (erstes Vorkommen) nach 2 Vergleichen. x = 1000: Rückgabe −1 nach 8 Vergleichen.

Erwartungshorizont zu Aufgabe c)
static boolean istGueltig(int[] karten, int x) {
    for (int i = 0; i < karten.length; i++) {
        if (karten[i] == x) {
            return true;
        }
    }
    return false;
}

Gleichwertig: return lineareSuche(karten, x) != -1;

Erwartungshorizont zu Aufgabe d)

Ungünstigster Fall (Karte ungültig oder ganz hinten): 12 000 Vergleiche. Gültige Karte, jede Position gleich wahrscheinlich: im Mittel \(\frac{12\,001}{2}\approx 6000\) Vergleiche. Bei 24 000 Karten verdoppeln sich beide Werte (24 000 bzw. etwa 12 000): Der Aufwand wächst linear mit der Zahl der Karten.

2

Hochwasser-Messstation

AFB II–III

Eine Messstation an einem Fluss speichert jeden Morgen den Pegelstand in cm; pegel[0] ist der erste Tag einer Messreihe. Ab einem Pegel über der Grenze grenze gilt Hochwasserwarnung. Ein Praktikant hat den abgebildeten Algorithmus entworfen.

Beispiel: pegel[0] = 310, pegel[1] = 355, pegel[2] = 402, pegel[3] = 388, pegel[4] = 415, pegel[5] = 370 und grenze = 400.

Algorithmus des Praktikanten
  1. Analysieren Sie den Algorithmus, indem Sie ihn für das Beispiel mit einer Tracetabelle durchlaufen. Geben Sie an, was der Rückgabewert allgemein bedeutet.
  2. Erläutern Sie, warum der Algorithmus unabhängig von den Daten immer genau so viele Vergleiche pegel[i] > grenze ausführt, wie die Reihung Elemente hat.
  3. Entwerfen Sie ein Struktogramm für einen Algorithmus mit demselben Ergebnis, der die Messreihe nur so weit durchläuft wie nötig. Geben Sie an, wie viele Vergleiche er für das Beispiel braucht.
  4. Ein Kollege schlägt vor, die Reihung pegel zuerst aufsteigend zu sortieren, damit die Suche schneller wird. Beurteilen Sie diesen Vorschlag.

Hinweise

Hinweis zu Aufgabe a)
Die Schleife läuft rückwärts. Notieren Sie in jeder Zeile i, pegel[i], das Ergebnis des Vergleichs und ergebnis.
Hinweis zu Aufgabe b)
Suchen Sie im Struktogramm nach einer Anweisung, die die Schleife vorzeitig beendet.
Hinweis zu Aufgabe c)
Vorwärts laufen und beim ersten Treffer sofort zurückgeben — das Muster der linearen Suche mit einer anderen Bedingung.
Hinweis zu Aufgabe d)
Was bedeutet der Index eines Messwerts nach dem Sortieren noch?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
ipegel[i]pegel[i] > 400ergebnis
5370falsch−1
4415wahr4
3388falsch4
2402wahr2
1355falsch2
0310falsch2

Rückgabe 2. Weil rückwärts gelaufen wird und jeder spätere Treffer ergebnis überschreibt, bleibt der kleinste Index mit pegel[i] > grenze stehen: der erste Tag mit Hochwasserwarnung, oder −1, wenn es keinen solchen Tag gibt.

Erwartungshorizont zu Aufgabe b)

Die Schleife endet nur über ihre Bedingung i ≥ 0; im Rumpf gibt es keine Rückgabe und keinen Abbruch. i läuft also von Länge − 1 bis 0, in jedem Durchlauf wird genau einmal verglichen: \(n\) Vergleiche. Ein Treffer ändert nur ergebnis, weil ein Tag weiter vorn — der ja erst später geprüft wird — den Wert noch ersetzen könnte.

Erwartungshorizont zu Aufgabe c)

Für das Beispiel: Vergleiche bei i = 0, 1, 2 — nach 3 Vergleichen wird 2 zurückgegeben (statt 6). Im ungünstigsten Fall bleiben es \(n\) Vergleiche.

Erwartungshorizont zu Aufgabe d)

Der Vorschlag ist ungeeignet. Gesucht ist der erste Tag — die Information steckt in der zeitlichen Reihenfolge, also im Index. Nach dem Sortieren gehört ein Index zu keinem Tag mehr; man könnte nur noch feststellen, ob ein Wert über der Grenze liegt, nicht wann. Außerdem kostet das Sortieren mit einfachen Verfahren etwa \(\frac{n^2}{2}\) Vergleiche, deutlich mehr als eine lineare Suche mit höchstens \(n\). Sinnvoll wäre es höchstens mit einer sortierten Kopie, die zu jedem Wert den ursprünglichen Tag mitspeichert — für eine einzelne Abfrage lohnt das nicht.