Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 46114 2005 | Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (Unterrichtsfach) Einzeiprüfung: Algerithmen/Datenstrukt./Progr.-meth. Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 5 Bitte wenden! Herbst 2005 Einzelprüfungsnummer: 46114 Seite: 2 Thema Nr. 1 Aufgabe 1: Algorithmen und Datenstrukturen Sei G ein gerichteter Graph. Die Transposition von G hat dieselben Knoten wie G, aber alle Kanten sind entgegengesetzt ausgerichtet. Bei der Darstellung von Graphen durch Adjazenzlisten wird za jedem Knoten die Liste der benachbarten Knoten angegeben. a) Zeichnen Sie einen gerichteten Graphen mit mindestens 5 Knoten und 10 Kanten und geben Sie dessen Repräsentation durch Adjazenzlisten an! b) Entwerfen Sie ein Verfahren, welches die Transposition eines durch Adjazenzlisten gegebenen Graphen in ebendieser Form bestimmt! Beschreiben Sie das Verfahren detailliert, z.B. durch Angabe von Pseudocode! c) Geben Sie die Komplexitat Ihres Verfahrens unter Verwendung der O-Notation als Funktion der Knotenzahl m und der Kantenzahl n an! d) Beschreiben Sie nun ein Verfahren, welches zu zwei Knoten s, tin einem durch Adjazenzlisten gegebenen Graphen feststellt, ob t von s aus erreichbar ist, und, falls ja, die Länge des kürzesten verbindenden Pfades angibt! Geben Sie auch hier die Zeitkomplexität in der unter c) beschriebenen Form an! Aufgabe 2: Objektorientierter Entwurf Im Betriebssystem Phindows gibt es vier Arten von Dateien, die jeweils die angegebenen Attribute haben: - Text: Name, Größe, Anzahl der Zeilen, Verzeichnis. Das Suffix einer Text-Datei ist .txt - HTML: Name, Größe, Anzahl der Zeilen, Titel, Verzeichnis. Das Suffix einer HTML-Datei ist ‚htm oder ‚html , - GIF: Name, Größe, Breite, Höhe, Verzeichnis. GIF-Dateien haben das Suffix .gif - Verzeichnis: Name, Verzeichnis, enthaltene Dateien. Verzeichnisse haben entweder kein Suffix oder eines, welches von den bisher genannten verschieden ist. Das, Attribut "Verzeichnis" gibt jeweils das Verzeichnis an, in dem sich eine Datei befindet. Bei den folgenden Teilaufgaben können Sie statt des objektorientierten Pseudocodes auch Java verwenden. Aus dem Pseudocode muss insbesondere die Schnittstelle Ihrer Methoden (also Klassenzugehörigkeit, Anzahl und Typ der Parameter, Typ des Rückgabewertes) eindeutig hervorgehen. Außerdem muss das intendierte Verhalten aller von Ihnen geschriebenen Methoden dokumentiert sein! Fortsetzung nächste Seite! Herbst 2005 Einzelprüfungsnummer: 46114 Seite: 3 qd) Modellieren Sie diese Situation in UML. Schreiben Sie objektorientierten Pseudocode für eine Methode, die zu gegebenem Namen eine Datei der entsprechenden Art anhand des Suffixes bildet. Zugriffspfade sind in Phindows durch „|“ getrennte Listen von Dateinamen, etwa „|home |user|test.txt“ Schreiben Sie objektorientierten Pseudocode für eine Methode, die zu einer gegebenen Datei den vollständigen Zugriffspfad als Zeichenkette ausgibt. In Phindows beginnen alle Pfade bei einem Wurzelverzeichnis (im Beispiel home), das sich selbst als Verzeichnis hat. Schreiben Sie objektorientierten Pseudocode für eine Methode, die in einem gegebenen Verzeichnis und all seinen Unterverzeichnissen nach einer Datei eines gegebenen Namens sucht! Herbst 2005 Einzelprüfungsnummer: 46114 Seite: 4 Thema Nr. 2 Aufgabe 1 Gegeben seien die Schlüsselwerte (3, 5,11, 8, 4, 1, 12, 7, 2, 6, 10, 9) a) Generieren Sie den binären Suchbaum, der durch sukzessives Einsetzen dieser Werte entsteht. Gehen Sie dabei von einem leeren Baum aus! b) Geben Sie zu den jeweiligen Knoten die zugehörige Balance ein! Ist der Baum ein AVL-Baum ? c) Generieren Sie wie in a) erneut einen Suchbaum durch sukzessives Einsetzen der gegebenen Werte und stellen Sie nach jedem Schritt die AVL-Eigenschaft wieder her, so dass beim nächsten Einsetzen ein AVL-Baum zugrunde liegt und auch der Baum am Ende ein AVL-Baum ist. d) Stellen Sie jetzt für obige Schlüsselwertmenge einen B-Baum der Ordnung 3 auf! Gehen Sie schrittweise vor, so dass die Vorgehensweise nachvollziehbar ist! Aufgabe 2 Die Backus-Naur-Form kann dazu verwendet werden, die Syntax der Kommandozeilenparameter eines Programms zu beschreiben. Als Beispiel wird das Bildkonvertierungstool convert herangezogen. Mit diesem können die verschiedensten Operationen auf Bilder, welche durch ihre Dateinamen file gegeben sind, ausgeführt werden. Beschreibung (Auszug): Version: ImageMagick 6.0.7 11/03 (04 Y16& http: //www.imagemagick.org Copyright: Copyright (C) 1999-2004 ImageMagick Studio LLC Usage: convert {} file {{} file} {} file ::= -antialias | -contrast | -dither | -monochrome | -normalize Where options include: . -antialias remove pixel -aliasing -contrast enhance or reduce the image contrast -dither apply Floyd/Steinberg error diffusion to image -monochrome transform image to black and white -normalize transform image to span the full range of colors a) Sind folgende Programmaufrufe für die Bilder bildı1.jpg, bild2.jpg und bild3.jpg gültig? Begründen Sie die Antwort! i) convert bildi.jpg -antialias bild2.jpg ii) convert bildl.jpg iii) convert bildi1.jpg bild2.jpg -normalize -monochrome bild3.jpg -dither iv) convert bildl.ipg bild2.jpg -normalize -monochrome bild3.jpg b) Wandeln Sie die Backus-Naur-Form in ein Syntax-Diagramm um! Fortsetzung nächste Seite! Herbst 2005 Einzelprüfungsnummer: 46114 Seite: 5 Aufgabe 3: Gegeben sind folgende Ersetzungsregeln: ::= | + | - ::= | * | / ::= | () | ::=0 |(1[2]3]4]5]6|7|8|9)f0]1|2|3]4|5]6|7|8 9 a) Erstellen Sie ein Syntaxdiagramm zu obigen Ersetzungsregeln! b) Erweitern Sie die Regeln, um das arithmetische Potenzieren darstellen zu können! Verwenden Sie dabei das ” Zeichen für die Potenz a”b © a’. Geben Sie auch die Änderungen am Syntaxdiagramm an! Aufgabe 4 Eine Rechnung besteht aus mehreren Posten, von denen jeder eine Artikelnummer, Anzahl, Einzelpreis und Gesamtpreis enthält. Eine Rechnung ist an eine Person gerichtet und kann mit unterschiedlichen Zahlungsmethoden bezahlt werden. Zahlungsmethoden sind: - Barzahlung, ohne weitere Attribute - ec-Karte mit BLZ und PIN-Nummer - Kreditkarte mit Nummer und Verfallsdatum a) Modellieren Sie den Sachverhalt mit einem ersten UML Klassendiagramm. Geben Sie alle relevanten Beziehungen, Attribute und Methoden an! Begründen Sie Ihre Entwurfsentscheidung! Verwenden Sie hier noch keine Vererbung! b) Geben Sie ein Objektdiagramm, welches eine Situation beschreibt, in der alle Zahlungsmethoden verwendet werden! c) Wenden Sie nun Generalisierung (Vererbung) an, um den Entwurf zu verbessem!