Fragen zu Datenstrukturen

Fragen zu Datenstrukturen javafrage Wed, 03/22/2017 - 20:18

1 Binärbäume

1 Binärbäume

Welche der Bäume sind korrekte, streng aufsteigend sortierte Binärbäume? Was sind die Fehler in den nicht korrekten Bäumen?

Geben Sie eine kurze Begründung.

Binärbaum 1 Binärbaum 2
erster Binärbaum zweiter Binärbaum

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 4 Minuten
javafrage Tue, 02/07/2012 - 08:22

2 AVL-Bäume

2 AVL-Bäume

Welche der beiden Bäume sind korrekte AVL-Bäume? Was sind die Fehler in den nicht korrekten Bäumen?

AVL-Baum 1 AVL-Baum 2
 AVL Baum 1 AVL Baum 2 

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 4 Minuten

Antwort zu Frage 1: Binärbäume

Geben Sie eine kurze Begründung.

Binärbaum 1 Binärbaum 2

erster Binärbaum

Dieser Baum ist korrket

zweiter Binärbaum

Dieser Baum ist nicht korrekt. Der Knoten 2 müsste links von 4 eingeordnet sein

javafrage Wed, 02/08/2012 - 08:35

3 Bruderbäume

3 Bruderbäume

Welche der beiden Bäume sind korrekte Bruderbäume? Was sind die Fehler in den nicht korrekten Bäumen? Bitte geben Sie eine kurze Erklärung.

Bruder-Baum 1 Bruder-Baum 2
AVL Baum 1 AVL Baum 2

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 4 Minuten

Antwort zu Frage 2: AVL-Bäume

AVL-Baum 1 AVL-Baum 2

 AVL Baum 1

Der Baum ist ein korrekter AVL-Baum.

AVL Baum 2 

Der AVL-Baum ist inkorrekt. Der Knoten F hat Höhe 3. Die Knoten M,N haben die Höhe 5. Bei AVL Bäumen ist nur ein Höhenunterschied von +/-1 erlaubt.

 

javafrage Fri, 02/10/2012 - 10:41

4 Erweitern eines AVL-Baums

4 Erweitern eines AVL-Baums

Der unten gezeigte Baum ist ein streng aufsteigend, sortierter Binärbaum und gleichzeitig ein AVL-Baum. Die Schlüssel in den Knoten sind ganze, positive Zahlen.
Fügen Sie 6 Knoten in das Diagramm ein.

  • Wählen Sie die Knotenpositionen so, dass der Baum ein AVL-Baum bleibt.
  • Tragen Sie dann die Schlüsselwerte so ein, dass der Baum streng sortiert bleibt.

AVL-Baum für Übungsaufgabe

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 6 Minuten

Antwort zu Frage 3: Bruderbäume

Brudebaum 1 Bruderbaum 2

AVL Baum 1

Der Baum ist ein korrekter Bruderbaum

AVL Baum 2

Der Baum ist kein korrekter Bruderbaum.

Die Knoten L und M haben eine andere Höhe.

javafrage Sat, 01/05/2013 - 14:15

Anonymous (not verified)

Tue, 06/23/2020 - 18:57

Hallo, der rechte Baum wäre doch auch kein Bruderbaum wenn er zwar höhenbalanciert wäre aber nicht alle Söhne die gleiche Höhe hätten. Also der entscheidende Punkt ist ja nicht die Ausgeglichenheit sondern die Höhe der Söhne, oder?
Beste Grüße

5 Definition von Brüdern (bei Brüderbäumen)

5 Definition von Brüdern (bei Brüderbäumen)

Was sind Brüder im Kontext von Brüderbäumen?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 4: Erweitern eines AVL-Baums

Eine mögliche Lösung

 Lösung zur Übungsaufgabe zur Erweiterung eins AVL-Baums

javafrage Sat, 01/05/2013 - 14:30

6 Binär- und Bruderbäume

6 Binär- und Bruderbäume

Wann ist ein Binärbaum ein Bruderbaum? Nennen Sie die Kriterien.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 6 Minuten

Antwort zu Frage 5: Definition Bruder (bei Bruderbäumen)

Knoten die den gleichen Vater besitzen.

javafrage Sat, 01/05/2013 - 14:41

7 Aufwände von Operationen in Listen, Warteschlangen und Bäumen

7 Aufwände von Operationen in Listen, Warteschlangen und Bäumen

Welche Aufwände O(n) haben die folgenden Operationen bei nicht optimierten Implementierungen?

  • Einfügen eines Elements am Kopf einer Liste
  • Suchen eines Elements in einer Liste
  • Finden eines Elements in einem balancierten Baum
  • Finden eines Elements in einem Feld(Array) bei bekanntem Index
  • Finden eines Elements in einem Feld(Array) wenn der Zugriffsindex nicht bekannt ist

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 5 Minuten

Antwort zu Frage 6: Binär- und Bruderbäume

  • Jeder innere Knoten hat einen oder zwei Söhne
  • Jeder unäre Knoten hat einen binären Bruderknoten
  • Alle Söhne haben die gleiche Tiefe
javafrage Tue, 03/18/2014 - 08:36

Anonymous (not verified)

Sat, 05/20/2017 - 13:08

Vielen Dank für die Javafragen!
Sollte der letzte Stichpunkt der Antwort zu Frage 6 und 8 nicht heißen:
- Alle Blattknoten haben die gleiche Tiefe
Bei Fragen 8 und 9 ist mir außerdem aufgefallen, dass die Kommentarfunktion deaktiviert ist.

habe die Kommentarfunktion wieder eingeschaltet. Das gab es mal böse Robots...
Zu den Söhnen. Das passt schon. Jeder Vater hat Söhne mit der gleichen Tiefe. Es können nicht alle Blattknoten im Baum die gleiche Höhe haben. Ein Vater ist immer um eins höher als sein Sohn.

8 Definition Bruderbaum

8 Definition Bruderbaum

Welche drei Bedingungen gelten für einen Bruderbaum?

 

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 6 Minuten

Antwort zu Frage 7: Aufwände von Operationen in Listen, Warteschlangen und Bäumen

  • Einfügen eines Elements am Kopf einer Liste: O(1)
  • Suchen eines Elements in einer Liste: O(n)
  • Finden eines Elements in einem balancierten Baum: O(logN)
  • Finden eines Elements in einem Feld(Array) bei bekanntem Index: O(1)
  • Finden eines Elements in einem Feld(Array) wenn der Zugriffsindex nicht bekannt ist: O(n)
javafrage Tue, 03/18/2014 - 08:47

9 Anforderungen an einen AVL-Baum

9 Anforderungen an einen AVL-Baum

Was gilt für alle Teilbäume eines AVL-Baums?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 8: Definition Bruderbaum

  1. Jeder innere Knoten hat einen oder zwei Söhne
  2. Jeder unäre Knoten hat einen binären Bruderknoten
  3. Alle Söhne eines Vaters haben die gleiche Tiefe
javafrage Tue, 03/18/2014 - 08:57

Anonymous (not verified)

Tue, 06/27/2017 - 11:22

Es sollte bei 3. m.E. heißen: Alle Blätter haben die gleiche Tiefe.
Denn, auch innere Knoten sind Söhne, haben jedoch unterschiedliche Tiefen.

Eine etwaige Änderung müsste auch im Artikel "Bruderbäume" übernommen werden.

10 Bruderbaum korrigieren

10 Bruderbaum korrigieren
Inkorrekter Bruderbaum

Der Baum links, ist mit seinen äusseren Blattknoten (Werte 1 bis 6) streng aufsteigend sortiert.

Warum ist dieser Baum kein Bruderbaum? Geben Sie eine kurze Erklärung.

Zeichnen Sie rechts einen Baum, der ein streng aufsteigend sortierter Bruderbaum ist.

Er soll die gleichen 6 äusseren Blattknoten (Wert 1 bis 6) besitzen.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 6 Minuten

Antwort zu Frage 9: Anforderungen an einen AVL-Baum

Die Höhe des linken Unterbaums unterscheidet sich um maximal 1 von der Höhe des rechten Unterbaums.

javafrage Sat, 02/13/2016 - 17:10

11 Höhenbalancierter Binärbaum

11 Höhenbalancierter Binärbaum
Nicht höhenbalancierter Binärbaum Der links gezeigte Binärbaum ist streng aufsteigend sortiert. Er ist nicht höhenbalanciert.
Transformieren Sie die Knoten dieses Baums so, dass ein höhenbalancierter, streng sortierter Binärbaum der entsteht.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 5 Minuten

Antwort zu Frage 10: Bruderbaum korrigieren

Aufgabe Lösung
 Inkorrekter Bruderbaum Korrekter Bruderbaum 
javafrage Sat, 02/13/2016 - 17:23

12 AVL Baum: Fehler erkennen und korrigieren

12 AVL Baum: Fehler erkennen und korrigieren
Inkorrekter AVL Baum Der links gezeigte streng sortierte Binärbaum ist kein AVL Baum. Warum ist er kein AVL Baum? Geben Sie eine kurze Begründung:

Zeichnen Sie rechts die gleichen Knoten als einen streng aufsteigend, sortierten AVL-Baum ein:

 

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2+4 Minuten

Antwort zu Frage 11: Höhenbalancierter Binärtbaum

Aufgabe Lösung
 Nicht höhenbalancierter Binärbaum Höhenbalancierter Binärbaum 

 

javafrage Sat, 02/13/2016 - 17:47

13 Warteschlangen

13 Warteschlangen

Die „einfache“ Warteschlange wird in echten Implementierungen eher selten eingesetzt. Nennen Sie den wichtigsten Nachteil einer „einfachen“ Warteschlange. Welcher Warteschlangentyp wird in realen Implementierungen eher eingesetzt. Nennen Sie den Fachbegriff. Was ist der Vorteil dieses Warteschlangentyps?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2+2 Minuten

Antwort zu Frage 12: AVL Baum: Fehler erkennen und korrigieren

Knoten „80“ hat keinen Unterbaum (Höhe 1). Der Unterbaum von „40“ rechts hat die Höhe 3. Die Unterbäume dürfen sich in der Höhe nur um 1 unterscheiden.

Aufgabe Lösung
Inkorrekter AVL Baum Korrekter AVL Baum
javafrage Sat, 02/13/2016 - 18:13

Anonymous (not verified)

Sun, 06/19/2016 - 17:46

Könnte man nicht auch einfach die 60 links unter die 80 schreiben? Dann müsste man nicht den ganzen Baum ändern

14 Streng sortierte Binärbäume

14 Streng sortierte Binärbäume

Nennen Sie drei Eigenschaften die für jeden inneren Knoten eines streng
aufsteigend sortierten Binärbaums gelten.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 3 Minuten

Antwort zu Frage 13: Warteschlangen

Einfache Warteschlangen können beliebig groß werden falls ein Prozessor, der die Warteschlange bedient ausfällt. Dieser Ausfalls des Prozessors der die Warteschlange abarbeitet und Elemente löscht wird dann zu einem Hauptspeicheproblem führen. Das Hauptspeicherproblem kann dann die gesamte Anwendung stoppen.

Die Lösung:

Ringsspeicher auch Ringpuffer genannt.

Sie haben einen konstanten Speicherverbrauch.

javafrage Sat, 03/25/2017 - 17:21

15 Maximaler Aufwand für Binärbaum

15 Maximaler Aufwand für Binärbaum
Der streng sortierte Binärbaum (rechts) gewährleistet einen Zugriff auf alle Knoten mit einem minimalen Aufwand. Zeichnen Sie rechts daneben einen streng sortierten Binärbaum mit den gleichen Werten der den höchstmöglichen (schlechtesten) Aufwand für den Zugriff auf alle Knoten besitzt Binärbaum

Die Antwort finden Sie unten auf dieser Seite.

Niveau 2
Schwierigkeitsgrad mittel
Zeit 4 Minuten

Antwort zu Frage 14: Streng sortierte Binärbäume

  1. Jeder Knoten hat einen oder zwei Söhne
  2. Jeder linke Sohn ist kleiner als der Vater
  3. Jeder rechte Sohn ist größer als der Vater

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Antwort zu Frage 15: Maximaler Aufwand für Binärbaum

Ein Baum der zu einer Liste degeniert ist hat den schlechtesten Aufwand O(n).

Anbei ein Beispiel:

Degenerierter Binärbaum

javafrage Sat, 03/25/2017 - 17:31