zurück zur Liste

Schweppe-Profil: Fragen und Antworten

Bäume und Graphen

  1. Was für Arten von Bäumen kennen Sie?

    Binärbäume, n-äre Bäume, AVL-Bäume, Rot-Schwarz-Bäume, B-Bäume (Mehrwegbäume)

  2. Wie löscht man aus binären Bäumen?

    Idee: Man ersetzt mit dem größten (rechtesten) Element aus dem linken Teilbaum (oder umgekehrt).
    Lässt sich die Idee nicht sauber implementieren, kann es besser sein, den rechten Teilbaum einfach an das größte Element aus dem linken anzuhängen und dann den Baum wieder auszugleichen.

  3. Implementieren Sie einen binären Baum in Haskell

    data BinTree = E | N BinTree Int BinTree deriving Eq

    insertVal :: BinTree -> Int -> BinTree
    insertVal E i = N E i E
    insertVal (N l v r) i
      | v == i = N l v r
      | v < i = N l v (insertVal r i)
      | otherwise = N (insertVal l i) v r

    delete :: BinTree -> Int -> BinTree (saubere Implementierung)
    delete E i = E
    delete (N l v r) i
      | v < i = N l v (delete r i)
      | v > i = N (delete l i) v r
      | l == E = r
      | r == E = l
      | otherwise = N (delete l (greatestElement l)) (greatestElement l) r
     where greatestElement :: BinTree -> Int
           greatestElement (N l v r)
            | r == E = v
            | otherwise = greatestElement r

    delete :: BinTree -> Int -> BinTree (naive Implementierung)
    delete E i = E
    delete (N l v r) i
      | v == i = insertLeftTree r l
      | v < i = N l v (delete r i)
      | otherwise = N (delete l i) v r
     where insertLeftTree :: BinTree -> BinTree -> BinTree
           insertLeftTree E t = t
           insertLeftTree (N l v r) t = N (insertLeftTree l t) v r

    contains :: BinTree -> Int -> Bool
    contains E i = False
    contains (N l v r) i
      | v == i = True
      | v < i = contains r i
      | otherwise = contains l i

    showT :: BinTree -> String
    showT E = "*"
    showT (N l v r) = "[" ++ showT l ++ "]" ++ " " ++ show v ++" " ++ "[" ++ showT r ++ "]"

    listTree :: BinTree -> [Int]
    listTree E = []
    listTree (N l v r) = v:(listTree l ++ listTree r)

  4. Welche durchschnittliche Höhe hat ein Binärbaum?

    Höhe ist logarithmisch, aber warum? → s. gprot18 Die mittlere Weglänge im Baum ist die Summe der Weglängen zu den Knoten durch die Anzahl der Knoten.
    Die Höhe eines vollständigen binären Baumes wächst nur logarithmisch mit der Knotenzahl.

  5. Implementieren Sie einen Binärbaum in Java (ADT)

    class Node {

      protected Comparable value;
      protected Node left;
      protected Node right;

      public Node(Comparable value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
      }
    }

    public class BinTree implements BinaryTree {

      private Node root;

      public BinTree(Node root) {
        this.root = root;
      }

      public void insert(Comparable value) {

        Node temp = root;
        Node parent = null;

        while (temp != null) {
          parent = temp;
          if (value.compareTo(temp.value) < 0) {
            temp = temp.left;
          }
          else {
            temp = temp.right;
          }
        }

        if (parent != null) {
          if (value.compareTo(parent.value) > 0) {
            parent.right = new Node(value, null, null);
          }
          else {
            parent.left = new Node(value, null, null);
          }
        }
      }
    }

  6. Wann ist ein Binärbaum entartet?

  7. Was ist ein AVL-Baum, welche Vor-und Nachteile hat er gegenüber einem Binärbaum?

  8. Was ist ein B-Baum?

    B-Bäume sind Mehrweg-Suchbäume. Alle Blätter eines B-Baums haben die gleiche Tiefe. (Baum ist vollständig.)
    2-3-Bäume bzw. 2-4-Bäume sind B-Bäume der Ordnung 3 bzw. 4. Die 2 gibt die minimale Anzahl der Kinder pro Knoten an.

  9. Sind B-Bäume binär?

    Nein, es handelt sich ja um Mehrwegbäume. Ein B-Baum kann aber den Aufbau eines Binärbaums haben → jeder Knoten hat höchstens zwei Kinder.

  10. Warum ist ein B-Baum ausgeglichen?

  11. Was ist ein Rot-Schwarz-Baum?

  12. Was sind die zwei wichtigsten Möglichkeiten, um Graphen zu speichern?

    Adjazenzliste (Knotenliste), Adjazenzmatrix

Abstrakte Datentypen & Programmierung

  1. Was sind abstrakte Datentypen, worin liegen ihre Vorteile

    Abstrakte Datentypen beschreiben Wertemengen ausschließlich durch die darauf zulässigen Operationen.
    Datenabstraktion ist die Anwendung des Geheimnisprinzips auf Datenstrukturen. Bestimmte Programmteile sind für den Benutzer nicht sichtbar, bzw. der Zugriff nicht gestattet. Man abstrahiert von der Implementierung und charakterisiert die Datenstruktur über die Operationen auf ihr. (Der Zugriff erfolgt dann nur noch über eine Schittstelle.)

  2. Was ist Polymorphie?

    Man unterscheidet Universelle Polymorphie (mit Inklusions- und Parametrischer Polymorpie) und Ad-hoc-Polymorphie (→ gleiche Funktionsnamen mit verschiedenen formalen Parametern).

  3. Stellen Klassen in Java ADTs dar?

    Können, müssen aber nicht. (→ s. 1.)

  4. Was ist Hashing?

  5. Implementieren Sie eine Menge mit Hashes und offener Adressierung

  6. Was für Parameterübergabe-Mechanismen gibt es?

    Call-by-value, Call-by-reference, Call-by-result (=Call-by-value-return), Call-by-name. (+Erklärung)

  7. Welchen Parameterübergabe-Mechanismus nutzt Java?

    Call-by-value für primitive Datentypen, Call-by-reference für Objekte.

  8. Was ist lazy evaluation?

    Bei der verzögerten Auswertung wird ein Ausdruck erst dann durch seinen Wert ersetzt, wenn er gebraucht wird. Dadurch lassen sich z.B. in Haskell unendlich große Datenstrukturen definieren (liste = 'a':liste). → s. gprot40

  9. Was ist late binding?

    Dynamische Typzuordnung zur Laufzeit (→ Polymorphie)

  10. Was ist das Factory Pattern?

    Ein design pattern zur Entkoppelung von der Implementierung - nur die Funktionalität ist wichtig.

  11. Implemetieren Sie die Fakultätsfunktion in Haskell

    fak 0 = 1
    fak x = x * fak(x-1)

  12. Wie kann man die Fakultätsfunktion noch einfacher implementieren? (→ Endrekursion)

    fak2 x = faka x 1
     where faka 0 a = a
           faka x a = faka (x-1) (a*x)

  13. Wie kann man diese Funktion entrekursieren?

    int fak(int x) {
      int akk = 1;
      while (x > 1) {
        akk = akk * x;
        x--;
      }
    }

Laufzeit

  1. Was ist Laufzeit?

  2. Definition der Laufzeit?

  3. Warum ist die Laufzeit von Quicksort im schlechtesten Fall O(n²)?

  4. Was besagt die Church'sche These?

Algorithmen

  1. Was ist ein Greedy-Algorithmus?

    Das Prinzip des Greedy-Algorithmus ist es, in jedem Teilschritt so viel wie möglich zu erreichen (lokales Optimum). Unter Umständen wird dadurch jedoch das globale Optimum nicht erreicht.(Bsp.: Wechselgeld)

  2. Was ist der Dijkstra-Algorithmus?

    Algorithmus zum finden kürzester Wege in Graphen. (+Erklärung)

  3. Was ist der Kruskal-Algorithmus?

    Algorithmus zum finden des kleinsten aufspannenden Baums. (+Erklärung)

  4. Was ist der Algorithmus von Prim?

    Auch ein Algorithmus zum finden des kleinsten aufspannenden Baums. (+Erklärung)

  5. Was ist der Huffman-Algorithmus?

    Ein Algorithmus zum finden einer optimalen Binärcodierung von Zeichen. Erzeugt wird ein sog. kommafreier Präfixcode. (+Erklärung)

Rekursion

  1. Welche Arten von Rekursion gibt es?

    Linare Rekursion und nicht lineare Rekursion. Bei der linearen Rekursion unterscheidet man noch endrekursive und nicht endrekursive Funktionen.

Spezifikation

  1. Was ist eine Spezifikation und wie kann man Spezifizieren?

    Modellierende / algebraische Spezifikation

  2. Was ist der Nachteil der modellierenden gegenüber der axiomatischen Spezifikation?

    Man legt sich bereits auf eine Implementierung fest.

  3. Spezifizieren Sie einen Stack (algebraisch & modellierend)

  4. Spezifizieren Sie eine Schlange algebraisch

  5. Wie kann man die Korrektheit eines imperativen Programms (Java) beweisen?

    Verifikation mit Hoare Kalkül → Vorbedingung {P} wird in Nachbedingung {Q} überführt.
    {P} S {Q} mit Zuweisungsaxiom {P}x = e{P[e/x]} → alles was vorher für e galt, gilt jetzt für x

  6. Ist der Algorithmus dann korrekt?

    ...partielle Korrektheit nachgewiesen, totale Korrektheit mit Terminierungsfunktion...

  7. Was kann man nicht automatisch beweisen?

    Die Invariante

Sonstiges