Informatik-Abitur-Wiederholung-Lösungen: Unterschied zwischen den Versionen
Zeile 141: | Zeile 141: | ||
==Normalisierung== | ==Normalisierung== | ||
Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier: <br> | Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier: <br> |
Version vom 6. Februar 2018, 09:24 Uhr
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
- Ü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?
//TODO
Normalisierung
Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier:
Normalisierung
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