Reihungen — Suchen, Sortieren, Effizienz: Probe-Klassenarbeit – Informatik Leistungskurs

Name

Datum

Punkte0 / 60

Notenpunkte—

Bearbeitet0 / 0

Bearbeitungszeit90 Minuten

Teil A

Grundlagen: Reihungen, Suchen, Verfahren

15 Punkte

Wissen abrufen und Verfahren von Hand ausführen; Zwischenschritte auf dem Konzeptpapier notieren. Empfohlene Zeit: etwa 20 Minuten.

Temperaturmessung

AFB I 4 Punkte

Eine Wetterstation speichert sechs Messwerte:

double[] t = {12.5, 14.0, 9.5, 11.0, 13.5, 10.0};

Geben Sie an:

a) den Wert von t.length 1 P

a) =

b) den größten gültigen Index 1 P

b) =

c) den Wert von t[t.length / 2] 1 P

c) =

d) Womit ist jedes Element von new double[6] vor der ersten Zuweisung belegt? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 6 (1 P) b) 5 (1 P) c) t.length / 2 = 3, t[3] = 11.0 (1 P) d) 0.0 (1 P).

Binäre Suche im Fahrplan

AFB I 5 Punkte

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

ab30811421932543153664275085796310

Wenden Sie die binäre Suche an.

a) Welcher Index wird bei der Suche nach 50 zuerst untersucht? 1 P

a) =

b) Welchen Wert liefert die Suche nach 50? 1 P

b) =

c) Wie viele Vergleiche braucht die Suche nach 50? 1 P

c) =

d) Wie viele Vergleiche braucht die Suche nach 20 (nicht vorhanden)? 2 P

d) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) (0 + 10) / 2 = 5 (1 P) b) 31 < 50 → links = 6; mitte 8 mit 50: Rückgabe 8 (1 P) c) 2 (1 P) d) Mitten 5 (31), 2 (14), 3 (19), 4 (25), danach links = 4 > rechts = 3: 4 Vergleiche (2 P).

Verfahren und ihre Idee

AFB I 6 Punkte

Ordnen Sie jedem Verfahren seine Grundidee zu. 6 P

Lineare Suche

Binäre Suche

Selectionsort

Insertionsort

Bubblesort

Markierungsreihung

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Lineare Suche – unsortiert möglich; binäre Suche – halbiert; Selectionsort – Minimum nach vorn; Insertionsort – Einfügen; Bubblesort – Nachbarn tauschen; Markierungsreihung – Platz je Wert (je 1 P).

Teil B

Analysieren: Zählen, Sortieren, Laufzeit, Speicher

29 Punkte

Programme analysieren, Operationen zählen, Laufzeiten und Speicher abschätzen. Empfohlene Zeit: etwa 45 Minuten.

Paare zählen

AFB II 7 Punkte

int z = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (a[j] > a[i]) {
            z++;
        }
    }
}

Analysieren Sie das Programm für eine Reihung a der Länge \(n\).

a) Wie viele Vergleiche a[j] > a[i] finden für \(n = 5\) statt? 2 P

a) =

b) Wie viele sind es für \(n = 100\)? 2 P

b) =

c) Welchen Wert hat z für a = {4, 2, 5, 1, 3}? 2 P

c) =

d) In welcher Wachstumsklasse liegt die Zahl der Vergleiche? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) \(0 + 1 + 2 + 3 + 4 = 10\) (2 P) b) \(\frac{100 \cdot 99}{2} = 4950\) (2 P) c) z zählt die falsch stehenden Paare: (4,2), (4,1), (4,3), (2,1), (5,1), (5,3) — 6 (2 P) d) \(O(n^2)\) (1 P).

Insertionsort verfolgen

AFB II 6 Punkte

Die Reihung {7, 3, 9, 2, 6} wird mit Insertionsort aufsteigend sortiert. Ermitteln Sie:

a) die Gesamtzahl der Vergleiche 2 P

a) =

b) die Gesamtzahl der Verschiebungen 2 P

b) =

c) Welche Aussagen über Insertionsort treffen zu? 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Einfügen von 3: 1 Vergleich, 1 Verschiebung; 9: 1 Vergleich; 2: 3 Vergleiche, 3 Verschiebungen; 6: 3 Vergleiche (9, 7, 3), 2 Verschiebungen. a) 8 (2 P) b) 6 (2 P) c) stabil und in-place (2 P).

Laufzeiten abschätzen

AFB II 8 Punkte

Schätzen Sie ab bzw. bestimmen Sie:

a) Ein \(O(n^2)\)-Programm sortiert 20 000 Werte in 1,5 s. Wie viele Sekunden braucht es für 60 000 Werte? 2 P

a) =

b) Wie viele Vergleiche braucht die binäre Suche bei \(n = 10^6\) höchstens? 1 P

b) =

c) Ein \(O(2^n)\)-Programm braucht für \(n = 30\) eine Sekunde. Wie viele Sekunden für \(n = 33\)? 2 P

c) =

d) In welcher Klasse liegt \(T(n) = 7n \log_2 n + 3n^2\)? 1 P

e) Ab welchem kleinsten \(n_0\) gilt \(2n^2 + 50n \le 3n^2\)? 2 P

e) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) Faktor 3 bei \(n\) → Faktor 9: 13,5 s (2 P) b) 20 (1 P) c) \(2^3 = 8\) s (2 P) d) \(O(n^2)\) — \(n^2\) wächst schneller als \(n \log n\) (1 P) e) \(50n \le n^2 \Leftrightarrow n \ge 50\) (2 P).

Speicher

AFB II 8 Punkte

Berechnen Sie den Speicherbedarf der Elemente in Byte (boolean 1, int 4, double 8 Byte):

a) new double[500][400] 2 P

a) =

b) new int[300_000] 2 P

b) =

c) new boolean[10_000_000] 1 P

c) =

d) Welche Verfahren kommen mit \(O(1)\) Zusatzspeicher aus? 3 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) \(500 \cdot 400 \cdot 8 = 1\,600\,000\) (2 P) b) \(300\,000 \cdot 4 = 1\,200\,000\) (2 P) c) \(10^7\) (1 P) d) Selectionsort, lineare Suche, Insertionsort — Kopie \(O(n)\), Markierungsreihung \(O(W)\) (3 P).

Teil C

Beurteilen: Effizienz in Anwendungen

16 Punkte

Strategien vergleichen und begründet entscheiden. Empfohlene Zeit: etwa 25 Minuten.

Das Anmeldesystem

AFB III 8 Punkte

Ein Sportverein speichert 3000 Anmeldenummern unsortiert. Suchen erfolgen linear oder nach einmaligem Sortieren mit Selectionsort binär (ungünstigster Fall, \(\lfloor\log_2 3000\rfloor + 1 = 12\)).

Beurteilen Sie die Strategien.

a) Ab welcher kleinsten Zahl \(k\) von Suchen braucht „sortieren und binär suchen“ weniger Vergleiche als \(k\) lineare Suchen? 3 P

a) =

b) Es gibt 800 Suchen pro Tag, die Nummern ändern sich jeden Abend. Was ist effizienter? 2 P

c) Die Nummern ändern sich nur noch einmal im Monat (800 Suchen pro Tag). Was ist nun effizienter? 3 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) \(3000k > \frac{3000 \cdot 2999}{2} + 12k = 4\,498\,500 + 12k \Leftrightarrow k > 1505{,}5\): ab 1506 Suchen (3 P) b) 800 Suchen zwischen zwei Änderungen liegen unter 1506 — Sortieren lohnt nicht (2 P) c) Etwa 24 000 Suchen je Monat, weit über 1506: einmal sortieren und binär suchen (3 P).

Zwei Algorithmen

AFB III 8 Punkte

Algorithmus A braucht \(50 \cdot n \cdot \log_2 n\), Algorithmus B \(n^2\) Schritte.

Vergleichen Sie die Algorithmen.

a) Schritte von A für \(n = 256\) 2 P

a) =

b) Schritte von B für \(n = 256\) 1 P

b) =

c) Welcher Algorithmus ist für \(n = 4096\) schneller? 2 P

d) Welche Aussagen treffen zu? 3 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) \(50 \cdot 256 \cdot 8 = 102\,400\) (2 P) b) \(256^2 = 65\,536\) (1 P) c) A: \(50 \cdot 4096 \cdot 12 = 2\,457\,600\), B: \(16\,777\,216\) — A (2 P) d) A gewinnt für große \(n\); bei 256 ist B schneller; A liegt auch in \(O(n^2)\), weil O eine obere Schranke ist. Konstante Faktoren ändern die Klasse nicht (3 P).

Ergebnis

Erreicht

0 / 60

Prozent

0 %

Notenpunkte

—

Aufgabe	Thema	Punkte

Punkteverteilung

Aufgabe	Thema	Teil	AFB	Punkte
A1	Temperaturmessung	Teil A	AFB I	4
A2	Binäre Suche im Fahrplan	Teil A	AFB I	5
A3	Verfahren und ihre Idee	Teil A	AFB I	6
A4	Paare zählen	Teil B	AFB II	7
A5	Insertionsort verfolgen	Teil B	AFB II	6
A6	Laufzeiten abschätzen	Teil B	AFB II	8
A7	Speicher	Teil B	AFB II	8
A8	Das Anmeldesystem	Teil C	AFB III	8
A9	Zwei Algorithmen	Teil C	AFB III	8
Summe (AFB I: 15 P · AFB II: 29 P · AFB III: 16 P)				60

Notenschema (Notenpunkte der Oberstufe)

Punkte	Notenpunkte	Beurteilung
57 – 60 P	15	sehr gut +
54 – 56 P	14	sehr gut
51 – 53 P	13	sehr gut −
48 – 50 P	12	gut +
45 – 47 P	11	gut
42 – 44 P	10	gut −
39 – 41 P	9	befriedigend +
36 – 38 P	8	befriedigend
33 – 35 P	7	befriedigend −
30 – 32 P	6	ausreichend +
27 – 29 P	5	ausreichend
24 – 26 P	4	ausreichend −
20 – 23 P	3	mangelhaft +
16 – 19 P	2	mangelhaft
12 – 15 P	1	mangelhaft −
0 – 11 P	0	ungenügend

Probe-Klausur

Grundlagen: Reihungen, Suchen, Verfahren

Analysieren: Zählen, Sortieren, Laufzeit, Speicher

Beurteilen: Effizienz in Anwendungen

Ergebnis

Punkteverteilung

Notenschema (Notenpunkte der Oberstufe)