Informatik-Abitur-Wiederholung-Lösungen

Auf dieser Seite finden sich die Lösungen für die Aufgaben der folgenden Seite:

Informatik-Abitur-Wiederholung

Arrays

Standardmethoden für einfache Arrays

1. Implementiere die Methode public int anzahl().
2. Implementiere die Methode public boolean enthaelt(String pName).
3. Implementiere die Methode public void sortiere().

public int anzahl(){
   return namen.length;
}

public boolean enthaelt(String pName){
   for(int i=0; i<namen.length; i++){
      String derName = namen[i];
      if(derName.equals(pName)){
          return true;
      }
   }
   return false;
}

Das Sortieren macht man am besten mit Bubblesort - das geht für Arrays am einfachsten:

public void sortiere(){
   for(int i=0; i<namen.length; i++){
      durchlauf();
   }
}

public void durchlauf(){
   for(int i=0; i<namen.length-1; i++){
      String name = namen[i];
      String naechsterName = namen[i+1];
      if(name.compareTo(naechsterName) > 0){
         tausche(i,i+1);
      }
   }
}

public void tausche(int a, int b){
   String name_a = namen[a];
   String name_b = namen[b];
   namen[a] = name_b;
   namen[b] = name_a;
}

Zweidimensionale Arrays

Aufgabe 1

a) Implementiere die Methode public int[][] dasEinmalEins().

public int[][] dasEinmalEins(){
   int[][] ergebnis = new int[10]10];
   for(int i=0; i<10; i++){
       for(int j=0; j<10; j++){
         ergebnis[i][j] ) i*j;
      }
   }
}

b) Implementiere die Methode public int summe(int[][] tabelle)

 public int summe(int[][] tabelle){
   int ergebnis = 0;
   for(int i=0; i<tabelle.length; i++){
      for(int j=0; j<tabelle[i].length; j++){
         ergebnis += tabelle[i][j];
      }
   }
   return ergebnis;
}

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:

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

Queue bietet nicht ausreichend Funktionalität, denn man muss ein neues Element gemäß seiner Priorität einsortieren können. Das ist bei Queue sehr mühsam.

PriorityQueue erbt von List ist nicht möglich, denn es gibt Methoden der Klasse List, die die Struktur des PriorityQueue zerstören würden! Diese Methoden würde PriorityQueue erben.
Ein Beispiel dafür ist die Methode append: Damit könnte man ein Objekt - unabhängig von seiner Priorität! - einfach hinten anhängen.

Monopoly

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.

//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 und Titel.
• Medienplayer ist die "oberste" Klasse und damit der Ausgangspunkt der Modellierung.
• Medienplayer hat eine Liste mit Inhaltsobjekten vom Typ Wiedergabeliste. List eignet sich besser als Queue oder Stack, weil damit das Auswählen der Wiedergabeliste nach dem Titel einfacher realisiert werden kann.
• Medienplayer hat ein Attribut aktiveWiedergabeliste vom Typ <Wiedergabeliste, in dem die jeweils aktive Wiedergabeliste gespeichert wird.
• WiedergabeListe kann nicht von List erben, weil sie sonst die Methode concat(List pList) zur Verfügung hätte, die im Szenario nicht vorgesehen ist.
• Stattdessen: WiedergabeListe hat eine List mit Inhaltsobjekten vom Typ Titel. Queue oder Stack 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

Implementationsdiagramm Queue

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

1. Implementiere die folgenden Methoden:
   siehe Queue_ab_Abi_2017#Implementierung
2. 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

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.

 public class Bibliothek{

    private List<Buch> buecherListe;

    public Bibliothek(){
       buecherListe = new List<Buch>();
    }

    public boolean enthaelt(String pTitel){
        boolean ergebnis = false;
        for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
           Buch b = buecherListe.getContent();
           if(b.getTitel().equals(pTitel)){
               ergebnis = true;
           }
        }
        return ergebnis;
    }

    public void einfuegen(Buch pBuch){
        for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
           Buch b = buecherListe.getContent();
           if(pBuch.getTitel().compareTo(b.getTitel() < 0){
              buecherListe.insert(pBuch);
              return;
           }
        }
        // die Liste wurde komplett durchlaufen und das Buch nirgendwo eingefuegt!
        buecherListe.append(pBuch);
    }
}

eine Methode erläutern

Erläutere die Methode einfuegen (s.o.) unter Verwendung der wesentlichen Fachbegriffe.

Die Fachbegriffe sind im folgenden unterstrichen.

Die Methode einfuegen hat einen Parameter vom Typ Buch und gibt nichts zurück.

Zuerst wird die buecherListe mit einer for-Schleife komplett durchlaufen.

Dabei wird das jeweils aktuelle Buch in der lokalen Variable b gespeichert und sein Titel mit dem Titel von pBuch verglichen.

Wenn der Titel von pBuch im Alphabet VOR dem Titel von b ist, dann wird pBuch VOR b in die buecherListe eingefügt und die Methode verlassen

Nach dem Ende der Schleife wird pBuch hinten an buecherListe angehängt. Das ist richtig so, denn offensichtlich konnte pBuch in der ganzen Schleife nie eingefügt werden, d.h. pBuch ist das alphabetisch letzte Buch.

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?

//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.
Beachte: In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.

//TODO

Relationales Datenmodell

Die Lösung findet sich hier:
Relationales_Datenmodell

Das endgültige Modell sich hier: Relationales_Datenmodell#n:m-Beziehungen_übertragen

Was wäre die Konsequenz, wenn die Tabelle belegt als Primärschlüssel ein Attribut id hätte?

Dann könnte ein Schüler einen Kurs mehrfach belegen. Das ist aber nicht gewünscht.

Normalisierung

Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier:
Normalisierung

SQL

1. Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
   SELECT u.fach AS fach, SUM(u.stunden) AS stunden
FROM unterricht u
GROUP BY u.fach
ORDER BY stunden DESC
2. Eine Liste der Räume, in denen die 8B Unterricht hat.
   SELECT r.nummer
FROM raum r
JOIN unterricht u
ON u.raum_id = r.id
JOIN klasse k
ON k.id = u.klasse_id
WHERE k.name = '8B'
   Es geht auch ein kartesisches Produkt aus 3 Tabellen mit zwei Abgleichen zwischen den Tabellen.
3. Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
   SELECT k.name, COUNT(s.id) AS anzahl
FROM klasse k, schueler s
WHERE k.id = s.klasse_id
GROUP BY k.id
ORDER BY anzahl DESC
4. "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am wieviele Stunden unterrichtet.
   Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.id
   SELECT l.name, r.nummer, SUM(u.stunden) AS anzahl
FROM lehrer l JOIN unterricht u
ON l.id = u.lehrer_id
JOIN raum r
ON r.id = u.raum_id
GROUP BY l.id, r.id
ORDER BY l.name, r.nummer
5. Eine Liste aller Lehrer und Schüler.
   SELECT l.name
FROM lehrer l
UNION
SELECT s.name
FROM schueler s
6. In welchen Räumen findet nie Sport statt?
   SELECT r.nummer
FROM raum r
WHERE r.id NOT IN
( SELECT u.raum_id
   FROM unterricht u
)
7. Welche Schüler sind Klassenkameraden von Anne Ebert?
   SELECT s.name
FROM schueler s
WHERE s.klasse_id IN
( SELECT s2.klasse_id
   FROM schueler s2
   WHERE s2.name = 'Ebert' AND s2.vorname = 'Anne'
)
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.
   SELECT s.name AS schueler, k.name AS klasse
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id
9. Eine Liste der Schüler, die keine Klasse haben.
   SELECT s.name
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id
WHERE k.id IS NULL
10. Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.
    Danke an Luca und Jan!
    Man braucht hier zwei innere Abfragen: eine für den Sportunterricht und einen für allen Unterricht.
    SELECT k.name, (B.sport/A.gesamt)*100
FROM
( SELECT u.klasse_id as id, SUM(u.stunden) as gesamt
   FROM unterricht u
   GROUP BY u.klasse_id
) AS A ,
( SELECT u.klasse_id as id, SUM(u.stunden) as sport
   FROM unterricht u
   WHERE u.fach = 'Sport'
   GROUP BY u.klasse_id
) AS B , klasse k
WHERE A.id = B.id AND k.id = A.id

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.

//TODO

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.

//TODO

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?

//TODO

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

//TODO

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.

//TODO

Levelorder

1. Implementiere die Methode public List levelorder(BinaryTree pTree) für den Ahnenbaum.
2. Erläutere die Strategie von Levelorder anhand der Implementierung.

siehe Binärbaum#Levelorder-Traversierung_(nur_LK)

Binäre Suchbäume

1. Erläutere die Struktur eines Binären Suchbaumes.
2. Welche Rolle spielt Inorder in einem binären Suchbaum?

//TODO

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.

//TODO

Graphen

Tiefendurchlauf

Gesucht ist eine Liste aller Knoten, die sich vom Knoten startKnoten aus mit 3 Kanten erreichen lassen.

Bei diesem Problem markiert man die Knoten besser nicht, denn es könnte sein, dass man mit einem späteren Nachbarn eine kürzere Strecke zu einem Knoten findet!

  public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl){
     List<Vertex> ergebnis = new List<Vertex>();
     ergebnis.append(pStart);
     if(pAnzahl == 0){
        return ergebnis;
     }
     List<Vertex> nachbarn = graph.getNeighbours(pStart);
     for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
        Vertex n = nachbarn.getContent();
        List<Vertex> ergebnisN = findeKnoten(n, pAnzahl - 1);
        ergebnis.concat(ergebnisN);
     }
     return ergebnis;

Breitendurchlauf

//TODO

Backtracking

Das Rucksackproblem

Folgende Informationen muss man in Attributen speichern:

• die Gewichte, die aktuell im Rucksack sind: aktuelleGewichte
• die Gewichte, die zur bisher besten Lösung gehören: bisherBesteLösung

Bei diesem Backtracking-Problem entspricht jedes der Gewichte einer Stufe.
Für jedes Gewicht (d.h. auf jeder Stufe) hat man zwei Möglichkeiten:

• Das Gewicht in den Rucksack packen,
• Das Gewicht nicht in den Rucksack packen.

Für beide Möglichkeiten muss die Backtracking-Methode rekursiv aufgerufen werden.

Der Algorithmus kann so funktionieren:

rucksackBacktracking(pStufe)
  wenn man eine bessere Lösung gefunden hat:
     dann kopiere aktuelleGewichte in bisherBesteLösung u
  wenn pStufe größer ist als die Anzahl der Gewichte:
     dann verlasse die Methode (denn es kann nicht weiter gehen.)
  packe das Gewicht pStufe in den Rucksack (d.h. füge das Gewicht zu aktuelleGewichte hinzu.)
  rufe rucksackBacktracking(pStufe+1) auf.
  nimm das Gewicht pStufe wieder aus dem Rucksack (d.h. entferne das Gewicht aus aktuelleGewichte.)
  rufe rucksackBacktracking(pStufe+1) auf.
  Jetzt ist nichts mehr rückgängig zu machen, weil man das Gewicht ja schon rausgenommen hat.

Kryptographie

Diffie-Hellmann-Verfahren

//TODO

RSA-Verfahren

Welche Zahlen braucht man, um eine Nachricht zu verschlüsseln?

Man braucht das Produkt zweier großer Primzahlen, d.h. N = p * q , wobei p und q Primzahlen sind. N ist der sogenannte öffentliche Schlüssel.
Die Primzahlen p und q selber braucht man zum Verschlüsseln nicht zu kennnen!
Außerdem braucht man noch eine weitere Zahl e, auf die sich Sender und Empfänger einigen müssen, die aber öffentlich sein kann. (Für e wird häufig 65537 gewählt.)

Welche Zahlen braucht man, um eine Nachricht zu entschlüsseln?

Man braucht die oben genannten Primzahlen p und q. Diese sind der sogenannte private Schlüssel.
Außerdem braucht man die oben genannte Zahl e.

Warum kann jemand, der eine Nachricht mit RSA verschlüsselt, diese nicht wieder entschlüsseln?

Um die Nachricht zu entschlüsseln, müsste er den öffentlichen Schlüssel N in die beiden Primfaktoren p und q (d.h. den privaten Schlüssel) zerlegen können. Das dauert aber bei großen Primzahlen (d.h. 500stellig) selbst mit dem schnellsten Computer mehr als 50 Jahre, d.h. es ist quasi unmöglich.

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?

Beim Verschlüsseln muss man den öffentlichen Schlüssel N und die Nachricht M als Parameter übergeben und erhält als Rückgabe die verschlüsselte Nachricht C.

Beim Verschlüsseln muss man die beiden privaten Schlüssel p und q und die verschlüsselte Nachricht C als Parameter übergeben und erhält als Rückgabe die Nachricht M.

D.h. die Methodenköpfe können so aussehen:

 public int verschluessele(int N, int M)
 public int entschluessele(int p, int q, int C)

(In der Praxis nimmt man nicht int, weil der Zahlenbereich von int bei Weitem nicht ausreicht!
Stattdessen nimmt man Objekte der Klasse BigInteger - die können beliebig lange ganze Zahlen speichern.)

Welche Attribute muss die Klasse RSA haben?

Die Zahl e, auf die man sich geeinigt hat, kann als Attribut gespeichert werden.

Datenschutz

Erörtern Sie diese Anfrage unter datenschutzrechtlichen Aspekten.

Auf der einen Seite kann man vermutlich davon ausgehen, dass alle Schüler an einem Stipendium interessiert sind.

Andererseits werden hier aber personenbezogene Daten und Leistungsdaten abgefragt, ohne dass es dafür eine gesetzliche Grundlage gibt. Deswegen greift hier das Prinzip des Erlaubnisvorbehalts: Solche Daten dürfen nur weitergegeben werden, wenn die betroffenen Personen dem zustimmen - eine solche Zustimmung liegt aber nicht vor.

Deswegen muss die Schule die Anfrage der Studienstiftung ablehnen.

Schlagen Sie ggf. ein datenschutzrechtlich besseres Verfahren vor. (Das Verfahren sollte pragmatisch sein.)

Die Studienstiftung kann der Schule eine Email schicken, die diese an besonders gute Schüler weiterreicht. In der Mail kann ein Link zu einem Online-Formular der Studienstiftung sein, in das der Schüler seine Daten einträgt, seine Zustimmung gibt (und ggf. auch einen Scan des Abiturzeugnisses hochlädt). Die Studienstiftung sollte den Schüler auch um Zustimmung bitten, dass sie seine Angaben der Schule zur Überprüfung vorlegen darf.