Informatik-Abitur-Wiederholung
Auf dieser Seite werden Fragen zusammengestellt, die auf die "Basics" im Informatik-Abitur abzielen.
Die Lösungen finden sich hier: Informatik-Abitur-Wiederholung-Lösungen
Keine Garantie für Vollständigkeit!
Arrays
Standardmethoden für einfache Arrays
Eine Klasse NamensVerwaltung
enthalte als Attribut ein Array namen
:
Index | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
Wert | "Meier" | "Schmidt" | "Müller" | "Franzen" | "Altenburg" |
- Implementiere die Methode
public int anzahl()
. - Implementiere die Methode
public boolean enthaelt(String pName)
. - Implementiere die Methode
public void sortiere()
. Die Methode soll das Array mit einer für Arrays geeigneten Sortiermethode sortieren. Implementiere auch die notwendigen Hilfsmethoden.
Zweidimensionale Arrays
Aufgabe 1
a) Implementiere die Methode public int[][] dasEinmalEins()
.
Die Methode soll die Tabelle des kleinen EinmalEins zurückgeben.
b) Implementiere die Methode public int summe(int[][] tabelle)
Aufgabe 2
Die Beladung eines Containerschiffs wird durch ein zweidimensinales Array von Stacks abgebildet:
private Stack<Container>[][] beladung;
Jetzt soll von jedem Stack der oberste Container (wenn es einen gibt) runtergenommen und auf einen Güterzug verladen werden. Implementiere dafür die Methode
private List<Container> obersteContainerRunterNehmen();
Die Methode gibt in einer Liste alle runtergenommenen Container zurück.
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:
PriorityQueue
erbt vonList
PriorityQueue
erbt vonQueue
PriorityQueue
hat ein Objekt vom TypList
PriorityQueue
hat ein Objekt vom TypQueue
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.
- Entscheide dich begründet für eine Datenstruktur für die 40 Felder des Monopoly-Spiels.
- Zeichne ein Klassendiagramm mit den Klassen
MonopolyFeld
,Strasse
undBahnhof
und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die KlassenStrasse
,Bahnhof
und die von dir eingeführte Klasse auch die Attribute und Methoden an.
Medienplayer
Szenario:
Ein Medienplayer kann die Titel, die man hören möchte, in Wiedergabelisten verwalten. Folgende typische Operationen sollen im Modell enthalten sein:
- Für einen Titel werden der Name, der Interpret und die Länge in Sekunden gespeichert. (Um die Speicherung der Audio-Daten kümmert sich diese Modellierung nicht.)
- Ein Titel kann an einer beliebigen Position der Wiedergabeliste (d. h. am Anfang, am Ende oder an einer Stelle innerhalb der Liste) eingefügt werden. Ebenso kann ein beliebiger Titel aus der Liste gelöscht werden.
- Das Abspielen der Wiedergabeliste beginnt beim ersten Titel. Dann werden alle Titel nacheinander abgespielt. Man kann das Abspielen stoppen. Und man kann wieder an den Anfang der Wiedergabeliste gehen.
- In einem Medienplayer werden beliebig viele Wiedergabelisten verwaltet. Jede Wiedergabeliste hat einen Namen. Der Medienplayer kann immer nur eine aktive Wiedergabeliste haben. Die aktive Liste kann abgespielt werden.
- Im Medienplayer kann man eine Wiedergabeliste auswählen, indem man ihren Namen angibt. Man kann auch neue Wiedergabelisten anlegen, indem man einen Namen angibt. Und man kann die gerade aktive Wiedergabeliste löschen.
- Beim Abspielen einer Wiedergabeliste fragt der Medienplayer immer den nächsten Titel von der aktiven Wiedergabeliste an.
Aufgabe:
Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen. Begründen Sie auch, ob Sie sich für Stack
, Queue
oder List
entscheiden.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse
Queue
. - Implementiere die folgenden Methoden:
public boolean isEmpty()
public void enqueue(Object pObject)
public void dequeue()
public Object top()
- Die Klasse
Node
ist dabei transparent. Erläutere, was das bedeutet.
eine Liste durchlaufen
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.
public Bibliothek()
: Der Konstruktor erzeugt eine Bibliothek; diebuecherListe
ist zu Anfang leer. Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...public boolean enthaelt(String pTitel)
public void einfuegen(Buch pBuch)
: FügtpBuch
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.
Quicksort
- Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E".
- Implementiere die Methode
public List quicksort(List pBuchstaben)
. - Welchen Vorteil hat Quicksort gegenüber einfachen Sortierverfahren wie Selectionsort oder Bubblesort?
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.
- In der Datenbank soll nur der aktuelle Zustand gespeichert werden, d.h. es wird nur festgehalten, welcher Mitarbeiter den Dienstwagen gerade hat.
- In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.
Relationales Datenmodell
- Übertrage das Modell rechts in ein relationales Datenmodell.
- Erläutere, wie die Relation
belegt
in das relationale Datenmodell übertragen wird. Verwende die wesentlichen Fachbegriffe. - Was wäre die Konsequenz, wenn die Tabelle
belegt
als Primärschlüssel ein Attributid
hätte?
Normalisierung
- Benenne die Anforderungen der 1., 2. und 3. Normalform.
- 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)
- Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.
- Überführe nötigenfalls schrittweise in 3. Normalform.
SQL
- Die SQL-Aufgaben beziehen sich auf die Datenbank Schule.
- Testen kann man SQL-Abfragen auf der Datenbank Schule hier.
Die Zugangsdaten gibt's bei Herrn Kaibel
- Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
- Eine Liste der Räume, in denen die 8B Unterricht hat.
- Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
- "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am meisten Stunden unterrichtet.
Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.id - Disziplinarkonferenz für Schüler Schmidt: Eingeladen werden seine Fachlehrer und alle Klassenlehrer.
- In welchen Räumen findet nie Sport statt?
- Welche Schüler sind Klassenkameraden von Anne Ebert?
- Eine Liste ALLER Schüler, aus der hervorgeht, in welcher Klasse sie jeweils sind. Auch Schüler ohne Klasse (z.B. Wiesenhoff) sollen aufgeführt werden.
- Eine Liste der Schüler, die keine Klasse haben.
- Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.
Automaten
Deterministische / Nicht-Deterministische Endliche Automaten
- 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.
- Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.
- Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort LOL enthält.
- Zeichne dafür den Übergangsgraph eines Nicht deterministischen endlichen Automaten.
- Erläutere, warum die zugrunde liegende Sprache regulär ist.
Reguläre Grammatik
- Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?
- 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.
- Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält.
- Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält.
- Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben.
- Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende.
Binärbäume
Preorder, Inorder und Levelorder
Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren.
- Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an.
- Inwiefern ergibt Levelorder eine sinnvolle Reihenfolge?
- Für welche Bäume ergibt Inorder eine sinnvolle Anordnung?
- Wie kann man den Inorder-Durchlauf ganz einfach ablesen?
rekursive Methoden
- Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
- Implementiere die Methode
public List preorder(BinaryTree pTree)
.
Pfaddurchlauf
- Benenne für den Ahnenbaum (s. rechts) eine Methode, die sich mithilfe eines Pfaddurchlaufes realisieren lässt und implementiere sie.
- Erläutere die Implementationsstrategie beim Pfaddurchlauf.
Levelorder
- Implementiere die Methode
public List levelorder(BinaryTree pTree)
für den Ahnenbaum. - Erläutere die Strategie von Levelorder anhand der Implementierung.
Binäre Suchbäume
- Erläutere die Struktur eines Binären Suchbaumes.
- Welche Rolle spielt Inorder in einem binären Suchbaum?
Implementierung von binären Suchbäumen
Es soll eine Klasse Bibliothek
realisiert werden, in der die Bücher in einem Attribut buecherBaum
vom Typ BinarySearchTree
gespeichert werden.
- Zeichne ein Implementationsdiagramm mit den Klassen
Bibliothek
,Buch
und der SchnittstelleItem
- Welche Funktion erfüllt die Schnittstelle
Item
in diesem Zusammenhang? - Implementiere die Klasse
Buch
. - Implementiere für die Klasse
Bibliothek
die folgenden Methoden:public void einfuegen(Buch pBuch)
public Buch finde(String pTitel)
: Findet ein Buch nach dem Titel; gibt das Buch bzw. null zurück.