Informatik-Abitur-Wiederholung-Lösungen

Aus SibiWiki
Zur Navigation springen Zur Suche springen


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!

Medienplayer-beziehungen.png

Implementationsdiagramm: Die einzelnen Klassen

Jetzt werden die einzelnen Klassen mit Attributen und Methoden dargestellt.

Medienplayer-klassen.png

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

//TODO

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.

  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.

//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
  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.
    Man braucht hier zwei innere Abfragen: eine für den Sportunterricht und einen für allen Unterricht.
    Dieses Statement funktioniert noch nicht! Es zeigt nur die 8A an!
    SELECT sport.klasse_name AS klasse,100*SUM(sport.stunden)/SUM(alle.stunden) AS Prozent
    FROM
    ( SELECT k1.id AS klasse_id, k1.name AS klasse_name, SUM(u1.stunden) AS stunden
    FROM klasse k1, unterricht u1
    WHERE k1.id = u1.klasse_id
    AND u1.fach='Sport'
    GROUP BY k1.id
    ) AS sport ,
    ( SELECT k2.id AS klasse_id, k2.name AS klasse_name, SUM(u2.stunden) AS stunden
    FROM klasse k2, unterricht u2
    WHERE k2.id = u2.klasse_id
    GROUP BY k2.id
    ) AS alle
    WHERE sport.klasse_id = alle.klasse_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.

//TODO

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;

Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Informatik-Abitur-Wiederholung-Lösungen&oldid=2601“