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"

1. Implementiere die Methode public int anzahl().
2. Implementiere die Methode public boolean enthaelt(String pName).
3. 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:

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.

Medienplayer

Szenario:

Ein Medienplayer kann die Titel, die man hören möchte, in Wiedergabelisten verwalten. Folgende typische Operationen sollen im Modell enthalten sein:

1. 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.)
2. 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.
3. 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.
4. 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.
5. 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.
6. 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

1. Erläutere anhand des Objektdiagramms eine Implementationsstrategie für die Methode public void enqueue(ContentType pContent) .
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.

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.

Quicksort

1. Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E".
2. Implementiere die Methode public List quicksort(List pBuchstaben).
3. 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

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.

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

1. Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
2. Eine Liste der Räume, in denen die 8B Unterricht hat.
3. Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
4. "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
5. Eine Liste aller Schüler und Lehrer.
6. In welchen Räumen findet nie Sport statt?
7. Welche Schüler sind Klassenkameraden von Anne Ebert?
8. 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.
9. Eine Liste der Schüler, die keine Klasse haben.
10. Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.

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.

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

1. Warum gibt es für die Sprache L = {aⁿbⁿ} keinen deterministischen endlichen Automaten?
2. Zeichne einen Kellerautomat für die Sprache
3. Notiere eine kontextfreie Grammatik für die Sprache.
4. Implementiere einen Parser für die Sprache.

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?
3. Die Klasse BinarySearchTree kann implementiert werden, indem man die (fertige!) Klasse BinaryTree verwendet.
   1. Welche Beziehung besteht zwischen den beiden Klassen? Begründe.
   2. Implementiere die Methoden insert und search.

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.

Graphen

Deutschlandkarte

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.

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

1. 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.

Implementierungsaufgabe:

Implementiere die Methode

public List<Vertex> breitendurchlauf(String pStadt)

Beachte: Im Parameter wird ein String angegeben!

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.)