Wichtige Fragen zu den Definitionen der Datenstrukturen und Bedingungen (Java-Aufgaben)

notparanoidbutanandr
Neuling
Neuling
Beiträge: 5
Registriert: 16. Jul 2017 15:31

Wichtige Fragen zu den Definitionen der Datenstrukturen und Bedingungen (Java-Aufgaben)

Beitrag von notparanoidbutanandr » 16. Sep 2017 14:00

Hallo allerseits,

anscheinend gibt es schon teilweise Unterschiede zwischen den Definitionen der (6) Strukturen und Bedingungen auf dem Java-Übungsblatt und den an dieses angelehnte Klausuraufgaben.

- Bei ListItem auf dem Blatt gibt es next und back, bei back steht, es kann fehlen. Allerdings, wenn man sich die (iterativen) Aufgaben aus den beiden zur Verfügung gestellten Altklausuren anschaut, ist ListItem<T> ohne back definiert.
Wäre die iterative Aufgabe dementsprechend auch immer ohne back zu lösen? Das kann je nach Aufgabe einen erheblichen Unterschied machen!

- Erstmal allgemein zu den Baumstrukturen. Es heißt in den Klausuranweisungen, man dürfe keine weitere Funktionalität benutzen. Das trifft dann auch u.a. auch auf Vector und geeignete Methoden zu, nehme ich an? Wäre auch wichtig, zu wissen, ob man, falls eine iterative Aufgabe mit Bäumen drankommt, wirklich kein Vector / Stack, push() pop() etc. benutzen darf!

- Zur Struktur von TreeNode / TreeNodeT: In der Vorlesung gab es ja alle möglichen verschiedenen Fälle. Anscheinend sollen wir aber (z.B. nach so manchen Vorschlägen im Programmier-Thread und auch diesem inoffiziellen Lösungsvorschlag) von folgenden Regeln ausgehen:

für TreeNode (binär): key ist niemals null (das ist klar), wenn es einen(!) Nachfolger gibt, dann ist dieser garantiert root.left (!), wenn es 2 gibt dann root.left und root.right logischerweise? Also anders gesagt, es ist nicht möglich, dass es root.right gibt und root.left == null?

für TreeNodeT (ternär): ist key1 niemals null? und wenn key2 nicht null ist, ist dann garantiert root.right != null?

- zum Vielwegbaum TreeNodeV:
theKeys und theSuccessors sind natürlich != null. Jedoch: Sind alle Keys != null? Wenn nein, sind dann ab einer Position alle Keys null oder kann es 'Lücken' geben?
Dann gilt anscheinend, dass theSuccessors.length = theKeys.length+1, da es maximal n+1 Nachfolgeknoten zu n Keys geben kann. Da es auch Blattknoten gibt, sind natürlich nicht alle Nachfolger != null. Sind aber nun hier Nachfolger bis zu einer bestimmten Stelle != null und danach nicht mehr oder kann es auch hier 'Lücken' geben?

Schonmal vielen Dank im Voraus für jede sinnvolle Antwort.
Gruß

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wichtige Fragen zu den Definitionen der Datenstrukturen und Bedingungen (Java-Aufgaben)

Beitrag von Prof. Karsten Weihe » 23. Sep 2017 08:43

notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
- Bei ListItem auf dem Blatt gibt es next und back, bei back steht, es kann fehlen. Allerdings, wenn man sich die (iterativen) Aufgaben aus den beiden zur Verfügung gestellten Altklausuren anschaut, ist ListItem<T> ohne back definiert.
Wäre die iterative Aufgabe dementsprechend auch immer ohne back zu lösen?
Kann sein, dass back ggf. dabei ist, muss aber nicht sein.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
- Erstmal allgemein zu den Baumstrukturen. Es heißt in den Klausuranweisungen, man dürfe keine weitere Funktionalität benutzen. Das trifft dann auch u.a. auch auf Vector und geeignete Methoden zu, nehme ich an?
Wenn Sie java.util.Vector meinen, trifft das ganz sicher darauf zu.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
Wäre auch wichtig, zu wissen, ob man, falls eine iterative Aufgabe mit Bäumen drankommt, wirklich kein Vector / Stack, push() pop() etc. benutzen darf!
Das wird ggf. in der Aufgabenstellung spezifiziert, ob oder ob nicht.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
für TreeNode (binär): key ist niemals null (das ist klar), wenn es einen(!) Nachfolger gibt, dann ist dieser garantiert root.left (!), wenn es 2 gibt dann root.left und root.right logischerweise? Also anders gesagt, es ist nicht möglich, dass es root.right gibt und root.left == null?
Ja, aber ggf. wird das in der Aufgabenstellung nochmals zumindest angedeutet.

notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
für TreeNodeT (ternär): ist key1 niemals null?
Ja.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
und wenn key2 nicht null ist, ist dann garantiert root.right != null?
Kann man nicht allgemein sagen.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
- zum Vielwegbaum TreeNodeV:
theKeys und theSuccessors sind natürlich != null. Jedoch: Sind alle Keys != null? Wenn nein, sind dann ab einer Position alle Keys null oder kann es 'Lücken' geben?
Die KNoten eines Vielwegbaumes sind im Prinzip dynamische Arrays wie in den entsprechenden Live Codings, also bis zu der im int-Attribut festgelegten Position (off-by-one error vermeiden!) alles echte Keys, danach keine Keys mehr.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
Dann gilt anscheinend, dass theSuccessors.length = theKeys.length+1, da es maximal n+1 Nachfolgeknoten zu n Keys geben kann.
Ja.
notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
Da es auch Blattknoten gibt, sind natürlich nicht alle Nachfolger != null. Sind aber nun hier Nachfolger bis zu einer bestimmten Stelle != null und danach nicht mehr oder kann es auch hier 'Lücken' geben?
Parallel zu den Keys, aber es kann auch zwischendurch Lücken geben. Wenn wir eine striktere Struktur wie bspw. B-Baum implementieren, darf es dort keine Lücken geben, aber allgemein für Vielwegbäume muss man das nicht als Invariante fordern.

KW

nozyde
Erstie
Erstie
Beiträge: 20
Registriert: 7. Jun 2017 21:22

Re: Wichtige Fragen zu den Definitionen der Datenstrukturen und Bedingungen (Java-Aufgaben)

Beitrag von nozyde » 23. Sep 2017 09:59

notparanoidbutanandr hat geschrieben:
16. Sep 2017 14:00
für TreeNodeT (ternär): ist key1 niemals null? und wenn key2 nicht null ist, ist dann garantiert root.right != null?
Das bedeutet doch nichts anderes als: "Key2 kann nur dann null werden, wenn root.right auch null ist" oder anders gesagt: "Key2 kann nicht null werden, wenn es einen rechten Nachfolgeknoten (root.right) gibt". Umgekehrt ist das natürlich nicht auszuschließen, denn key2 kann besetzt sein, auch wenn es keinen rechten Nachfolgeknoten gibt.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wichtige Fragen zu den Definitionen der Datenstrukturen und Bedingungen (Java-Aufgaben)

Beitrag von Prof. Karsten Weihe » 23. Sep 2017 11:13

nozyde hat geschrieben:
23. Sep 2017 09:59
Das bedeutet doch nichts anderes als: "Key2 kann nur dann null werden, wenn root.right auch null ist" oder anders gesagt: "Key2 kann nicht null werden, wenn es einen rechten Nachfolgeknoten (root.right) gibt". Umgekehrt ist das natürlich nicht auszuschließen, denn key2 kann besetzt sein, auch wenn es keinen rechten Nachfolgeknoten gibt.
Man kann es auf zwei Arten definieren: Entweder wie bei B-Bäumen, dass die Anzahl der Nachfolger immer um 1 größer als die Anzahl der Keys ist, oder dass Lücken erlaubt sind. Je nachdem, kann man sich auf right != null verlassen oder nicht. In der Klausur würde ggf. so etwas genau spezifiziert sein.

KW

Antworten

Zurück zu „Archiv“