Rekursion und Teile und herrsche: Probe-Klassenarbeit – Informatik Leistungskurs

Name

Datum

Punkte0 / 60

Notenpunkte—

Bearbeitet0 / 0

Bearbeitungszeit90 Minuten

Teil A

Rekursion verstehen und entwerfen

26 Punkte

Rekursive Methoden auswerten, Aufrufe verfolgen, Zeichenketten und die binäre Suche; Aufrufbäume und Tracetabellen auf dem Konzeptpapier notieren. Empfohlene Zeit: etwa 40 Minuten.

Ein Stapel Kisten

AFB I 5 Punkte

In einem Lager werden Kisten zu einer Pyramide gestapelt: unten \(n \times n\) Kisten, darüber \((n-1) \times (n-1)\), ganz oben eine.

static int kisten(int n) {
    if (n == 1) {
        return 1;
    }
    return n * n + kisten(n - 1);
}

Geben Sie an:

a) den Wert von kisten(4) 1 P

a) =

b) die Anzahl der Aufrufe bei kisten(4) 1 P

b) =

c) die Rekursionstiefe bei kisten(100) 1 P

c) =

d) Was passiert beim Aufruf kisten(0)? 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 16 + 9 + 4 + 1 = 30 (1 P) b) Aufrufe mit n = 4, 3, 2, 1 (1 P) c) Aufrufe mit n = 100 … 1 sind gleichzeitig offen: 100 (1 P) d) 0, −1, −2, … erreicht die Abbruchbedingung n == 1 nie (2 P).

Ein Aufrufbaum

AFB I 6 Punkte

static int t(int n) {
    if (n < 2) {
        return 1;
    }
    return t(n - 1) + t(n - 2);
}

Stellen Sie den Aufrufbaum von t(5) auf dem Konzeptpapier dar und geben Sie die Ergebnisse ein.

a) Rückgabewert von t(5) 2 P

a) =

b) Anzahl der Knoten des Aufrufbaums (Aufrufe) 2 P

b) =

c) Rekursionstiefe 1 P

c) =

d) Wie wächst die Zahl der Aufrufe von t(n) mit n? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: t(0) = t(1) = 1, t(2) = 2, t(3) = 3, t(4) = 5, a) t(5) = 8 (2 P) b) A(n) = 1 + A(n − 1) + A(n − 2): 1, 1, 3, 5, 9, 15 (2 P) c) längster Weg t(5), t(4), t(3), t(2), t(1): 5 (1 P) d) exponentiell, weil dieselben Teilprobleme mehrfach berechnet werden (1 P).

Vokale zählen

AFB II 7 Punkte

static int vokale(String s) {
    if (s.length() == 0) {
        return 0;
    }
    int r = vokale(s.substring(1));
    if ("aeiou".indexOf(s.charAt(0)) >= 0) {
        return r + 1;
    }
    return r;
}

"aeiou".indexOf(c) liefert die Position von c in "aeiou" oder −1. Analysieren Sie die Methode.

a) Rückgabewert von vokale("Rekursion") 1 P

a) =

b) Anzahl der Aufrufe dabei 1 P

b) =

c) Ordnen Sie jedem Teil der Methode seine Rolle zu. 4 P

if (s.length() == 0) return 0;

vokale(s.substring(1))

"aeiou".indexOf(s.charAt(0)) >= 0

return r + 1;

d) Wie viele Rahmen braucht eine iterative Fassung mit einer Schleife für "Rekursion" höchstens auf dem Aufrufstapel? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) e, u, i, o: 4 (1 P) b) 9 Zeichen + leerer String: 10 Aufrufe (1 P) c) Abbruchbedingung, Selbstaufruf mit kleinerem Problem, Verarbeitung des ersten Zeichens, Verknüpfung mit dem Teilergebnis (je 1 P) d) Eine Schleife läuft in einem einzigen Methodenaufruf: 1 Rahmen (1 P).

Binäre Suche rekursiv

AFB II 8 Punkte

static int binSuche(int[] a, int x, int links, int rechts) {
    if (links > rechts) {
        return -1;
    }
    int mitte = (links + rechts) / 2;
    if (a[mitte] == x) {
        return mitte;
    }
    if (a[mitte] < x) {
        return binSuche(a, x, mitte + 1, rechts);
    }
    return ________________;
}

Die Methode sucht in einer aufsteigend sortierten Reihung mit 1000 Elementen (Startaufruf binSuche(a, x, 0, 999)). Ermitteln Sie:

a) die größte Zahl angesehener Elemente a[mitte] 2 P

a) =

b) die größte Zahl von Aufrufen, wenn x nicht enthalten ist 2 P

b) =

c) Welcher Ausdruck gehört in die Lücke? 2 P

d) Überprüfen Sie die Aussagen über die Methode: Welche sind richtig? (mehrere Antworten richtig) 2 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) \(\lfloor\log_2 1000\rfloor + 1 = 10\) (2 P) b) 10 Aufrufe mit Blick auf ein Element und ein Aufruf mit leerem Bereich: 11 (2 P) c) binSuche(a, x, links, mitte - 1) — a[mitte] ist erledigt (2 P) d) logarithmische Tiefe und Endrekursion sind richtig; eine Hilfsreihung wird nicht gebraucht, und auf unsortierten Daten versagt die Suche (2 P).

Teil B

Teile und herrsche

34 Punkte

Mergesort und Quicksort von Hand, Laufzeit und Speicher beurteilen, Rekursionsgleichungen deuten. Empfohlene Zeit: etwa 50 Minuten.

Mergesort von Hand

AFB I 6 Punkte

Mergesort sortiert {29, 12, 41, 7, 33, 18, 25, 3} aufsteigend. Wenden Sie das Verfahren an und notieren Sie alle Mischvorgänge.

a) Welcher Wert steht nach der ersten Misch-Ebene (Paare) an Index 3? 1 P

a) =

b) Vergleiche in Ebene 1 1 P

b) =

c) Vergleiche in Ebene 2 2 P

c) =

d) Vergleiche in Ebene 3 1 P

d) =

e) Vergleiche insgesamt 1 P

e) =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Ebene 1: 12 29 | 7 41 | 18 33 | 3 25, a) Index 3: 41 (1 P) b) 4 · 1 = 4 (1 P) c) 7 12 29 41 (3 Vergleiche) und 3 18 25 33 (3 Vergleiche): 6 (2 P) d) 3 7 12 18 25 29 33 41: 7 Vergleiche, erst die 41 kommt als Rest (1 P) e) 17 — der ungünstigste Fall \(n\log_2 n - n + 1\) (1 P).

Quicksort zerlegt

AFB II 7 Punkte

Quicksort (Pivot = letztes Element, zerlege aus dem Unterricht) sortiert {46, 13, 58, 27, 71, 35, 40}. Untersuchen Sie den Ablauf mit einer Tracetabelle.

a) Rückgabewert des ersten Aufrufs zerlege(a, 0, 6) 2 P

a) =

b) Wert von a[6] nach diesem ersten Zerlegen 1 P

b) =

c) Vergleiche a[k] <= pivot in diesem ersten Zerlegen 1 P

c) =

d) Vergleiche insgesamt, bis die Reihung sortiert ist 2 P

d) =

e) Warum ist Quicksort nicht stabil? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Pivot 40: 13, 27, 35 werden nach vorn getauscht, danach Pivot an Index 3: 13 27 35 40 71 58 46. a) 3 (2 P) b) 46 (1 P) c) 6 (1 P) d) weiter 0…2 (Pivot 35): 2, 0…1 (Pivot 27): 1, 4…6 (Pivot 46): 2, 5…6 (Pivot 71): 1 — insgesamt 6 + 2 + 1 + 2 + 1 = 12 (2 P) e) Tausch über weite Strecken ändert die Reihenfolge gleicher Werte (1 P).

Laufzeiten beurteilen

AFB III 9 Punkte

Ein Programm soll \(n = 2^{16} = 65\,536\) Messwerte sortieren, die meist schon aufsteigend sortiert ankommen. Berechnen Sie die Kennzahlen und beurteilen Sie die Verfahren.

a) höchstens Vergleiche von Mergesort (\(n\log_2 n\)) 2 P

a) =

b) Vergleiche von Quicksort (Pivot = letztes Element) bei sortierter Eingabe 2 P

b) =

c) Rekursionstiefe von Mergesort 1 P

c) =

d) Rekursionstiefe von Quicksort bei sortierter Eingabe 1 P

d) =

e) Welche Beurteilung ist fachlich am besten begründet? 3 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 65 536 · 16 = 1 048 576 (2 P) b) \(\frac{65\,536\cdot65\,535}{2} = 2\,147\,450\,880\) (2 P) c) \(\log_2 65\,536 + 1 = 17\) (1 P) d) 65 536 (1 P) e) Urteil mit allen Kriterien: Mergesort garantiert \(n\log_2 n\) und geringe Tiefe, braucht \(65\,536\cdot4\) Byte ≈ 260 kB; Quicksort mit letztem Pivot ist bei sortierten Daten quadratisch und stürzt ab (mit Median-aus-drei wäre er brauchbar) (3 P).

Rekursionsgleichungen

AFB III 12 Punkte

Zum schnellen Potenzieren gibt es zwei Fassungen:

// Fassung 1
long h = potenz(x, n / 2);
return (n % 2 == 0) ? h * h : h * h * x;
// Fassung 2
return (n % 2 == 0) ? potenz(x, n / 2) * potenz(x, n / 2)
                    : potenz(x, n / 2) * potenz(x, n / 2) * x;

Beide haben die Abbruchbedingung n == 0 mit Rückgabe 1. Leiten Sie die Kennzahlen her und ordnen Sie Rekursionsgleichungen ihrem Wachstum zu.

a) Multiplikationen von Fassung 1 für n = 64 2 P

a) =

b) Aufrufe von Fassung 2 für n = 64 2 P

b) =

c) Welche Gleichung beschreibt die Zahl der Aufrufe von Fassung 1? 2 P

d) Ordnen Sie jeder Rekursionsgleichung das Wachstum ihrer Lösung zu. 5 P

\(T(n) = 2\,T\!\left(\frac{n}{2}\right) + n\) (Mergesort)

\(T(n) = T\!\left(\frac{n}{2}\right) + 1\) (binäre Suche)

\(T(n) = T(n - 1) + n\) (Quicksort, ungünstig)

\(T(n) = 2\,T\!\left(\frac{n}{2}\right) + 1\) (Maximum)

\(T(n) = 2\,T(n - 1) + 1\) (zwei Aufrufe mit n − 1)

e) Welches Wachstum hat die Zahl der Aufrufe der baumrekursiven fib(n)? 1 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) Exponenten 64, 32, 16, 8, 4, 2 (je 1 Multiplikation) und 1 (2 Multiplikationen): 8 (2 P) b) \(C(0) = 1\), \(C(n) = 1 + 2\,C(n/2)\): 3, 7, 15, 31, 63, 127, 255 — die doppelten Aufrufe machen den Vorteil zunichte (2 P) c) ein Aufruf mit halbem Exponenten: \(C(n) = C(n/2) + 1\), logarithmisch (2 P) d) n · log₂ n, log₂ n, n², n, 2ⁿ (je 1 P) e) exponentiell, etwa Faktor 1,6 je Schritt (1 P).

Ergebnis

Erreicht

0 / 60

Prozent

0 %

Notenpunkte

—

Aufgabe	Thema	Punkte

Punkteverteilung

Aufgabe	Thema	Teil	AFB	Punkte
A1	Ein Stapel Kisten	Teil A	AFB I	5
A2	Ein Aufrufbaum	Teil A	AFB I	6
A3	Vokale zählen	Teil A	AFB II	7
A4	Binäre Suche rekursiv	Teil A	AFB II	8
A5	Mergesort von Hand	Teil B	AFB I	6
A6	Quicksort zerlegt	Teil B	AFB II	7
A7	Laufzeiten beurteilen	Teil B	AFB III	9
A8	Rekursionsgleichungen	Teil B	AFB III	12
Summe (AFB I: 17 P · AFB II: 22 P · AFB III: 21 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

Rekursion verstehen und entwerfen

Teile und herrsche

Ergebnis

Punkteverteilung

Notenschema (Notenpunkte der Oberstufe)