Reihungen — Suchen und Sortieren: Probe-Klassenarbeit – Informatik Grundkurs

Name

Datum

Punkte0 / 50

Notenpunkte—

Bearbeitet0 / 0

Bearbeitungszeit90 Minuten

Teil A

Reihungen, Suchen, Verfahren

22 Punkte

Grundwissen und Verfahren von Hand ausführen; Tracetabellen und Zwischenschritte auf dem Konzeptpapier notieren. Empfohlene Zeit: etwa 35 Minuten.

Freie Plätze im Parkhaus

AFB I 4 Punkte

Ein Parkhaus meldet die freien Plätze seiner sechs Etagen:

int[] frei = {23, 0, 17, 5, 41, 12};

Geben Sie an:

a) den Wert von frei.length 1 P

a) =

b) den Wert von frei[frei.length - 3] 1 P

b) =

c) den Index der Etage mit den meisten freien Plätzen 1 P

c) =

d) die Summe aller freien Plätze 1 P

d) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 6 (1 P) b) frei[3] = 5 (1 P) c) 41 steht an Index 4 (1 P) d) 23 + 0 + 17 + 5 + 41 + 12 = 98 (1 P).

Tracetabelle einer Schleife

AFB I 5 Punkte

int[] w = {3, 8, 5, 9, 9, 12};
int m = w[0];
int z = 0;
for (int i = 1; i < w.length; i++) {
    if (w[i] > m) {
        m = w[i];
        z++;
    }
}

Stellen Sie den Ablauf in einer Tracetabelle (i, w[i], m, z) dar und geben Sie die Ergebnisse ein.

a) Endwert von m 1 P

a) m =

b) Endwert von z 2 P

b) z =

c) Anzahl der Schleifendurchläufe 1 P

c) =

d) Was zählt z? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont:

i	w[i]	m	z
—	—	3	0
1	8	8	1
2	5	8	1
3	9	9	2
4	9	9	2
5	12	12	3

a) m = 12 (1 P) b) z = 3; die zweite 9 ist nicht echt größer (2 P) c) i = 1 … 5: 5 Durchläufe (1 P) d) z zählt, wie oft ein neues Maximum gefunden wurde (1 P).

Verfahren und ihre Idee

AFB I 5 Punkte

Ordnen Sie jedem Verfahren seine Grundidee zu. 5 P

Lineare Suche

Binäre Suche

Selectionsort

Insertionsort

Bubblesort

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Lineare Suche – auch unsortiert; binäre Suche – halbiert den Suchbereich; Selectionsort – Minimum des Rests nach vorn; Insertionsort – Einfügen in den sortierten Teil; Bubblesort – Nachbarn vertauschen (je 1 P).

Binäre Suche im Fahrplan

AFB II 4 Punkte

Die Abfahrtszeiten eines Busses (Minuten nach 6 Uhr) sind aufsteigend gespeichert:

ab70121182233294345406467518579631070117812

Wenden Sie die binäre Suche an (mitte = (links + rechts) / 2, ganzzahlig).

a) Wie viele Elemente werden bei der Suche nach 29 angesehen? 1 P

a) =

b) Welchen Wert hat mitte im zweiten Schritt der Suche nach 29? 1 P

b) mitte =

c) Wie viele Elemente werden bei der Suche nach 60 angesehen? 1 P

c) =

d) Wie viele Elemente sieht die binäre Suche bei dieser Reihung höchstens an? 1 P

d) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) mitte = 6 (40 > 29) → rechts = 5; mitte = 2 (18 < 29) → links = 3; mitte = 4 (29) gefunden: 3 Elemente (1 P) b) 2 (1 P) c) mitte = 6, 9, 11, 10 (40, 57, 70, 63), danach links = 10 > rechts = 9: 4 Elemente, Rückgabe −1 (1 P) d) \(\lfloor\log_2 13\rfloor + 1 = 3 + 1 = 4\) (1 P).

Mensa-Statistik

AFB II 4 Punkte

Die Mensa speichert, wie oft jedes ihrer drei Gerichte (g) an den fünf Wochentagen (t) verkauft wurde: verkauf[g][t].

verkauf	t = 0	t = 1	t = 2	t = 3	t = 4
g = 0	42	38	51	47	30
g = 1	25	31	22	40	36
g = 2	18	27	33	21	44

a) Nennen Sie den Wert von verkauf[1][3]. 1 P

a) =

b) Berechnen Sie die Summe der Zeile mit Index 2. 1 P

b) =

c) Ein Programm summiert mit zwei verschachtelten Schleifen jede Spalte und gibt den Index des Tages mit den meisten verkauften Essen aus. Ermitteln Sie diese Ausgabe. 2 P

c) Tag =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) Zeile 1, Spalte 3: 40 (1 P) b) 18 + 27 + 33 + 21 + 44 = 143 (1 P) c) Spaltensummen 85, 96, 106, 108, 110 → Tag mit Index 4 (2 P). Außen läuft die Schleife über die Spalten t, innen über die Zeilen g: summe += verkauf[g][t].

Teil B

Sortieren und Effizienz

28 Punkte

Verfahren analysieren, Vergleichszahlen herleiten und begründet entscheiden. Code in Java oder als Struktogramm. Empfohlene Zeit: etwa 55 Minuten.

Zwei Verfahren, eine Reihung

AFB II 7 Punkte

Die Reihung soll aufsteigend sortiert werden:

r47012135283294165

Analysieren Sie beide Verfahren, indem Sie jeweils den Zustand nach jedem Durchlauf notieren.

a) Selectionsort: Welcher Wert steht nach dem zweiten Durchlauf an Index 2? 1 P

a) =

b) Selectionsort: Anzahl der Vergleiche insgesamt 1 P

b) =

c) Selectionsort: Anzahl der Vertauschungen, bei denen zwei verschiedene Plätze getauscht werden 1 P

c) =

d) Insertionsort: Anzahl der Vergleiche zwischen Elementen insgesamt 2 P

d) =

e) Welches der beiden Verfahren ist stabil? 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Selectionsort: 8 12 35 47 29 16 → 8 12 35 47 29 16 → 8 12 16 47 29 35 → 8 12 16 29 47 35 → 8 12 16 29 35 47. a) 35 (1 P) b) \(\frac{6\cdot5}{2} = 15\) (1 P) c) Durchlauf 2 tauscht nicht, die anderen vier schon: 4 (1 P) d) Insertionsort: 1 + 2 + 3 + 3 + 4 = 13 Vergleiche (2 P) e) Insertionsort verschiebt nur an echt größeren Elementen vorbei und ist stabil; Selectionsort tauscht über andere hinweg (2 P).

Bubblesort mit Abbruch

AFB II 6 Punkte

Ein Bubblesort vergleicht benachbarte Paare, vertauscht bei a[j] > a[j + 1], macht jeden Durchlauf eine Stelle kürzer und bricht ab, wenn in einem Durchlauf nicht getauscht wurde.

t14091222173304255

Untersuchen Sie den Ablauf.

a) Welcher Wert steht nach dem ersten Durchlauf an Index 3? 1 P

a) =

b) Wie viele Durchläufe werden ausgeführt? 2 P

b) =

c) Wie viele Vergleiche werden insgesamt ausgeführt? 2 P

c) =

d) Wie viele Vertauschungen gibt es insgesamt? 1 P

d) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Durchlauf 1 (5 Vergleiche): 14↔9, 22↔17, 30↔25 → 9 14 17 22 25 30. a) 22 (1 P) b) Durchlauf 2 (4 Vergleiche) tauscht nicht → Abbruch nach 2 Durchläufen (2 P) c) 5 + 4 = 9 statt 15 ohne Abbruch (2 P) d) 3 (1 P).

Doppelte Einträge finden

AFB III 8 Punkte

Eine Methode zählt, wie viele Paare gleicher Werte eine Reihung enthält:

int doppelt = 0;
for (int i = 0; i < a.length - 1; i++) {
    for (int j = i + 1; j < a.length; j++) {
        if (a[i] == a[j]) {
            doppelt++;
        }
    }
}

a) Leiten Sie die Anzahl der Vergleiche a[i] == a[j] für 50 Werte her. 2 P

a) =

b) Welchen Wert hat doppelt für a = {4, 7, 4, 9, 7, 4}? 2 P

b) =

c) Entwerfen Sie für eine bereits sortierte Reihung ein Verfahren mit einer einzigen Schleife, das feststellt, ob es doppelte Werte gibt. Wie viele Vergleiche braucht es bei 50 Werten im ungünstigsten Fall? 2 P

c) =

d) Beurteilen Sie die Aussagen zur Doppelschleife. (mehrere Antworten richtig) 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) Für i = 0 … 48 läuft j über \(49 - i\) Werte: \(49 + 48 + \dots + 1 = \frac{50\cdot49}{2} = 1225\) (2 P) b) Die drei 4en an den Indizes 0, 2, 5 bilden 3 Paare, die zwei 7en ein Paar: 4 (2 P) c) In einer sortierten Reihung stehen gleiche Werte nebeneinander: for (int i = 1; i < a.length; i++) if (a[i] == a[i − 1]) return true; — höchstens \(n - 1 = 49\) Vergleiche (2 P) d) Richtig sind 1 (4950 statt 1225, Faktor ≈ 4) und 3; Speicher: nur zwei Zählvariablen; jedes Paar wird wegen j = i + 1 genau einmal verglichen (2 P).

Suchen in der Schulbibliothek

AFB III 7 Punkte

Die Schulbibliothek verwaltet 20 000 Medien über ihre Nummer. Pro Tag gibt es etwa 300 Suchanfragen; neue Medien kommen nur einmal im Halbjahr hinzu.

a) Anzahl angesehener Elemente der linearen Suche im ungünstigsten Fall 1 P

a) =

b) Anzahl angesehener Elemente der binären Suche im ungünstigsten Fall 2 P

b) =

c) Anzahl der Vergleiche, wenn die Nummern einmal mit Selectionsort sortiert werden 2 P

c) =

d) Entscheiden Sie sich begründet für ein Vorgehen. 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 20 000 (1 P) b) \(2^{14} = 16\,384 \le 20\,000 < 32\,768\): \(14 + 1 = 15\) (2 P) c) \(\frac{20\,000\cdot19\,999}{2} = 199\,990\,000\) (2 P) d) Jede binäre Suche spart im ungünstigsten Fall \(20\,000 - 15 = 19\,985\) Vergleiche; nach \(199\,990\,000 : 19\,985 \approx 10\,007\) Suchen, bei 300 pro Tag nach rund 34 Tagen, hat sich das Sortieren gelohnt. Da sich die Daten selten ändern, ist einmaliges Sortieren plus binäre Suche die beste Wahl (2 P).

Ergebnis

Erreicht

0 / 50

Prozent

0 %

Notenpunkte

—

Aufgabe	Thema	Punkte

Punkteverteilung

Aufgabe	Thema	Teil	AFB	Punkte
A1	Freie Plätze im Parkhaus	Teil A	AFB I	4
A2	Tracetabelle einer Schleife	Teil A	AFB I	5
A3	Verfahren und ihre Idee	Teil A	AFB I	5
A4	Binäre Suche im Fahrplan	Teil A	AFB II	4
A5	Mensa-Statistik	Teil A	AFB II	4
A6	Zwei Verfahren, eine Reihung	Teil B	AFB II	7
A7	Bubblesort mit Abbruch	Teil B	AFB II	6
A8	Doppelte Einträge finden	Teil B	AFB III	8
A9	Suchen in der Schulbibliothek	Teil B	AFB III	7
Summe (AFB I: 14 P · AFB II: 21 P · AFB III: 15 P)				50

Notenschema (Notenpunkte der Oberstufe)

Punkte	Notenpunkte	Beurteilung
48 – 50 P	15	sehr gut +
45 – 47 P	14	sehr gut
43 – 44 P	13	sehr gut −
40 – 42 P	12	gut +
38 – 39 P	11	gut
35 – 37 P	10	gut −
33 – 34 P	9	befriedigend +
30 – 32 P	8	befriedigend
28 – 29 P	7	befriedigend −
25 – 27 P	6	ausreichend +
23 – 24 P	5	ausreichend
20 – 22 P	4	ausreichend −
17 – 19 P	3	mangelhaft +
14 – 16 P	2	mangelhaft
10 – 13 P	1	mangelhaft −
0 – 9 P	0	ungenügend

Probe-Klausur

Reihungen, Suchen, Verfahren

Sortieren und Effizienz

Ergebnis

Punkteverteilung

Notenschema (Notenpunkte der Oberstufe)