Arithmetische Ausdrücke
In dieser recht kurzen Aufgabe von 2007 (nur 2 Seiten + 2 Seiten Anhang) wurde den Schülern zunächst gezeigt, was ein arithmetischer Ausdruck ist und wie man arithmetische Ausdrücke mit Hilfe von Bäumen darstellen kann, die man dann als Termbäume bezeichnet. Hier ein Beispiel, das nicht aus der Abituraufgabe stammt, aber so ähnlich ist:
Termbaum für (1+2) x (3-4)
Aufgaben
Aufgabe 1
Im ersten Teil der ersten Aufgabe sollen die S. allgemein beschreiben, wie ein Binärbaum aufgebaut ist - wohlgemerkt ein Binärbaum und nicht ein binärer Suchbaum! Die Begriffe "Wurzel", "Blatt" und "innerer Knoten" sollen dabei erläutert werden.
Im zweiten Teil der ersten Aufgabe soll dann ein Termbaum mit einem Binärbaum verglichen werden. Ich persönlich finde diese Aufgabenstellung etwas schwammig. Ob die S. von selbst darauf kommen, dass bei einem Termbaum alle Blätter Zahlen enthalten, alle inneren Knoten dagegen Operatoren? Und ob sie merken, dass bei einem Termbaum jeder innere Knoten genau zwei Nachfolger hat, während bei einem normalen Binärbaum auch innere Knoten mit nur einem Nachfolger existieren? Ich glaube das nicht!
Aufgabe 2
Hier sollen die S. einen gegebenen arithmetischen Ausdruck in einen Termbaum überführen. Es wird dann noch der völlig überflüssige Hinweise gegeben, dass die Struktur des Termbaums durch die Klammern im Term eindeutig festgelegt ist - so als ob die S. das vorgegebene Beispiel nicht verstanden hätten.
Aufgabe 3
Im ersten Teil der Aufgabe 3 soll ein Klassendiagramm entworfen werden für eine Klasse Item, mit der die Inhalte eines Baumknotens verwaltet werden können. In den offiziellen Modell-Lösungen werden den S. mehrere Möglichkeiten eingeräumt, zum Beispiel dass ein Objekt der Klasse Item drei verschiedene Attribute hat, das erste für eine int-Zahl, das zweite für einen String (Rechenzeichen) und das dritte für einen Wahrheitswert, der auf true gesetzt wird, wenn es sich um ein Blatt handelt und auf false, wenn es sich um einen inneren Knoten handelt. Aber auch andere Ideen sind möglich.
Im zweiten Teil der Aufgabe 3 sollen die S. erläutern, wie man für die Objekte der Klasse feststellen kann, ob es sich um ein Blatt handelt. Bei der oben genannten ersten Variante ist das wegen der boolean-Variablen überhaupt kein Problem. Eine andere Möglichkeit wäre es, wenn man "nachschauen" würde, ob beide Nachfolger eines Knotens den Wert null haben. Dann muss es sich natürlich um ein Blatt handeln. Streng genommen brächte man nur den linken Nachfolger zu überprüfen, denn ein Termbaum hat definitionsgemäß entweder zwei Nachfolger oder gar keinen.
Aufgabe 4
Hier wird den S. erläutert, was man unter einem Preorder-Durchlauf versteht. Die Prefix-Notation eines Terms erhält man, wenn man den Termbaum des arithmetischen Ausdrucks in der Preorder-Reihenfolge durchläuft. Die S. sollen dann in der eigentlichen Aufgabenstellen die Prefix-Notation eines gegebenen Terms angeben. Im zweiten Teil der Aufgabe sollen sie umgekehrt verfahren, nämlich eine vorgegebene Prefix-Notation in einen Termbaum umwandeln.
Und jetzt kommt endlich mal etwas Programmierarbeit. Im dritten Teil der Aufgabe sollen die S. eine Java-Methode
public String preorder (BinTree pTree)
implementieren!
Aufgabe 5
Und wieder ein anderer Aufgabentyp ist jetzt an der Reihe. Die S. bekommen einen Java-Quelltext einer ominösen Methode
public int was(BinTree pTree)
und sollen analysieren, wie die Methode arbeitet und welchen Wert sie berechnet.
Anlagen
Als Anlage bekommen die S. eine Dokumentation der Methoden der Klasse BinTree zur Verfügung gestellt.