Informatik-Abitur-Wiederholung

Aus SibiWiki
Zur Navigation springen Zur Suche springen


Auf dieser Seite werden Fragen zusammengestellt, die auf die "Basics" im Informatik-Abitur abzielen.

Keine Garantie für Vollständigkeit!

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.

lineare Datenstrukturen

eine lineare Datenstruktur implementieren

Implementationsdiagramm Queue
  1. Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse Queue .
  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. Erläutere, welche Rolle Casting hier spielt.

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

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.

  1. In der Datenbank soll nur der aktuelle Zustand gespeichert werden, d.h. es wird nur festgehalten, welcher Mitarbeiter den Dienstwagen gerade hat.
  2. In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.

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.

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.