Aufgaben zur Vorbereitung auf Klausur und Abitur

7. Aufgaben zur Vorbereitung auf Klausur und Abitur#

7.1. Aufgabe#

Welcher abstrakte Datentyp ist jeweils sinnvoll für die folgenden Anwendungen. Entscheide dich zwischen Liste, Stapel, Warteschlange, assoziatives Array und Baum.

  1. Organigramm einer Firma
    Darstellung der hierarchischen Struktur einer Organisation und ihrer Abteilungen.

  2. Verarbeitung von Support-Anfragen
    Anfragen werden in der Reihenfolge bearbeitet, in der sie eingehen.

  3. Undo-Funktion in einem Texteditor
    Schritte rückgängig machen in der Reihenfolge, in der sie durchgeführt wurden.

  4. Produktkatalog mit schnellen Suchfunktionen
    Zuordnung von Produktnamen zu Preisen und Lagerbeständen für schnellen Zugriff.

  5. Dateisystem auf einem Computer
    Organisieren und Speichern von Dateien in einer hierarchischen Struktur.

  6. Navigation im Browser
    Speichern der zuletzt besuchten Webseiten, um bei Bedarf zurückzukehren.

  7. Liste wartender Patienten
    Patienten in einer Reihenfolge verwalten, die (je nach Dringlichkeit) flexibel erweitert und angepasst werden kann.

Lösung:

  1. Baum

  2. Warteschlange

  3. Stapel

  4. Assoziatives Array

  5. Baum

  6. Stapel

  7. Liste

7.2. Aufgabe Verkettete Listen: Objektdiagramm zeichnen#

Für die Produktion des Films “Bibi und Tina (Teil 17)” werden - warum auch immer - alle im Drehbuch vorkommenden Figuren in einer verketteten Liste verwaltet. Der folgende Pseudocode erzeugt diese Liste mit den Klassen und Methoden aus dem Klassendiagram in Abb. 3.3.

Stelle die so entstandene Datenstruktur als Objektdiagramm dar.

Hinweis: Die Klassen Mensch und Pferd sind Unterklassen von Figur. Jedes Figur-Objekt hat ein Attribut name, das beim Erzeugen durch einen Parameter des jeweiligen Konstruktors gesetzt wird.

liste = NEU VerketteteListe<Figur>()
liste.anhaengen(NEU Mensch("Tina"))
liste.anhaengen(NEU Mensch("Bibi"))
liste.einfuegen(1, NEU Pferd("Amadeus"))
liste.einfuegenVorne(NEU Pferd("Sabrina"))
liste.entfernen(2)

Lösung:

../_images/OD_Sabrina_Tina_Bibi.svg

7.3. Aufgabe Verkettete Listen: Operation implementieren#

Implementiere die Methode anhaengen der Klasse VerketteteListe in Pseudocode oder Python, so wie sie im Klassendiagramm in Abb. 3.3 vorkommt.

Lösung:

Pseudocode:

OPERATION anhaengen(pInhalt: Typ) der Klasse VerketteteListe
    Lokale Variablen:  neuerKnoten: Knoten<Typ>, aktuell: Knoten<Typ>
    neuerKnoten = NEU Knoten(pInhalt)
    WENN erster == None:
        erster = neuerKnoten
    SONST
        aktuell = erster
        SOLANGE aktuell.gibNaechsten() != NICHTS
            aktuell = aktuell.gibNaechsten()
        ENDE SOLANGE
        aktuell.setzeNaechsten(neuerKnoten)
    ENDE WENN

Python:

def anhaengen(self, inhalt: Any) -> None:
    """hängt einen neuen Knoten mit dem Inhalt inhalt ans Ende der Liste an"""
    neuerKnoten = Knoten(inhalt)
    if self.erster == None:
        self.erster = neuerKnoten
    else:
        aktuell = self.erster
        while aktuell.gibNaechsten() != None:
            aktuell = aktuell.gibNaechsten()
        aktuell.setzeNaechsten(neuerKnoten)

7.4. Aufgabe Stapel#

Was gibt der folgende Code aus?

s1 = Stapel()
s2 = Stapel()

s1.push("Birne")
s1.push("Apfel")

s2.push("Kirsche")
s2.push("Banane")
s2.push("Erdbeere")

while not s1.ist_leer():
    t = s1.pop()
    s2.push(t)

while not s2.ist_leer():
    print(s2.pop())

Lösung:

Birne
Apfel
Erbeere
Banane
Kirsche

7.5. Aufgabe Binärbaum: Preorder/Postorder/Inorder#

Betrachte den folgenden Baum.

../_images/aufgabe_binbaum_suchbaum_seed40.svg

a) Beantworte die folgenden Fragen:

  1. Wie viele Blätter hat der Baum?

  2. Welche Tiefe hat der Baum?

  3. Wie viele Knoten befinden sich im rechten Teilbaum des linken Teilbaums der Wurzel?

b) Liste alle Elemente des Baums auf in

  • Preorder-

  • Postorder- und

  • Inorder-Reihenfolge.

Lösung:

a)

  • Anzahl Blätter: 7

  • Tiefe: 4

  • Anzahl Knoten im rechten Teilbaum des linken Teilbaums der Wurzel: 6

b)

  • Preorder: 15, 2, 1, 8, 7, 5, 10, 9, 12, 19, 17, 18, 22, 21, 29

  • Postorder: 1, 5, 7, 9, 12, 10, 8, 2, 18, 17, 21, 29, 22, 19, 15

  • Inorder: 1, 2, 5, 7, 8, 9, 10, 12, 15, 17, 18, 19, 21, 22, 29

7.6. Aufgabe Binärbaum: Operation implementieren#

Der folgende Binärbaum soll aufgebaut werden:

../_images/baum_abitur.svg

Nutze die Klassen und Methoden aus Abb. 6.17 um den Baum in Pseudocode oder Python zu erzeugen.

Lösung:

Eher unleserliche Variante der Lösung:

wurzel: Knoten[str] = Knoten("A")
baum = Binärbaum[str](wurzel)

wurzel.setzeLinkenKnoten(Knoten("B"))
wurzel.setzeRechtenKnoten(Knoten("I"))

wurzel.gibLinkenKnoten().setzeLinkenKnoten(Knoten("T"))
wurzel.gibLinkenKnoten().setzeRechtenKnoten(Knoten("U"))

wurzel.gibRechtenKnoten().setzeLinkenKnoten(Knoten("R"))
wurzel.gibRechtenKnoten().setzeRechtenKnoten(Knoten("❤️"))

Schöner ist es so:

# Knoten erstellen
knoten_a: Knoten[str] = Knoten("A")
knoten_b: Knoten[str] = Knoten("B")
knoten_i: Knoten[str] = Knoten("I")
knoten_t: Knoten[str] = Knoten("T")
knoten_u: Knoten[str] = Knoten("U")
knoten_r: Knoten[str] = Knoten("R")
knoten_herz: Knoten[str] = Knoten("❤️")

# Baumstruktur festlegen
baum = Binärbaum[str](knoten_a)

# Ebene 1
knoten_a.setzeLinkenKnoten(knoten_b)
knoten_a.setzeRechtenKnoten(knoten_i)

# Ebene 2
knoten_b.setzeLinkenKnoten(knoten_t)
knoten_b.setzeRechtenKnoten(knoten_u)
knoten_i.setzeLinkenKnoten(knoten_r)
knoten_i.setzeRechtenKnoten(knoten_herz)

7.7. Aufgabe Binärbaum: Rekursion verstehen#

Betrachte den folgenden Baum.

../_images/aufgabe_rekursion_verstehen_seed310347.svg

Was gibt die folgende rekursive Funktion aus, wenn sie mit der Wurzel des Baums als Argument aufgerufen wird? Begründe deine Antwort.

def geheimfunktion(k: Knoten|None) -> int:
    if k is None:
        return 999999999
    tmp1 = geheimfunktion(k.linker_teilbaum)
    tmp2 = geheimfunktion(k.rechter_teilbaum)
    tmp3 = k.inhalt
    ergebnis = tmp1
    if tmp2 < ergebnis:
        ergebnis = tmp2
    if tmp3 < ergebnis:
        ergebnis = tmp3
    return ergebnis

Lösung:

Es wird der Wert 20 ausgegeben.

Erklärung: Durch die if-Anweisungen am Ende der Funktionen wird der kleinste Wert unter tmp1, tmp2 und tmp3 bestimmt. tmp3 ist dabei der Inhalt des aktuellen Knotens, tmp2 und tmp3 speichern dann den kleinsten Wert im linken und rechten Teilbaum. Insgesamt wird also das Minimum aller Werte im Baum bestimmt.

7.8. Aufgabe Binärbaum: Rekursion programmieren#

Ergänze den untenstehenden Code zu einer rekursiven Funktion summe(knoten: Knoten|None), die die Summe aller Werte berechnet, die in dem Baum gespeichert sind.
(Beispiel: Für den Baum aus der vorigen Abbildung müsste die Funktion den Wert 432 als Summe aller Knoteninhalte berechnen.)

def summe(knoten: Knoten|None) -> int:
    """gibt die Summe aller Werte im Baum mit der Wurzel knoten zurück"""
    ...

Lösung:

def summe(knoten: Knoten|None) -> int:
    """gibt die Summe aller Werte im Baum mit der Wurzel knoten zurück"""
    if knoten == None:
        return 0
    return knoten.gibInhalt() + summe(knoten.gibLinkenKnoten()) + summe(knoten.gibRechtenKnoten())
Inhalt