Nachklausur

Nachklausur zur Lehrveranstaltung

"Programmierkurs Java"

WS 1996/97

FB Informatik

D. Boles

Nachname: Vorname:

Matrikelnr.:

Fachbereich: Semester:

Verschaffen Sie sich einen kurzen Überblick über die Aufgaben. Beginnen Sie mit den Aufgaben, die Ihnen ein Erfolgserlebnis bringen.

Sie können 100 Punkte erreichen. 50 Punkte reichen zum Bestehen.

Kennzeichnen Sie jedes Lösungsblatt mit Namen und Matrikelnummer.

Legen Sie Ihren Personalausweis und Ihren Studentenausweis neben sich.

Bei Verständnisfragen heben Sie bitte den Arm; das "Aufsichtspersonal" bemüht sich dann um eine Klärung.

Bei Täuschungsversuchen wird Ihre Klausur sofort eingezogen und mit 0 Punkten als nicht bestanden gewertet!

Schreiben Sie leserlich! Nicht lesbare oder unklare Teile werden mit 0 Punkten bewertet.

Denken Sie bei allen Aufgaben - sofern nicht anders angegeben - an die Berücksichtigung von Fehlerfällen, an aussagekräftige Bezeichner und an die Dokumentation komplexer Sachverhalte. Eine Dokumentation gemäß der javadoc-Dokumentationsrichtlinien ist nur bei Aufgabe 1 erforderlich.

Die Fragen beziehen sich immer auf die Programmiersprache Java wie sie in der Vorlesung vorgestellt wurde!

Viel Erfolg !

Aufgabe 1 (Imperative Programmierung): 15 Punkte

Schreiben Sie eine Funktion, die beim Schachspiel eingesetzt werden könnte, und zwar soll mit Hilfe der Funktion überprüft werden, ob sich zwei Damen gegenseitig werfen können (zwei Damen können sich genau dann werfen, wenn sie in derselben Spalte, derselben Reihe oder derselben Diagonale stehen).

Die Funktion soll als Parameter eine quadratische Matrix mit boolean-Werten übergeben bekommen, in der genau zwei Felder den Wert true habe. Die beiden Felder sind die von den Damen besetzten Felder. Die Funktion soll genau dann true liefern, wenn die Damen sich werfen können.

Dokumentieren Sie die Funktion gemäß der javadoc-Dokumentationsrichtlinien.

Aufgabe 2 (Objektorientierte Programmierung) 25 Punkte

In einem Programm soll ein abstrakter Datentyp Menge verwendet werden. Dieser soll es ermöglichen, mit Mengen im mathematischen Sinne umzugehen. Eine Menge soll dabei eine beliebig große Anzahl beliebiger Java-Objekte aufnehmen können, jedes Objekt aber maximal einmal.

Schreiben sie eine Klasse, welche diesen ADT implementiert.

Auf dem Datentypen Menge sollen folgende Funktionen möglich sein:

a) Erzeugen einer neuen leeren Menge.

b) Clonieren einer Menge, d.h. Erzeugen einer neuen Menge aus einer alten (Überschreiben der von der Klasse Object geerbten Methode clone).

c) Überprüfen auf Gleichheit zweier Mengen (Überschreiben der von der Klasse Object geerbten Methode equals).

d) Hinzufügen eines Objektes zu einer Menge.

e) Entfernen eines Objektes aus einer Menge.

f) Überprüfung, ob ein bestimmtes Objekt in der Menge enthalten ist.

g) Schnittmengenbildung zweier Mengen.

h) Vereinigung zweier Mengen.

i) Differenzbildung zweier Mengen.

Geben Sie die Signatur aller Methoden an. Suchen Sie sich dann 4 Methoden aus, die Sie implementieren.

Überlegen Sie sich, wie Ihre Methoden in Fehlerfällen reagieren sollen. Achten Sie auf Lesbarkeit, leichte Änderbarkeit und Erweiterbarkeit Ihrer Klasse. Dokumentieren Sie schwer verständliche Stellen.

Aufgabe 3 (Java und OO Details) 20 Punkte

(a) 5 Punkte

Erläutern Sie die folgenden Begriffe sowie Zusammenhänge bzw. Unterschiede zwischen ihnen:

Objektdeklaration

Objekterzeugung

Objektinitialisierung

(b) 5 Punkte

Wieso liefert der Java-Compiler bei folgendem Programmfragment einen Fehler:

...

public int betrag(int wert) {

if (wert < 0) return -wert;

}

...

(c) 5 Punkte

Welche Ausgabe liefert folgendes Java-Programmfragment? Begründen Sie Ihre Antwort!

public class A {

int i;

public A() { i=0;}

public void set(int i) { i=i; }

public int get() { return i; }

}

...

A a = new A();

a.set(3);

System.out.println(a.get());

...

(d) 5 Punkte

Stellen Sie sich vor, Sie wollen eine Funktion schreiben, die überprüft, ob eine übergebene Funktion f : float -> float Nullstellen besitzt oder nicht. Nun ist es in Java nicht möglich, Funktionstypen zu definieren, d.h. es ist ohne weiteres nicht möglich, einer Funktion als Parameter eine andere Funktion zu übergeben. Wie kann mit Hilfe objektorientierter Konzepte trotzdem eine solche Funktion implementiert werden. Nennen Sie die Konzepte! Skizzieren Sie den Lösungsansatz und die Signatur der Funktion! Sie brauchen die Funktion, d.h. die Nullstellenbestimmung, nicht zu implementieren.

Aufgabe 4 (Programmieraufgabe) 40 Punkte

Stellen Sie sich folgende Situation vor: Es gibt eine Menge von Städten. Einige aber nicht unbedingt alle Städte sind durch Straßen, und zwar ausschließlich Einbahnstraßen, miteinander verbunden. Sie möchten Auskunft darüber bekommen, ob Sie mit dem Auto von einer Stadt zu einer anderen Stadt gelangen können.

Derartige Probleme lassen sich in der Mathematik bzw. Informatik mit Hilfe der Graphentheorie lösen. Die Städte sind Knoten, die Straßen gerichtete Kanten eines Graphen. Es ist zu untersuchen, ob es einen Weg von einem bestimmten Knoten zu einem anderen bestimmten Knoten gibt.

Schreiben Sie ein Java-Programm, das dieses Problem löst. Überlegen Sie sich eine geeignete Repräsentationsform bzw. Datenstruktur für den Graphen, d.h. die Knoten und Kanten. Das Programm soll derart aufgebaut sein, daß der Benutzer zunächst den Graphen eingibt, d.h. Anzahl der Knoten und von welchen Knoten zu welchen anderen eine gerichtete Kante existiert. Anschließend soll es möglich sein, mehrmals einen Ausgangs- und Ankunftsknoten anzugeben, wobei das Programm dann jeweils ausgibt, ob es einen Weg von dem Ausgangs- zum Ankunftsknoten gibt.

Anmerkungen:

Die Effizienz des gewählten Algorithmus spielt keine Rolle (siehe auch Aufgabe 5)

Berücksichtigen Sie fehlerhafte Eingaben des Benutzers und behandeln Sie diese auf eine angemessene Weise.

Zur Eingabe können Sie die aus der Vorlesung bekannte Terminal-Klasse nutzen.

Auszug eines möglichen Dialogs eines Benutzers mit dem Programm:

Grapheingabe

Anzahl Städte: 5

Verbindung von: 1

Verbindung nach: 2

Verbindung von: 2

Verbindung nach: 3

...

Auskunft

Verbindung von: 1

Verbindung nach: 3

Es existiert eine Verbindung!

Verbindung von: 1

Verbindung nach: 4

Es existiert keine Verbindung!

...

Aufgabe 5 (Test) max. 5 Bonuspunkte

Überlegen Sie sich Möglichkeiten, wie die Laufzeiteffizienz des Programms aus Auf-gabe 4 gesteigert werden kann.

Musterlösung

Aufgabe 1

  /**

  * Realisiert eine Ueberpruefung, ob sich zwei Damen beim Schachspiel

  * gegenseitig werfen koennen.

  * @param boolean brett das Schachbrett, es wird vorausgesetzt, dass

  *                      es sich um eine quadratische Matrix handelt und

  *                      dass genau zwei Felder true sind (die Damen)

  * @return true, falls sich die beiden Damen werfen koennen,

  *         ansonsten false

  */

  static boolean werfen(boolean[][] brett) {

    int dame_zeile[] = new int[2];

    int dame_spalte[] = new int[2];

    int dame = 0;

    for (int zeile=0; zeile
      for (int spalte=0; spalte
        if (brett[zeile][spalte]) {

          dame_zeile[dame] = zeile;

          dame_spalte[dame] = spalte;

          dame++;

        }

      }  

    }  

    return (dame_zeile[0] == dame_zeile[1] ||

            dame_spalte[0] == dame_spalte[1] ||

            dame_zeile[1] - dame_zeile[0] == dame_spalte[1] - dame_spalte[0] ||

            dame_zeile[1] - dame_zeile[0] == dame_spalte[0] - dame_spalte[1]

           );

  }

Aufgabe 2

public class Menge {



  protected Object[] elemente;

  protected int groesse;

  protected int anzahl;



  public Menge() {

    this.anzahl = 0;

    this.groesse = 2;

    this.elemente = new Object[this.groesse];

  }



  public Object clone() {

    Menge neue_menge = new Menge();

    neue_menge.vergroessern(this.anzahl);

    for (int i=0; i
      neue_menge.hinzufuegen(this.elemente[i]);

    }

    return neue_menge;

  }



  public boolean equals(Object menge) {

    if (!isMengeClass(menge)) throw new ClassCastException();

    if (this.anzahl != ((Menge)menge).anzahl) return false;

    for (int i=0; i
      if (!((Menge)menge).istElement(this.elemente[i])) return false;

    }

    return true;

  }



  public void hinzufuegen(Object object) {

    if (this.istElement(object)) return;

    if (this.anzahl == this.groesse) {

      this.vergroessern(this.groesse*2);

    }

    this.elemente[this.anzahl++] = object;

  }



  public void entfernen(Object object) {

    for (int i=0; i
      if (this.elemente[i] == object) {

        for (int j=i; j
          this.elemente[j] = this.elemente[j+1];

        }

        this.anzahl--;

        break;

      }  

    }  

  }  



  public boolean istElement(Object object) {

    for (int i=0; i
      if (this.elemente[i] == object) return true;

    }

    return false;

  }



  public static Menge schnittmenge(Menge m1, Menge m2) {

    Menge menge = new Menge();

    for (int i=0; i
      if (m1.istElement(m2.elemente[i])) {

        menge.hinzufuegen(m2.elemente[i]);

      }  

    }  

    return menge;

  }



  public static Menge vereinigung(Menge m1, Menge m2) {

    Menge menge = (Menge)(m1.clone());

    menge.vergroessern(m1.anzahl + m2.anzahl);

    for (int i=0; i
      if (!menge.istElement(m2.elemente[i])) {

        menge.hinzufuegen(m2.elemente[i]);

      }  

    }  

    return menge;

  }



  public static Menge differenz(Menge m1, Menge m2) {

    Menge menge = (Menge)(m1.clone());

    for (int i=0; i
      if (menge.istElement(m2.elemente[i])) {

        menge.entfernen(m2.elemente[i]);

      }  

    }  

    return menge;

  }



  public void print() {

    for (int i=0; i
      System.out.println(this.elemente[i]);

    }

    System.out.println();

  }



  private void vergroessern(int neue_groesse) {

    if (neue_groesse <= this.anzahl) return;

    Object[] speicher = new Object[neue_groesse];

    for (int i=0; i
      speicher[i] = this.elemente[i];

    } 

    this.elemente = speicher;

    this.groesse = neue_groesse;

  }   

 

  private static boolean isMengeClass(Object obj) {

    // ueberprueft, ob obj ein Objekt der Klasse Menge oder einer

    // von Menge abgeleiteten Klasse ist!

    // fuer die Klausur irrelevant!

    Class class_obj = obj.getClass();

    while (!class_obj.getName().equals("Menge") &&

           !class_obj.getName().equals("java.lang.Object")) {

      class_obj = class_obj.getSuperclass();

    }

    return (class_obj.getName().equals("Bruch"));

  }

 

}

Aufgabe 3

Aufgabe 4

import dibo.*;



class InvalidNumberException extends Exception {

  int nummer;

  public InvalidNumberException(int eingabe) {

    this.nummer = eingabe;

  }

}



public class A4 {



  private static int anzahl_staedte = 0;

  private static boolean graph[][];



  public static void main(String[] args) {

    try {



      // zunaechst wird der Graph aufgebaut

      graphAufbauen();



      // dann wird die transitive Huelle berechnet, d.h. im Graph wird

      // explizit gekennzeichnet, welche Verbindungen existieren

      transitiveHuelleBerechnen();



      // Auskuenfte koennen nun direkt in der Matrix nachgeschaut werden

      auskunftGeben();



    } catch (Exception e) {

      System.out.println(e);

      return;

    }

  }  



  private static void graphAufbauen() {

    // Anzahl an Staedten einlesen

    Terminal.out.print("Anzahl Staedte (>0, <100): ");

    anzahl_staedte = Terminal.readInt();

    while (anzahl_staedte <= 0 || anzahl_staedte >= 100) {

      Terminal.out.print("Fehler! Anzahl Staedte (>0, <100): ");

      anzahl_staedte = Terminal.readInt();

    }



    // Graph initialisieren

    graph = new boolean[anzahl_staedte][anzahl_staedte];

    for (int i=0; i
      for (int j=0; j
        if (i==j) {

          // eine Verbindung von einer Stadt zu sich selbst existiert immer

          graph[i][j] = true;

        } else {

          graph[i][j] = false;

        }

      }  

    }  



    // Graph gemaess Nutzereingaben aufbauen

    try {

      int von, nach;

      Terminal.out.println("Graph aufbauen; direkte Verbindungen eingeben!");

      while (true) {

        Terminal.out.print("von: ");

        von = stadtEingeben();

        Terminal.out.print("nach: ");

        nach = stadtEingeben();

        graph[von][nach] = true;

      }  

    } catch (InvalidNumberException e) {

      // der Graph gilt als fertig erstellt, wenn eine ungueltige

      // Stadtnummer eingegeben wurde

      return;

    }

  }  



  private static void transitiveHuelleBerechnen() {

    // Achtung: ein korrekter aber sehr ineffizienter Algorithmus

    // Ueberlegen Sie sich selbst, wie man ihn effizienter machen koennte

    for (int ausgangsstadt=0; ausgangsstadt
      for (int nach=0; nach
        if (ausgangsstadt != nach && graph[ausgangsstadt][nach]) {

          nachfolgerFinden(ausgangsstadt, nach);

        }

      }  

    }  

  }  



  private static void nachfolgerFinden(int ausgangsstadt, int von) {

    for (int nach=0; nach
      if (graph[von][nach] && !graph[ausgangsstadt][nach]) {

        graph[ausgangsstadt][nach] = true;

        nachfolgerFinden(ausgangsstadt, nach);

      }  

    }  

  }  



  private static void auskunftGeben() {

    try {

      int von, nach;

      Terminal.out.println("Auskunft geben; Verbindungen abfragen!");

      while (true) {

        Terminal.out.print("von: ");

        von = stadtEingeben();

        Terminal.out.print("nach: ");

        nach = stadtEingeben();

        if (graph[von][nach]) {

          Terminal.out.println("Verbindung existiert!");

        } else {

          Terminal.out.println("Verbindung existiert nicht!");

        }

      }  

    } catch (InvalidNumberException e) {

      // die Auskunft wird beendet, wenn eine ungueltige

      // Stadtnummer eingegeben wurde

      return;

    }

  }  



  private static int stadtEingeben() throws InvalidNumberException {

    int nummer = Terminal.readInt();

    if (nummer < 0 || nummer >= anzahl_staedte) {

      throw new InvalidNumberException(nummer);

    }

    return nummer;

  }



}

Ergebnisse

Lehrveranstaltung

"Programmierkurs Java"

WS 1996/97

FB Informatik

D. Boles

Die Nachklausur gilt als bestanden, wenn 50 Punkte oder mehr erreicht wurden. Die Scheine können ab Beginn des Sommersemesters 97 im Sekretariat bei Frau Martsfeld (OFFIS, Raum 0 48) abgeholt werden. Einblick in die eigene Klausur ist nur am Mittwoch, den 09.04.97, zwischen 13 und 15 Uhr möglich. Mündliche Nachprüfungen sind am 15. und 16. und 17. Juli, zwischen 9 und 16 Uhr (jeweils eine dreiviertel Stunde) bei D. Boles, OFFIS-Gebäude, Raum O 71 (Tel.: 0441/9722-212, email: boles@informatik.uni-oldenburg.de) möglich. Falls mündliche Nachprüfung erwünscht, bitte bis zum 18.04.97 unten Datum und Uhrzeit (volle Stunde) eintragen.

Matrikelnummer Punktzahl Schein Termin (mündl. Prüfung)

6418120 50 X

6412230 19

6550020 61 X

6573300 39

6505280 24

6433570 41

5941340 39

6535700 20

6512840 23

6551380 37

6434700 40

6484460 20

6161190 32

6503400 40

6505310 29

6558240 69 X

6546500 41

Statistik

Scheine: 3

Keine Scheine: 14

Eine Musterlösung findet sich unter

http://www-is.informatik.uni-oldenburg.de/~dibo/teaching/java/nachklausur.html