MINT lernen

Abituraufgaben: Implementieren auf Papier

Zwei Implementierungsaufgaben mit Schreibtischtest und Bewertung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Notenliste auswerten

AFB I–II

Die Noten einer Klausur (1 bis 6) stehen in einer DynArray noten vom Inhaltstyp Ganzzahl.

  1. Implementieren Sie anzahlUnter(noten: DynArray, g: Ganzzahl): Ganzzahl, die die Anzahl der Noten liefert, die schlechter als g sind (also größer als g).
  2. Implementieren Sie entferneFehlend(noten: DynArray), die alle Einträge 0 (Klausur nicht geschrieben) entfernt.
  3. Begründen Sie mit einem Schreibtischtest für [0, 0, 3], dass Ihre Lösung zu b) korrekt arbeitet.

Hinweise

Hinweis zu Aufgabe a)
Zählschleife über getLength() mit getItem(i).
Hinweis zu Aufgabe b)
Nach delete(i) rücken die folgenden Elemente nach — i nur im else-Zweig erhöhen.
Hinweis zu Aufgabe c)
Tabelle mit i, getLength() und Inhalt nach jedem Schritt.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
def anzahlUnter(noten, g):
    n = 0
    for i in range(noten.getLength()):
        if noten.getItem(i) > g:
            n = n + 1
    return n
Erwartungshorizont zu Aufgabe b)
def entferneFehlend(noten):
    i = 0
    while i < noten.getLength():
        if noten.getItem(i) == 0:
            noten.delete(i)
        else:
            i = i + 1
Erwartungshorizont zu Aufgabe c)
igetLength()InhaltAktion
03[0, 0, 3]0 → delete(0)
02[0, 3]0 → delete(0)
01[3]3 → i = 1
11[3]Schleife endet

Beide Nullen werden entfernt, weil i nach dem Löschen nicht erhöht wird.

2

Palindrom-Prüfung

AFB II–III

Ein Palindrom liest sich vorwärts und rückwärts gleich, z. B. „RENTNER“. Mit einem Stapel und einer Schlange kann man das prüfen: Jedes Zeichen wird in beide Strukturen eingefügt; danach vergleicht man die Zeichen, die beide Strukturen nacheinander liefern.

  1. Erläutern Sie, warum dieser Vergleich genau dann nur Übereinstimmungen liefert, wenn das Wort ein Palindrom ist.
  2. Implementieren Sie istPalindrom(w: Zeichenkette): Wahrheitswert mit Stack und Queue.
  3. Beurteilen Sie Ihre Lösung im Vergleich zu einer Lösung, die nur Positionen von vorne und hinten vergleicht.

Hinweise

Hinweis zu Aufgabe a)
Was liefert der Stapel zuerst, was die Schlange?
Hinweis zu Aufgabe b)
Zwei Schleifen: einfügen, dann vergleichen. Bei Unterschied sofort False.
Hinweis zu Aufgabe c)
Speicherbedarf und Anzahl der Vergleiche.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Die Schlange liefert die Zeichen in Originalreihenfolge, der Stapel in umgekehrter. Stimmen alle Paare überein, ist das Wort gleich seiner Umkehrung — also ein Palindrom. Gibt es einen Unterschied, ist es keins.

Erwartungshorizont zu Aufgabe b)
def istPalindrom(w):
    s = Stack()
    q = Queue()
    for i in range(len(w)):
        s.push(w[i])
        q.enqueue(w[i])
    while not s.isEmpty():
        if s.pop() != q.dequeue():
            return False
    return True
Erwartungshorizont zu Aufgabe c)

Der direkte Vergleich von w[i] mit w[Länge − 1 − i] kommt ohne zusätzliche Strukturen aus und braucht nur die Hälfte der Vergleiche. Die Stack-Queue-Lösung braucht zusätzlichen Speicher, zeigt aber die Eigenschaften LIFO und FIFO sehr anschaulich. Für den Einsatz ist der direkte Vergleich effizienter; begründetes Urteil erwartet.