Quelltext der Seite Informatik-Abitur-Wiederholung

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]

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 <code>NamensVerwaltung</code> enthalte als Attribut ein Array <code>namen</code>:
{| class="wikitable"
|-
!| Index ||0||1||2||3||4

|-
|<b>Wert</b>|| "Meier" || "Schmidt" || "Müller" || "Franzen" || "Altenburg"
|}

# Implementiere die Methode <code>public int anzahl()</code>.
# Implementiere die Methode <code>public boolean enthaelt(String pName)</code>.
# Implementiere die Methode <code>public void sortiere()</code>. 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 <code>public int[][] dasEinmalEins()</code>.

Die Methode soll die Tabelle des kleinen EinmalEins zurückgeben.

b) Implementiere die Methode <code>public int summe(int[][] tabelle)</code>

===Aufgabe 2===
Die Beladung eines Containerschiffs wird durch ein zweidimensinales Array von Stacks abgebildet:

<code>private Stack<Container>[][] beladung;</code>

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

<code>private List<Container> obersteContainerRunterNehmen();</code>

Die Methode gibt in einer Liste alle runtergenommenen Container zurück.

=Modellierung=

==PriorityQueue==
Es soll eine Klasse <code>PriorityQueue</code> erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden <code>public Object getFirst()</code> und <code>public void insert(Object pObject, int pPriority)</code> verfügen. Die Klasse <code>PriorityQueue</code> soll auf der Basis der Klasse <code>List</code> oder <code>Queue</code> implementiert werden. 

'''Entscheide dich für eine der folgenden Möglichkeiten und begründe:'''
#<code>PriorityQueue</code> erbt von <code>List</code>
#<code>PriorityQueue</code> erbt von <code>Queue</code>
#<code>PriorityQueue</code> hat ein Objekt vom Typ <code>List</code>
#<code>PriorityQueue</code> hat ein Objekt vom Typ <code>Queue</code>

==Monopoly <font color='red'>NICHT im Vorabi</font>==
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 <code>MonopolyFeld</code>, <code>Strasse</code> und <code>Bahnhof</code> und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die Klassen <code>Strasse</code>, <code>Bahnhof</code> 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 <code>Stack</code>, <code>Queue</code> oder <code>List</code> entscheiden.

=lineare Datenstrukturen=

==eine lineare Datenstruktur implementieren==
[[File:Implementationsdiagramm-Queue.png|thumb|Implementationsdiagramm Queue |628px]]
# '''Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse <code>Queue</code> .'''
# '''Implementiere die folgenden Methoden: '''
## <code>public boolean isEmpty()</code>
## <code>public void enqueue(Object pObject)</code>
## <code>public void dequeue()</code>
## <code>public Object top()</code>
# '''Die Klasse <code>Node</code> ist dabei ''transparent''. Erläutere, was das bedeutet.'''


==eine Liste durchlaufen==
[[Datei:Klassendiagramm_Buch.png|405px|thumb|right|Klassendiagramm der Klasse Buch]]

Die Klasse <code>Bibliothek</code> hat ein Attribut <code>buecherListe</code> vom Typ <code>List</code>. In <code>buecherListe</code> sind die Bücher gespeichert und zwar alphabetisch nach Titel sortiert.

'''Implementiere die folgenden Methoden. Verwende, wenn möglich, eine for-Schleife. '''

# <code>public Bibliothek()</code>: Der Konstruktor erzeugt eine Bibliothek; die <code>buecherListe</code> ist zu Anfang leer. ''Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...''
# <code>public boolean enthaelt(String pTitel)</code>
# <code>public void einfuegen(Buch pBuch)</code>: Fügt <code>pBuch</code> an der richtigen Stelle in die Bibliothek ein.

==eine Methode erläutern==
'''Erläutere die Methode <code>einfuegen</code> (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 <code>public List quicksort(List pBuchstaben)</code>.
# 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==
[[File:ER-modell-lehrer-kurs-schueler.png|thumb|ER-Modell Kurssystem |572px]]

# '''Übertrage das Modell rechts in ein relationales Datenmodell.'''
# '''Erläutere, wie die Relation <code>belegt</code> in das relationale Datenmodell übertragen wird. Verwende die wesentlichen Fachbegriffe.'''
# '''Was wäre die Konsequenz, wenn die Tabelle <code>belegt</code> als Primärschlüssel ein Attribut <u><code>id</code></u> 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(<u>id</u>, bezeichnung, schuljahr, halbjahr, lehrer_kuerzel, lehrer_name)
* Leistung(<u>&uarr;kurs_id</u>, <u>schueler_id</u>, 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 '''[http://sibi-wiki.de/informatikag/videodb/index.php hier]'''. <br/>Die Zugangsdaten gibt's bei Herrn Kaibel

[[Datei:Beispieldatenbank-schule.jpg]]

# 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.<br/>''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 <u>Nicht</u> 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=
[[File:Ahnenbaum.png|thumb|Ahnenbaum: Justus und seine Vorfahren|300px]]

==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 <code>public List preorder(BinaryTree pTree)</code>.

==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 <code>public List levelorder(BinaryTree pTree)</code> 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===
[[Datei:Klassendiagramm_Buch.png|405px|thumb|right|Klassendiagramm der Klasse Buch]]
Es soll eine Klasse <code>Bibliothek</code> realisiert werden, in der die Bücher in einem Attribut <code>buecherBaum</code> vom Typ <code>BinarySearchTree</code> gespeichert werden.
# Zeichne ein Implementationsdiagramm mit den Klassen <code>Bibliothek</code>, <code>Buch</code> und der Schnittstelle <code>Item</code>
# Welche Funktion erfüllt die Schnittstelle <code>Item</code> in diesem Zusammenhang?
# Implementiere die Klasse <code>Buch</code>.
# Implementiere für die Klasse <code>Bibliothek</code> die folgenden Methoden:
## <code>public void einfuegen(Buch pBuch)</code>
## <code>public Buch finde(String pTitel)</code>: Findet ein Buch nach dem Titel; gibt das Buch bzw. null zurück.

=Graphen=
==Tiefendurchlauf==
Gesucht ist eine Liste aller Knoten, die sich vom Knoten <code>startKnoten</code> aus mit 3 Kanten erreichen lassen.<br/>

D.h. zu implementieren ist eine Methode

<code>public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl)</code>

Diese Methode wird dann wie folgt aufgerufen:

<code>List<Vertex>ergebnis = findeKnoten(startKnoten,3);</code>

(Der Graph soll in einem Attribut <code>graph</code> gespeichert sein.)