MINT lernen

Übungen: Lineare Suche

Zehn Übungen zur linearen Suche — vom Nachvollziehen einer Tracetabelle bis zur Suche nach dem letzten Vorkommen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Was die lineare Suche leistet
AFB I

Die Methode lineareSuche(a, x) aus dem Unterricht durchsucht eine int-Reihung. Geben Sie alle Aussagen an, die zutreffen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Die Suche bricht beim ersten Treffer mit return i ab — deshalb gewinnt das erste Vorkommen, und die restlichen Elemente werden nie angesehen. −1 ist kein Index, sondern das vereinbarte Signal „nicht gefunden“; der letzte Index wäre a.length - 1.
Ansatz: Denken Sie an die Stelle, an der return i steht.
Weiter: Welcher Wert kann nie ein gültiger Index sein? Genau den nimmt man für „nicht gefunden“.
A2
Stimmt's? — Pfandautomat
AFB I

Ein Pfandautomat speichert die zuletzt gescannten Flaschencodes in int[] code = {507, 312, 845, 312, 190, 666};. Wenden Sie die lineare Suche gedanklich an und entscheiden Sie bei jeder Aussage, ob sie stimmt.

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

Faustregel: Treffer an Index i kostet i + 1 Vergleiche; ein fehlender Wert kostet immer alle n Vergleiche.
Ansatz: Zählen Sie ab Index 0 und stoppen Sie beim ersten Treffer.
Weiter: Vergleiche = Index des Treffers + 1.
A3
Tracetabelle Paketwaage
AFB I

Eine Paketstation speichert Gewichte in kg: int[] gewicht = {14, 3, 9, 21, 9};. Stellen Sie den Ablauf von lineareSuche(gewicht, 9) in einer Tracetabelle dar und geben Sie darunter Rückgabewert und Zahl der Vergleiche an.

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls. Wahrheitswerte als wahr oder falsch.
igewicht[i]gewicht[i] == 9
014
1
2
Rückgabewert
Vergleiche
Bei i = 2 ist der Vergleich wahr — die Methode gibt sofort 2 zurück. Die zweite 9 an Index 4 und die 21 werden nicht mehr angesehen. Drei Zeilen in der Tabelle, drei Vergleiche.
Ansatz: Die Schleife beginnt bei i = 0. In jeder Zeile steht genau ein Vergleich.
Weiter: Nach dem ersten „wahr“ endet die Tabelle, denn return verlässt die Methode.
A4
Kundenkartei
AFB II

Ein Fahrradladen speichert 480 Kundennummern unsortiert in einer Reihung. Berechnen Sie die Zahl der Vergleiche a[i] == x der linearen Suche.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Die gesuchte Nummer steht an Index 0: Vergleiche
  2. Die gesuchte Nummer steht an Index 211: Vergleiche
  3. Die gesuchte Nummer ist nicht in der Kartei: Vergleiche
  4. Man sucht rückwärts ab Index 479. Die Nummer steht an Index 211: Vergleiche
Vorwärts kostet Index i genau i + 1 Vergleiche. Rückwärts beginnt man bei 479 und prüft die Indizes 479, 478, …, 211 — das sind 479 − 211 + 1 = 269. Welche Richtung schneller ist, hängt nur davon ab, wo der Wert steht; im ungünstigsten Fall sind es immer 480.
Ansatz: Treffer an Index i: i + 1 Vergleiche.
Weiter: Rückwärts: von 479 bis 211 einschließlich zählen — Anzahl = größter − kleinster Index + 1.
A5
Gästeliste prüfen
AFB II

Für ein Schulfest soll geprüft werden, ob ein Name auf der Gästeliste steht. Erstellen Sie aus den Zeilen eine korrekte Java-Methode, indem Sie sie in die richtige Reihenfolge bringen.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static boolean enthaelt(String[] gaeste, String name) {
2for (int i = 0; i < gaeste.length; i++) {
3if (gaeste[i].equals(name)) return true;
4} // Ende der for-Schleife
5return false;
6} // Ende der Methode
Das return false; darf erst nach der Schleife stehen: Erst wenn alle Namen verglichen sind, steht fest, dass der Name fehlt. Bei Texten vergleicht man mit equals, nicht mit ==.
Ansatz: Die Methode liefert boolean — statt eines Index genügt „gefunden“ oder „nicht gefunden“.
Weiter: Wann darf man sicher sagen, dass der Name nicht auf der Liste steht?
A6
Ausdruck und Wert
AFB II Mix

Gegeben ist int[] t = {48, 52, 61, 57, 49};. Ordnen Sie jedem Ausdruck seinen Wert zu.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Zwei Ausdrücke liefern einen Index, zwei einen gespeicherten Wert, einer die Länge. t[4] ist 49 — und 49 steht nur an Index 4, deshalb liefert die Suche danach 4. Der letzte Index ist t.length - 1 = 4, nicht 5.
Ansatz: Unterscheiden Sie: Liefert der Ausdruck einen Index oder einen Wert aus der Reihung?
Weiter: t[t.length - 1] ist das letzte Element, also t[4].
A7
Drei Fehler in der Suche
AFB II

Die folgende Methode soll den Index des ersten Vorkommens von x liefern, sonst −1. Überprüfen Sie die Methode: Markieren Sie die fehlerhaften Zeilen und korrigieren Sie sie.

static int findeIndex(int[] a, int x) {
Klicken Sie die fehlerhaften Zeilen an — dann klappt ein Feld auf, in das Sie die richtige Zeile schreiben. Geprüft werden Auswahl und Korrekturen.
Zeile 1: Index 0 würde übersprungen. Zeile 2: Mit <= greift die Methode auf a[a.length] zu — ArrayIndexOutOfBoundsException. Zeile 5: Das else beendet die Suche schon nach dem ersten Element; −1 gehört ausschließlich hinter die Schleife (Zeile 8).
Ansatz: Prüfen Sie Startwert, Schleifenbedingung und die Stelle, an der −1 zurückgegeben wird.
Weiter: Drei Zeilen sind falsch. Welche Indizes gibt es bei Länge n, und wann steht fest, dass x fehlt?
A8
Wann darf man früh aufhören?
AFB III

Nicht jede Suchaufgabe erlaubt den Abbruch beim ersten Treffer. Entscheiden Sie für jede Aufgabe auf einer Reihung mit Tageswerten, wie sie am effizientesten korrekt gelöst wird.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1Vorwärts, beim ersten Treffer abbrechen
2Rückwärts, beim ersten Treffer abbrechen
3Immer die ganze Reihung durchlaufen
Abbrechen darf man nur, wenn der erste Treffer die Frage schon endgültig beantwortet. Für „das letzte …“ läuft man rückwärts und bricht ebenfalls früh ab. Zählen, alle Stellen sammeln und das Maximum brauchen dagegen jedes Element — ein späterer Wert könnte das Ergebnis noch ändern.
Ansatz: Fragen Sie: Kann ein Element weiter hinten das Ergebnis noch ändern, nachdem der erste Treffer gefunden ist?
Weiter: „Das letzte Vorkommen“ ist von hinten gesehen das erste.
A9
Suche in der Suche
AFB III Trick

Gegeben ist int[] b = {6, 2, 9, 2, 6, 9};. Bestimmen Sie den Wert des Ausdrucks lineareSuche(b, lineareSuche(b, 9)).

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Zuerst wird der innere Aufruf ausgewertet: Die erste 9 steht an Index 2. Der äußere Aufruf sucht jetzt den Wert 2 — nicht den Index 2! Die erste 2 steht an Index 1. Wer 2 antwortet, hat Index und Wert verwechselt.
Ansatz: Werten Sie von innen nach außen aus.
Weiter: Das Ergebnis des inneren Aufrufs wird im äußeren Aufruf zum Suchwert.
A10
Letztes Vorkommen
AFB III

Die lineare Suche soll so verändert werden, dass sie den Index des letzten Vorkommens von x liefert — mit so wenigen Vergleichen wie möglich. Verändern Sie die Methode, indem Sie die Lücken füllen.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
static int letzterIndex(int[] a, int x) {
    for (int i = ; i ; i) {
        if (a[i] == x) return i;
    }
    return ;
}
Rückwärts laufen und beim ersten Treffer abbrechen: Start bei a.length - 1 (bei a.length gäbe es eine Exception), Bedingung i >= 0, damit auch Index 0 geprüft wird, und i--. Nach der Schleife ist i nicht mehr sichtbar — zurückgegeben wird −1.
Ansatz: Das letzte Vorkommen ist von hinten gesehen das erste.
Weiter: Welcher Index ist der größte, und muss Index 0 noch geprüft werden?