Informatik-Abitur-Wiederholung: Unterschied zwischen den Versionen
Zeile 265: | Zeile 265: | ||
==Dijkstra-Algorithmus== | ==Dijkstra-Algorithmus== | ||
Ermittle mithilfe des Dijkstra-Algorithmus den kürzesten Weg von Kassel nach Bremen. | |||
=Backtracking= | =Backtracking= |
Version vom 5. April 2018, 12:06 Uhr
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 für die Beziehungen zwischen den Klassen. Begründen Sie auch, ob Sie sich für Stack
, Queue
oder List
entscheiden.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Objektdiagramms eine Implementationsstrategie für die Methode
public void enqueue(ContentType pContent)
. - 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.
Berücksichtige, dass in der Datenbank auch Reservierungen für die Zukunft gespeichert werden sollen.
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 - Eine Liste aller Schüler und Lehrer.
- 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.
Parser
Programmiere einen Parser für die folgende Sprache:
Akzeptiert wird jedes Wort beliebiger Länge, das genau ein a und mindestens ein b enthält.
(Es lohnt sich, vorab einen Automaten zu zeichnen!)
Kellerautomat, kontextfreie Grammatik, Parser für Kellerautomat
- Warum gibt es für die Sprache L = {anbn} keinen deterministischen endlichen Automaten?
- Zeichne einen Kellerautomat für die Sprache
- Notiere eine kontextfreie Grammatik für die Sprache.
- Implementiere einen Parser für die Sprache.
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?
- Die Klasse
BinarySearchTree
kann implementiert werden, indem man die (fertige!) KlasseBinaryTree
verwendet.- Welche Beziehung besteht zwischen den beiden Klassen? Begründe.
- Implementiere die Methoden
insert
undsearch
.
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.
Graphen
Tiefendurchlauf
Verständnisaufgabe:
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die weniger weit entfernt ist.
Welcher Traversierungsmethode beim Binärbaum entspricht der Tiefendurchlauf? Warum? Wie zeigt sich das an der Implementierung?
Implementierungsaufgabe:
Gesucht ist eine Liste aller Knoten, die sich vom Knoten startKnoten
aus mit 3 Kanten erreichen lassen.
D.h. zu implementieren ist eine Methode
public List<Vertex> findeKnoten(Vertex pStart, int pAnzahl)
Diese Methode wird dann wie folgt aufgerufen:
List<Vertex> ergebnis = findeKnoten(startKnoten,3);
(Der Graph soll in einem Attribut graph
gespeichert sein.)
Breitendurchlauf
Verständnisaufgabe:
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die weniger weit entfernt ist.
Welcher Traversierungsmethode beim Binärbaum entspricht der Breitendurchlauf? Warum? Wie zeigt sich das an der Implementierung?
Implementierungsaufgabe:
Implementiere die Methode
public List<Vertex> breitendurchlauf(String pStadt)
Beachte: Im Parameter wird ein String
angegeben!
Dijkstra-Algorithmus
Ermittle mithilfe des Dijkstra-Algorithmus den kürzesten Weg von Kassel nach Bremen.
Backtracking
Das Rucksackproblem
In einen Container können 500kg gepackt werden. Es gibt folgende Gewichte:
47.347, 55.734, 33.878, 11.321, 99.960, 42.316, 20.764, 52.945, 65.182, 83.339, 94.084, 68.415, 50.309, 70.037, 85.085
Jetzt sollen Gewichte so ausgewählt werden, dass die 500kg möglichst gut ausgenutzt werden, ohne dass die 500kg überschritten werden.
Die optimale Lösung ist in diesem Fall übrigens 499.983, d.h. ziemlich nah dran...
- Erläutere, wie man das Problem mit Backtracking lösen kann.
Gib dabei auch an, welche Informationen man in Attributen speichern muss.
Kryptographie
Diffie-Hellmann-Verfahren
//TODO
Diffie-Hellmann soll man ja auch mathematisch durchrechnen können.
Wenn das kommt, dann wird dafür wird eine Liste von geeigneten Primzahlen / Primitivwurzeln angegeben.
RSA-Verfahren
Das RSA-Verschlüsselungsverfahren verwendet Zahlen.
- Welche Zahlen braucht man, um eine Nachricht zu verschlüsseln?
- Welche Zahlen braucht man, um eine Nachricht zu entschlüsseln?
- Warum kann jemand, der eine Nachricht mit RSA verschlüsselt, diese nicht wieder entschlüsseln?
Es soll jetzt eine Java-Klasse RSA
programmiert werden, mit der man Nachrichten verschlüsseln und entschlüsseln kann.
In der Klasse soll es eine Methode verschluessele(...)
und eine Methode entschluessele(...)
geben.
- Welche Parameter und Rückgabetypen müssen diese Methoden haben?
- Welche Attribute muss die Klasse
RSA
haben?
Datenschutz
Eine gemeinnützige Studienstiftung bietet Stipendien für besonders gute Abiturienten an.
Um den Abiturienten fächerspezifisch geeignete Angebote machen zu können, hätte die Studienstiftung gerne eine Liste der besonders guten Abiturienten (Schnitt: besser als 1,3) mit folgenden Einträgen:
- Name
- Vorname
- Adresse
- Englisch-Note
- Deutsch-Note
- Mathematik-Note
- Informatik-Note
- Durchschnittsnote
Erörtern Sie diese Anfrage unter datenschutzrechtlichen Aspekten.
Schlagen Sie ggf. ein datenschutzrechtlich besseres Verfahren vor. (Das Verfahren sollte pragmatisch sein.)