Lernkarten

Karten 106 Karten
Lernende 8 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 15.01.2013 / 10.02.2020
Lizenzierung Kein Urheberrechtsschutz (CC0)
Weblink
Einbinden
0 Exakte Antworten 106 Text Antworten 0 Multiple Choice Antworten

1/106

Fenster schliessen

Welche vier Durchlaufstrategien gibt es bei Bäumen?

Es wird zwischen vier möglichen Strategien, den Baum systematisch zu durchlaufen, unterschieden:

  • pre-order: wir untersuchen zuerst den betrachteten Knoten, dann den linken und dann den rechten Nachfolger;

  • post-order: wir besuchen zuerst den linken Nachfolger, dann den rechten Nachfolger und schließlich den betrachteten Knoten;

  • in-order: hierbei besuchen wir zuerst den linken Nachfolger, dann den betrachteten Knoten und schließlich den rechten Nachfolger;

  • level-order: zuerst werden alle Knoten auf einer Ebene untersucht, dann alle Nachfolgerknoten jedes Knotens der betrachteten Ebene von links nach rechts.

 

Die in-order-Strategie kann lediglich bei binären Bäumen verwendet werden. Alle anderen Strategien können auch bei anderen Bäumen angewendet werden.

Die von uns gezeigten Durchlaufstrategien bevorzugen ein links-nach-rechts-Verfahren. Wir hätten ebenso ein rechts-nach-links-Verfahren vorschlagen können, doch der Durchlauf von links nach rechts ist der Standard.

Fenster schliessen

Durchlaufen Sie die beiden in der Abbildung  dargestellten Bäume mit der pre-order-, post-order- und level-order-Strategie und geben Sie jeweils an, in welcher Reihenfolge die Knoten besucht werden. Durchlaufen Sie den binären Baum außerdem auch mit Hilfe der in-order-Strategie.

linker Baum:

pre-order: 5, 2, 9, 0, 1, 4, 7, 3, 6, 8

post-order: 9, 0, 4, 1, 2, 7, 6, 8, 3, 5

level-order: 5, 2, 7, 3, 9, 0, 1, 6, 8, 4

rechter Baum:

pre-order: 6, 2, 1, 3, 5, 8, 7, 4, 9

post-order: 3, 5, 1, 2, 7, 9, 4, 8, 6

level-order: 6, 2, 8, 1, 7, 4, 3, 5, 9

in-order: 2, 3, 1, 5, 6, 7, 8, 9, 4

Fenster schliessen

Was sind in Java Binärbäume?

 

Binäre Bäume sind Datenstrukturen, die in jedem Knoten einen Eintrag speichern und deren Knoten einen maximalen Ausgangsgraf von 2 aufweisen. Ein binärer Baum kann in Java ähnlich wie eine Liste implementiert werden. Bei einem binären Baum muss jeder Knoten jedoch nicht nur einen, sondern zwei Verweise auf seine Nachfolger speichern können.
Fenster schliessen

Definieren Sie die Klasse BinaryTreeNode für unsere Baumknote.

 

public class BinaryTreeNode {    private int entry;    private BinaryTreeNode leftChild;    private BinaryTreeNode rightChild;        public BinaryTreeNode(int e) {        this.entry = e;    }        public BinaryTreeNode(int e, BinaryTreeNode left,                                  BinaryTreeNode right) {        this(e);        this.leftChild = left;        this.rightChild = right;    }        // Getter und Setter    // ...}
Fenster schliessen

Entwerfen Sie die BinaryTree Klasse.

 

public class BinaryTree {    private BinaryTreeNode root;        public BinaryTree() {    }        public BinaryTree(BinaryTreeNode root) {        this.root = root;    }        // Getter und Setter    // ...}
Fenster schliessen

Entwickeln Sie die Anweisungen, um den Baum aus  der Abbildung darzustellen.

 

    BinaryTreeNode a         = new BinaryTreeNode(6, null, new BinaryTreeNode(5));    BinaryTreeNode b         = new BinaryTreeNode(2, new BinaryTreeNode(9), a);    BinaryTreeNode c         = new BinaryTreeNode(1, new BinaryTreeNode(4),                                 new BinaryTreeNode(8));    BinaryTreeNode root = new BinaryTreeNode(7, b, c);    BinaryTree bt = new BinaryTree(root);
Fenster schliessen

Welche Suchmethoden sind bei Binärbäumen anwendbar.

 

Rekursive Methoden sind gut geeignet, einen Baum zu durchsuchen und zu verändern, wenn man eine der ersten drei Durchquerungsstrategien pre-, post-, oder in-order benutzt. Diese Verfahren spiegeln die rekursive Struktur eines Baumes, der aus linken und rechten Unterbäumen besteht, wider.

Im Gegensatz dazu ist die level-order-Durchquerung für ein rekursives Verarbeitungsschema weniger gut geeignet, da sie den Verknüpfungen eines Baums nicht folgt, sondern sie quer durchschneidet.

Fenster schliessen

Wir wollen nun eine Methode printPreorder() in der Klasse BinaryTree implementieren, die die Knoten in der Reihenfolge ausgibt, in der sie mit Hilfe der pre-order-Strategie besucht werden. Auch hier benutzen wir wieder eine private Hilfsmethode.

 

public class BinaryTree {    private BinaryTreeNode root;        // ...        public void printPreorder() {        // start with root        printPreorder(root);    }        private void printPreorder(BinaryTreeNode tn) {        // base case: empty subtree        if (tn == null) {            return;        }        // visit current node        System.out.print(tn.getEntry() + " ");        // visit left child        printPreorder(tn.getLeftChild());        // visit right child        printPreorder(tn.getRightChild());    }}
Fenster schliessen

Entwickeln Sie analog zur Methode printPreorder() die Methoden printInorder() und printPostorder() für die KlasseBinaryTree.

 

public class BinaryTree {    Private BinaryTreeNode root;        / / ...        public void printInorder () {        / / Mit Root starten        printInorder (root);    }        private void printInorder (BinaryTreeNode tn) {        / / Base case: empty Teilbaum        if (tn == null) {            zurück;        }        / / Besuch linke Kind        printInorder (tn.getLeftChild ());        / / Besuch aktuellen Knoten        System.out.print (tn.getEntry () + "");        / / Besuch rechte Kind        printInorder (tn.getRightChild ());    }        public void printPostorder () {        / / Mit Root starten        printPostorder (root);    }        private void printPostorder (BinaryTreeNode tn) {        / / Base case: empty Teilbaum        if (tn == null) {            zurück;        }        / / Besuch linke Kind        printPostorder (tn.getLeftChild ());        / / Besuch rechte Kind        printPostorder (tn.getRightChild ());        / / Besuch aktuellen Knoten        System.out.print (tn.getEntry () + "");    }    }
Fenster schliessen

Entwickeln Sie eine Methode public contains(int x), die überprüft, ob der Baum den Wert x enthält. Geben Sie an, welche Suchstrategie Ihre Methode verwendet.

 

public class BinaryTree {    Private BinaryTreeNode root;        / / ...        public boolean contains (int x) {        Rückkehr enthält (Wurzel, x);    }        private boolean contains (BinaryTreeNode tn, int x) {        / / Base case 1: leere Teilbaum        if (tn == null) {            return false;        }        / / Search in preorder        / / Vergleichen x mit aktuellen Knoten        if (tn.getEntry () == x) {    / / Base case 2: x gefunden            return true;        }        / / Search in der linken und in der rechten Teilbaum        Rückkehr enthält (tn.getLeftChild (), x)                 | | Enthält (tn.getRightChild (), x);    }}
Fenster schliessen

Entwickeln Sie eine Methode public contains(int x), die überprüft, ob der Baum den Wert x enthält. Geben Sie an, welche Suchstrategie Ihre Methode verwendet.

 

public class BinaryTree {    Private BinaryTreeNode root;        / / ...        public boolean contains (int x) {        Rückkehr enthält (Wurzel, x);    }        private boolean contains (BinaryTreeNode tn, int x) {        / / Base case 1: leere Teilbaum        if (tn == null) {            return false;        }        / / Search in preorder        / / Vergleichen x mit aktuellen Knoten        if (tn.getEntry () == x) {    / / Base case 2: x gefunden            return true;        }        / / Search in der linken und in der rechten Teilbaum        Rückkehr enthält (tn.getLeftChild (), x)                 | | Enthält (tn.getRightChild (), x);    }}
Fenster schliessen

Nach welchem Schema ist ein Suchbaum aufgebaut?

Der Wert, der im linken Kind gespeichert ist, ist immer kleiner als der Wert des Elternknotens, und der Wert des rechten Kindes ist immer größer als der Wert des Elternknotens. Ein Baum, dessen Elemente diese Eigenschaft aufweisen, wird auch Suchbaum genannt. In einem solchen Suchbaum kann jedes Element maximal einmal vorkommen.

Fenster schliessen

Zeichnen Sie den Suchbaum, der entsteht, wenn Sie der Reihe nach die Werte 7, 12, 20, 3, 5, 1, 6, 9 einfügen.

Suchbaum

Fenster schliessen

Beschreiben Sie das Verfahren der Tiefensuche.

Bei der Tiefensuche hingegen wird erst ein Nachbar gewählt und anschließend von diesem Nachbarn wieder ein Nachbar ausgewählt. Es wird solange diese Strategie angewendet, bis ein Knoten keine Nachbarn hat oder all seine Nachbarn schon besucht wurden. Ist dies der Fall, geht man einen Schritt zurück und schaut, ob dieser Knoten noch andere unbesuchte Knoten aufweist. Diese Strategie des Zurückgehens wird auch als Backtracking bezeichnet. Bei der Tiefensuche geht man ähnlich wie in einem Labyrinth so lange weiter, bis man in eine Sackgasse gelangt, arbeitet sich dann wieder ein Stück zurück und versucht eine andere Abzweigung. Man sucht also zunächst in der Tiefe des Graphen. Die Abbildung veranschaulicht dieses Vorgehen. Die Nummern zeigen an, in welcher Reihenfolge die Knoten besucht werden.

 

Um eine Breitensuche systematisch durchführen zu können, benötigen wir eine Warteschlange.

1.

Füge den Startknoten in die Warteschlange ein.

2.

Entnehme solange den ersten, also ältesten Knoten aus der Warteschlange, bis du einen unbesuchten erhältst.

3.

Vergleiche den Wert des Knotens mit dem gesuchten Knoten.

4.

Sind sie identisch, so ist der gesuchte Knoten gefunden und die Suche kann beendet werden.

5.

Sind sie nicht identisch, so wird der Knoten als besucht gekennzeichnet.

6.

Füge alle noch nicht besuchten Nachbarn des Knotens in die Warteschlange ein.

7.

Ist die Warteschlange leer, so konnte der Knoten nicht gefunden werden und die Suche kann beendet werden.

8.

Fahre mit Schritt 2 fort.

 

Fenster schliessen

Erläutern Sie der Verfahren der Breitensuche.

Die beiden Verfahren unterscheiden sich darin, in welcher Reihenfolge sie die Knoten durchsuchen. Beide Verfahren müssen speichern, welche Knoten schon besucht wurden, um nicht im Kreis zu laufen. Die BreitensucheBreitensucheBreitensuche betrachtet zunächst alle direkten Nachbarn des aktuellen Knotens. Wenn das gesuchte Element nicht dabei ist, so werden als nächstes die Nachbarn der Nachbarn betrachtet und so weiter. In welcher Reihenfolge die direkten Nachbarn untersucht werden, spielt keine Rolle. Man tastet sich bei der Suche also in der vollen Breite immer weiter vor. Abb.  36.5-1 veranschaulicht dieses Vorgehen. Die Nummern zeigen an, in welcher Reihenfolge die Knoten besucht werden.

 

Für die Tiefensuche können wir das folgende systematische Verfahren verwenden:

1.

Überprüfe ob der aktuelle Knoten der gesuchte Knoten ist.

2.

Sind die Knoten identisch, so ist der gesuchte Knoten gefunden und die Suche kann beendet werden.

3.

Sind sie nicht identisch, so wird der Knoten als besucht gekennzeichnet.

4.

Hat der Knoten keine unbesuchten Nachbarn, so muss die Suche hier erfolgreich abgebrochen werden und zum Vorgänger zurückgekehrt werden.

5.

Wähle einen unbesuchten Nachbarn des aktuellen Knotens aus und suche von dort rekursiv mit diesem Verfahren weiter.

6.

Wird ohne Erfolg vom besuchten Nachbarn hierher zurückgekehrt, so fahre mit Schritt 4 fort.

 

Fenster schliessen

Implementieren Sie eine Methode boolean istEnthalten(String wert, String[] feld), die überprüft, ob die übergebene Zeichenkette im Feld enthalten ist. Was müssen Sie hierbei im Gegensatz zur Implementierung für Felder primitiver Typen beachten?

 

Die Elemente sollten nicht mit ==, sonder mit Hilfe der Methode equals() verglichen werden.

    boolean istEnthalten(String wert, String[] feld) {        if (feld == null) {            return false;        }        for (String s : feld) {            // Wert gefunden?            if (s.equals(wert)) {                return true;            }        }        return false;    }
 

 

Fenster schliessen

Implementieren Sie eine Methode int bestimmeAnzahl(int wert, int[] feld), die zählt,

wie oft der übergebene Wert in dem Feld enthalten ist.

 

 

 

    int bestimmeAnzahl(int wert, int[] feld) {        if (feld == null) {            return 0;        }        int anzahl = 0;        for (int i : feld) {            // Wert gefunden?            if (i == wert) {                anzahl++;            }        }        return anzahl;    }
Fenster schliessen

Gegeben seien die folgenden Klassen

public class Kunde {     // ... } 

public class Rechnung {    

private Kunde rechnungsempfaenger;     // ...  

      

public Kunde liefereRechnungsempfaenger() {        

return this.rechnungsempfaenger;    

}     

public int bestimmeBetragInCent() {       

                // ...    

          }

     // ...

}  

 

public class Rechnungssammlung {    

private Rechnung[] rechnungen;   

      // ...

}

 

Implementieren Sie eine Methode

int bestimmeGesamtbetragAllerRechnungenVon(Kunde k)

in der Klasse Rechnungssammlung, die die Summe aller Rechnungsbeträge dieses Kunden in Cent bestimmt.

 

 

    int bestimmeGesamtbetragAllerRechnungenVon(Kunde k) {        // wenn kein Kunde oder keine Rechnungen vorhanden        if (k == null || rechnungen == null) {            return 0;        }        int betrag = 0;        // alle Rechnungen betrachten        for (Rechnung r : rechnungen) {            // wenn gesuchter Kunde            if (r.liefereRechnungsempfaenger() == k) {                // Betrag dazuaddieren                betrag += r.bestimmeBetragInCent();            }        }        return betrag;    }

 

 

Fenster schliessen

Implementieren Sie eine Methode Rechnung findeTeuersteRechnung() in der Klasse Rechnungssammlung, die die Rechnung mit dem größten Betrag bestimmt.

 

Rechnung findeTeuersteRechnung() {   // wenn keine Rechnungen vorhanden    if (rechnungen == null) {        return null;    }    Rechnung max = null;    // alle Rechnungen betrachten    for (Rechnung r : rechnungen) {        // wenn noch kein Maximum gefunden        // oder aktuelle Rechnung teurer        if (max == null || max.bestimmeBetragInCent()                            < r.bestimmeBetragInCent()) {            // Maximum anpassen            max = r;        }    }    return max;}
Fenster schliessen

Wie können in einem Feld Teilfolgen ermittelt werden?

 

 

Man beginnt damit, den ersten Wert des Feldes mit dem ersten Wert der Zahlenfolge zu vergleichen. Stimmen die Werte überein, vergleicht man anschließend die zweiten Werte und so weiter. Stimmen die Werte nicht überein, so weiß man lediglich, dass die Zahlenfolge nicht beim ersten Element des Feldes beginnend gefunden werden kann. Man beginnt dann mit dem zweiten Element des Feldes und vergleicht es mit dem ersten der gesuchten Folge. Stimmen diese überein, so vergleicht man anschließend das dritte mit dem zweiten und so weiter. Wurde die gesamte Teilfolge gefunden, so kann die Methode beendet werden. Bei der Implementierung müssen wir aufpassen, dass wir nicht auf ungültige Feldelemente zugreifen.

Fenster schliessen

Wie können in einem Feld Teilfolgen ermittelt werden?

 

boolean istTeilfolge(int[] feld, int[] gesuchteFolge) {        // es muss nicht bis zum letzten Element gesucht werden,        // da dort die Folge nicht mehr vollständig vorkommen kann        for (int i = 0; i < feld.length                             - gesuchteFolge.length + 1; i++) {            for (int j = 0; j < gesuchteFolge.length; j++) {                // Vergleiche entsprechende Einträge                if (feld[i + j] != gesuchteFolge[j]) {                    // Zahl an Position j stimmt nicht überein                    // suche bei i+1 weiter                    break;                } else if (j == gesuchteFolge.length - 1) {                    // gesamte Folge wurde gefunden                    return true;                }            }        }        // Teilfolge konnte nicht vollständig gefunden werden        return false;    }
Fenster schliessen

Implementieren Sie eine Methode int bestimmeAnfangdesWorts(char[] feld, String wort), die die Position zurückliefert, ab der das Wort vollständig im Feld gefunden wurde. Wird das Wort nicht vollständig gefunden, so soll -1 zurückgeliefert werden.

 

    int bestimmeAnfangdesWorts(char[] feld, String wort) {        for (int i = 0; i < feld.length - wort.length() + 1; i++) {            for (int j = 0; j < wort.length(); j++) {                // Vergleiche entsprechende Buchstaben                if (feld[i + j] != wort.charAt(j)) {                    // Buchstabe an Position j stimmt nicht überein                    // suche bei i+1 weiter                    break;                } else if (j == wort.length() - 1) {                    // gesamtes Wort wurde gefunden                    return i;                }            }        }        // Wort konnte nicht vollständig gefunden werden        return -1;    }
Fenster schliessen

Wie kann das suchen in großen Datenbeständen beschleunigt werden?

 

Wenn die Datenelemente gemäß einer Ordnungsrelation sortiert werden. Der Suchalgorithmus kann diese Eigenschaft nutzen, um ein bestimmtes Element in der sortierten Menge zu finden.

Fenster schliessen

Schreiben eine Methode, die Aufsteigend ein einfaches Feld sortiert.

 

void sortiereAufsteigend(int[] feld) {        // beginne beim zweiten Element und betrachte         // die Liste bis zum Index i - 1 als sortiert        for (int i = 1; i < feld.length; i++) {            // gehe solange von i nach links            // bis das Element an die richtige            // Stelle gerutscht ist            for (int j = i;  j > 0; j--) {                if (feld[j - 1] > feld[j]) {                    // wenn linkes groesser,                    // vertausche die Elemente                    int temp = feld[j];                    feld[j] = feld[j - 1];                    feld[j - 1] = temp;                   } else {                    // das Element ist                    // an der richtigen Stelle                    break;                }            }        }}
Fenster schliessen

 

Wie viele Vergleichs- und Vertauschungsoperationen benötigt der Algorithmus „Sortieren beim Einfügen“, um das folgende Feld zu sortieren?

    int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21};

Als Vergleich zählt die Auswertung der if-Bedingung.

Wir betrachten die drei Anweisungen im if-Block als eine Vertauschungsoperation.

Es werden 18 Vergleiche und 12 Vertauschungen benötigt.

Fenster schliessen

Entwerfen Sie eine Methode void sortiereAbsteigend(String[] feld), die absteigend ein Feld von Zeichenketten sortiert.

 

   void sortiereAbsteigend(String[] feld) {        // beginne beim zweiten Element und betrachte        // die Liste bis zum Index i - 1 als sortiert        for (int i = 1; i < feld.length; i++) {            // gehe solange von i nach links            // bis das Element an die richtige            // Stelle gerutscht ist            for (int j = i; j > 0; j--) {                if (feld[j - 1].compareTo(feld[j]) < 0) {                    // wenn linkes kleiner,                    // vertausche die Elemente                    String temp = feld[j];                    feld[j] = feld[j - 1];                    feld[j - 1] = temp;                } else {                    // sonst, ist das Element                    // an der richtigen Stelle                    break;                }            }        }    }
Fenster schliessen

Schreiben Sie eine Methode, die ein Feld nach dem klassischer Sortierungsalgorithmus Bubblesort bearbeitet.

 

void bubblesort(int[] feld) {        // es werden  maximal feld.length - 1 Durchläufe benötigt        for (int i = 0; i < feld.length - 1; i++) {            // solange keine Vertauschungen vorgenommen werden            // ist das Feld sortiert            boolean sorted = true;            // Durchlaufe das Feld, in jedem Durchlauf muss            // ein Element weniger berücksichtigt werden            for (int j = 0; j < feld.length - 1 - i; j++) {                if (feld[j] > feld[j + 1]) {                    // wenn linkes größer                    // dann vertausche                    int temp = feld[j];                    feld[j] = feld[j + 1];                    feld[j + 1] = temp;                       // Feld ist nicht sortiert                    sorted = false;                }            }            if (sorted) {                // keine Vertauschungen, Feld ist                 // folglich vollständig sortiert                break;            }        }    }
 
Fenster schliessen

Entwerfen Sie mit Hilfe des Bubblesort-Algorithmus eine Methode void sortiereAufsteigend(Rechnung[] rechnungen), die die Rechnungen aufsteigend nach ihren Beträgen sortiert.

 

void sortiereAufsteigend(Rechnung[] rechnungen) {        // es werden maximal length - 1 Durchläufe benötigt        for (int i = 0; i < rechnungen.length - 1; i++) {            // solange keine Vertauschungen vorgenommen werden            // ist das Feld sortiert            boolean sorted = true;            // Durchlaufe das Feld, in jedem Durchlauf muss            // ein Element weniger berücksichtigt werden            for (int j = 0; j < rechnungen.length - 1 - i; j++) {                if (rechnungen[j].bestimmeBetragInCent()                        > rechnungen[j + 1].bestimmeBetragInCent()) {                    // wenn linkes größer dann vertausche                    Rechnung temp = rechnungen[j];                    rechnungen[j] = rechnungen[j + 1];                    rechnungen[j + 1] = temp;                    // Feld ist nicht sortiert                    sorted = false;                }            }            if (sorted) {                // keine Vertauschungen, Feld ist                // folglich vollständig sortiert                break;            }        }    }
Fenster schliessen

Der Algorithmus „Sortieren durch Auswählen“ (engl. selection sortselection sortselection sort) nimmt am Anfang das komplette Feld als unsortiert an, sucht sich das größte Element unter den unsortierten Elementen und vertauscht es, wenn nötig, anschließend mit dem letzten Element des unsortierten Bereichs.

Im nächsten Schritt gehört das letzte Element nun zum sortierten Bereich. Es wird wiederum das größte Element des unsortierten Bereichs mit dem letzten Element vertauscht, so dass es anschließend zum sortierten Bereich gehört. Der Algorithmus terminiert, wenn der unsortierte Bereich aus einem Element besteht.

Wenden Sie den Algorithmus auf das folgende Feld an und zählen Sie die dabei nötigen Vergleichs- und Vertauschungsoperationen .

    int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21};

Es werden 28 Vergleiche und 6 Vertauschungen benötigt.

Fenster schliessen

Implementieren Sie die Methode void sortiere(double[] feld) so, dass sie das übergebene Feld mit Hilfe des Algorithmus „Sortieren durch Auswählen“ sortiert.

 

void sortiere(double[] feld) {        // suche length-1 mal das Maximum        for (int i = 0; i < feld.length - 1; i++) {            // Position des Maximums            int max = 0;            // Suche das Maximum            for (int j = 1; j < feld.length - i; j++) {                // wenn aktueller Wert größer als Maximum                if (feld[j] > feld[max]) {                    // speichere aktuelle Position                    max = j;                }            }            // setzte das Maximum an die letzte der unsortierten            // Positionen, wenn es dort nicht schon ist            if (max != feld.length - 1 - i) {                double temp = feld[max];                feld[max] = feld[feld.length - 1 - i];                feld[feld.length - 1 - i]  = temp;            }        }    }