Informatik-Abitur-Wiederholung

Auf dieser Seite werden Fragen zusammengestellt, die auf die "Basics" im Informatik-Abitur abzielen.

Keine Garantie für Vollständigkeit!

Modellierung

PriorityQueue

Es soll eine Klasse PriorityQueue erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden public Object getFirst() und public void insert(Object pObject, int pPriority) verfügen. Die Klasse PriorityQueue soll auf der Basis der Klasse List oder Queue implementiert werden.

Entscheide dich für eine der folgenden Möglichkeiten und begründe:

1. PriorityQueue erbt von List
2. PriorityQueue erbt von Queue
3. PriorityQueue hat ein Objekt vom Typ List
4. PriorityQueue hat ein Objekt vom Typ Queue

Monopoly

Bei Monopoly gibt es 40 Felder. Das sind z.T Straßen (wie z.B. die Poststraße) und z.T. Bahnhöfe (wie z.B. der Westbahnhof). Die anderen Felder (wie z.B. Elektrizätswerk, Los, Frei Parken, Gemeinschaftsfeld) werden hier der Einfachheit halber nicht betrachtet. Wenn man auf ein Feld kommt, dann kann man es kaufen, wenn es noch nicht verkauft ist. Wenn man auf einen Bahnhof oder eine Straße eines anderen Spielerst tritt, dann muss man bezahlen. Bei den Straßen hängt das davon ab, wie viele Häuser schon gebaut wurden. Bei den Bahnhöfen hängt es davon ab, wie viele Bahnhöfe der Besitzer hat. Wenn man auf eine eigene Straße tritt, dann kann man ein Haus bauen und muss dafür bezahlen.

1. Entscheide dich begründet für eine Datenstruktur für die 40 Felder des Monopoly-Spiels.
2. Zeichne ein Klassendiagramm mit den Klassen MonopolyFeld, Strasse und Bahnhof und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die Klassen Strasse, Bahnhof und die von dir eingeführte Klasse auch die Attribute und Methoden an.

lineare Datenstrukturen

eine lineare Datenstruktur implementieren

Implementationsdiagramm Queue

1. Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse Queue .
2. Implementiere die folgenden Methoden:
   1. public boolean isEmpty()
   2. public void enqueue(Object pObject)
   3. public void dequeue()
   4. public Object top()
3. Die Klasse Node ist dabei transparent. Erläutere, was das bedeutet.

eine Liste durchlaufen

Klassendiagramm der Klasse Buch

Die Klasse Bibliothek hat ein Attribut buecherListe vom Typ List. In buecherListe sind die Bücher gespeichert und zwar alphabetisch nach Titel sortiert.

Implementiere die folgenden Methoden. Verwende, wenn möglich, eine for-Schleife. Erläutere, welche Rolle Casting hier spielt.

1. public Bibliothek(): Der Konstruktor erzeugt eine Bibliothek; die buecherListe ist zu Anfang leer. Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...
2. public boolean enthaelt(String pTitel)
3. public void einfuegen(Buch pBuch): Fügt pBuch an der richtigen Stelle in die Bibliothek ein.

eine Methode erläutern

Erläutere die Methode einfuegen (s.o.) unter Verwendung der wesentlichen Fachbegriffe.

Ein Beispiel dafür findet sich unter Quelltextanalyse (Java).

Datenbanken

Entity-Relationship-Modellierung

Eine Firma möchte die Ausleihe der Dienstwagen mit einer Datenbank verwalten. Für Mitarbeiter wird Name, Vorname und Telefon gespeichert. Von den Dienstwagen das Kennzeichen und die Anzahl der Sitzplätze. Immer wenn ein Mitarbeiter einen Dienstwagen benötigt, werden das Startdatum und das Enddatum für die Ausleihe gespeichert.

Zeichne ein ER-Modell für die folgenden zwei Fälle. Begründe jeweils die Kardinalitäten.

1. In der Datenbank soll nur der aktuelle Zustand gespeichert werden, d.h. es wird nur festgehalten, welcher Mitarbeiter den Dienstwagen gerade hat.
2. In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.

Relationales Datenmodell

ER-Modell Kurssystem

1. Übertrage das Modell rechts in ein relationales Datenmodell.
2. Erläutere, wie die Relation belegt in das relationale Datenmodell übertragen wird. Verwende die wesentlichen Fachbegriffe.
3. Was wäre die Konsequenz, wenn die Tabelle belegt als Primärschlüssel ein Attribut id hätte?

Normalisierung

1. Benenne die Anforderungen der 1., 2. und 3. Normalform.
2. Erläutere, wie man Verstöße gegen die 1., 2. und 3. Normalform feststellt.

Gegeben ist die folgende Modellierung:

• Kurs(id, bezeichnung, schuljahr, halbjahr, lehrer_kuerzel, lehrer_name)
• Leistung(↑kurs_id, schueler_id, name, vorname, note)

1. Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.
2. Überführe nötigenfalls schrittweise in 3. Normalform.

Automaten

Deterministische / Nicht-Deterministische Endliche Automaten

1. Ein deterministischer endlicher Automat erhält Zahlen als Eingabe. Er soll überprüfen, ob die Zahl durch drei teilbar ist. Dafür überprüft er die Quersumme der Zahl: Ist die Quersumme durch drei teilbar, dann ist auch die Zahl selber durch drei teilbar. Zeichne den Übergangsgraph für diesen deterministischen endlichen Automaten.
2. Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.
3. Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort LOL enthält.
   1. Zeichne dafür den Übergangsgraph eines Nicht deterministischen endlichen Automaten.
   2. Erläutere, warum die zugrunde liegende Sprache regulär ist.

Reguläre Grammatik

1. Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?
2. Das Alphabet der folgenden Sprachen besteht nur aus den Buchstaben a und b. Welche der folgenden Sprachen ist regulär? Begründe. Gib ggf. eine reguläre Grammatik an.
   1. Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält.
   2. Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält.
   3. Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben.
   4. Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende.

Binärbäume

Ahnenbaum: Justus und seine Vorfahren

Preorder, Inorder und Levelorder

Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren.

1. Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an.
2. Inwiefern ergibt Levelorder eine sinnvolle Reihenfolge?
3. Für welche Bäume ergibt Inorder eine sinnvolle Anordnung?
4. Wie kann man den Inorder-Durchlauf ganz einfach ablesen?

rekursive Methoden

1. Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
2. Implementiere die Methode public List preorder(BinaryTree pTree).

Pfaddurchlauf

1. Benenne für den Ahnenbaum (s. rechts) eine Methode, die sich mithilfe eines Pfaddurchlaufes realisieren lässt und implementiere sie.
2. Erläutere die Implementationsstrategie beim Pfaddurchlauf.

Levelorder

1. Implementiere die Methode public List levelorder(BinaryTree pTree) für den Ahnenbaum.
2. Erläutere die Strategie von Levelorder anhand der Implementierung.

Binäre Suchbäume

1. Erläutere die Struktur eines Binären Suchbaumes.
2. Welche Rolle spielt Inorder in einem binären Suchbaum?

Implementierung von binären Suchbäumen

Klassendiagramm der Klasse Buch

Es soll eine Klasse Bibliothek realisiert werden, in der die Bücher in einem Attribut buecherBaum vom Typ BinarySearchTree gespeichert werden.

1. Zeichne ein Implementationsdiagramm mit den Klassen Bibliothek, Buch und der Schnittstelle Item
2. Welche Funktion erfüllt die Schnittstelle Item in diesem Zusammenhang?
3. Implementiere die Klasse Buch.
4. Implementiere für die Klasse Bibliothek die folgenden Methoden:
   1. public void einfuegen(Buch pBuch)
   2. public Buch finde(String pTitel): Findet ein Buch nach dem Titel; gibt das Buch bzw. null zurück.