Informatik-Abitur-Wiederholung-Lösungen
Auf dieser Seite finden sich die Lösungen für die Aufgaben der folgenden Seite:
Informatik-Abitur-Wiederholung
Arrays
Standardmethoden für einfache Arrays
- Implementiere die Methode
public int anzahl()
. - Implementiere die Methode
public boolean enthaelt(String pName)
. - Implementiere die Methode
public void sortiere()
.
//TODO
Zweidimensionale Arrays
Aufgabe 1
a) Implementiere die Methode public int[][] dasEinmalEins()
.
//TODO
b) Implementiere die Methode public int summe(int[][] tabelle)
Aufgabe 2
private List<Container> obersteContainerRunterNehmen()
{
List<Container> ergebnis = new List<Container>();
for(int i=0; i < beladung.length; i++){
for(int j=0; j < beladung[i].length; j++)
{
Stack<Container> aktuellerStapel = beladung[i][j];
if( ! aktuellerStapel.isEmpty() )
{
Container oberster = aktuellerStapel.top();
ergebnis.append(oberster);
aktuellerStapel.pop();
}
}
}
}
Modellierung
PriorityQueue
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
//TODO
Monopoly
- 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.
//TODO
Medienplayer
Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen. Begründen Sie auch, ob Sie sich für Stack
, Queue
oder List
entscheiden.
Analyse
Bei der Analyse schreibt man formelhaft Begründungen für die Beziehungen der Klassen:
- Aus dem Szenario ergeben sich die Klassen
Medienplayer
,Wiedergabeliste
undTitel
. Medienplayer
ist die "oberste" Klasse und damit der Ausgangspunkt der Modellierung.Medienplayer
hat eine Liste mit Inhaltsobjekten vom TypWiedergabeliste
.List
eignet sich besser alsQueue
oderStack
, weil damit das Auswählen der Wiedergabeliste nach dem Titel einfacher realisiert werden kann.Medienplayer
hat ein AttributaktiveWiedergabeliste
vom Typ <Wiedergabeliste, in dem die jeweils aktive Wiedergabeliste gespeichert wird.WiedergabeListe
kann nicht vonList
erben, weil sie sonst die Methodeconcat(List pList)
zur Verfügung hätte, die im Szenario nicht vorgesehen ist.- Stattdessen:
WiedergabeListe
hat eineList
mit Inhaltsobjekten vom TypTitel
.Queue
oderStack
eignen sich nicht, weil man an beliebigen Stellen einfügen können muss.
Implementationsdiagramm: Beziehung der Klassen
Zuerst werden nur die Beziehungen zwischen den Klassen in einem Diagramm dargestellt.
Attribute und Methoden werden noch nicht dargestellt. Das erleichtert WESENTLICH die Modellierung und das Zeichnen!
Implementationsdiagramm: Die einzelnen Klassen
Jetzt werden die einzelnen Klassen mit Attributen und Methoden dargestellt.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse
Queue
.
Queue verfügt über zwei Attribute vom Typ Node, eins für den Anfang des Queues, eins für das Ende.
In jedem Node ist als value ein Objekt gespeichert. Jeder Node verweist wieder auf den nächsten Node.
- Implementiere die folgenden Methoden:
siehe Queue_ab_Abi_2017#Implementierung - Die Klasse
Node
ist dabei transparent. Erläutere, was das bedeutet.
Wenn man Queues verwendet, muss man über die Klasse Node gar nichts wissen - man weiß ggf. noch nicht einmal, dass es sie gibt. Als Nutzer der Klasse Queue schaut man gewissermaßen durch die Klasse Node hindurch direkt auf die Objekte, die in den Nodes gespeichert sind.
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. Erläutere, welche Rolle Casting hier spielt.
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.
//TODO
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?
//TODO
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.
//TODO
Relationales Datenmodell
Die Lösung findet sich hier:
Relationales_Datenmodell
Das endgültige Modell sich hier: Relationales_Datenmodell#n:m-Beziehungen_übertragen
Was wäre die Konsequenz, wenn die Tabelle belegt
als Primärschlüssel ein Attribut id
hätte?
Dann könnte ein Schüler einen Kurs mehrfach belegen. Das ist aber nicht gewünscht.
Normalisierung
Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier:
Normalisierung
SQL
- Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
SELECT u.fach AS fach, SUM(u.stunden) AS stunden
FROM unterricht u
GROUP BY u.fach - Eine Liste der Räume, in denen die 8B Unterricht hat.
SELECT r.nummer
FROM raum r
JOIN unterricht u
ON u.raum_id = r.id
JOIN klasse k
ON k.id = u.klasse_id
WHERE k.name = '8B'
Es geht auch ein kartesisches Produkt aus 3 Tabellen mit zwei Abgleichen zwischen den Tabellen. - Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
SELECT k.name, COUNT(s.id) AS anzahl
FROM klasse k, schueler s
WHERE k.id = s.klasse_id
GROUP BY k.id
ORDER BY anzahl DESC - "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am wieviele Stunden unterrichtet.
Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.idSELECT l.name, r.nummer, SUM(u.stunden) AS anzahl
FROM lehrer l JOIN unterricht u
ON l.id = u.lehrer_id
JOIN raum r
ON r.id = u.raum_id
GROUP BY l.id, r.id
ORDER BY l.name, r.nummer - Eine Liste aller Lehrer und Schüler.
SELECT l.name
FROM lehrer l
UNION
SELECT s.name
FROM schueler s - In welchen Räumen findet nie Sport statt?
SELECT r.nummer
FROM raum r
WHERE r.id NOT IN
( SELECT u.raum_id
FROM unterricht u
) - Welche Schüler sind Klassenkameraden von Anne Ebert?
SELECT s.name
FROM schueler s
WHERE s.klasse_id IN
( SELECT s2.klasse_id
FROM schueler s2
WHERE s2.name = 'Ebert' AND s2.vorname = 'Anne'
) - 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.
SELECT s.name AS schueler, k.name AS klasse
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id - Eine Liste der Schüler, die keine Klasse haben.
SELECT s.name
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id
WHERE k.id IS NULL - Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.
Man braucht hier zwei innere Abfragen: eine für den Sportunterricht und einen für allen Unterricht.
Dieses Statement funktioniert noch nicht! Es zeigt nur die 8A an!SELECT sport.klasse_name AS klasse,100*SUM(sport.stunden)/SUM(alle.stunden) AS Prozent
FROM
( SELECT k1.id AS klasse_id, k1.name AS klasse_name, SUM(u1.stunden) AS stunden
FROM klasse k1, unterricht u1
WHERE k1.id = u1.klasse_id
AND u1.fach='Sport'
GROUP BY k1.id
) AS sport ,
( SELECT k2.id AS klasse_id, k2.name AS klasse_name, SUM(u2.stunden) AS stunden
FROM klasse k2, unterricht u2
WHERE k2.id = u2.klasse_id
GROUP BY k2.id
) AS alle
WHERE sport.klasse_id = alle.klasse_id
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.
//TODO
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.
//TODO
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?
//TODO
rekursive Methoden
- Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
- Implementiere die Methode
public List preorder(BinaryTree pTree)
.
//TODO
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.
//TODO
Levelorder
- Implementiere die Methode
public List levelorder(BinaryTree pTree)
für den Ahnenbaum. - Erläutere die Strategie von Levelorder anhand der Implementierung.
//TODO
Binäre Suchbäume
- Erläutere die Struktur eines Binären Suchbaumes.
- Welche Rolle spielt Inorder in einem binären Suchbaum?
//TODO
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.
//TODO