H 6.8

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

H 6.8

Beitrag von banshee »

hi,

a) "wie viele verschiedene einfügereihenfolgen gibt es, die zu einer verketteten liste führen"

kann mir mal jemand erklären, was das bedeuten soll? ich kann damit grade gar nix anfangen...

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Beitrag von Edoat »

Ich habe mich noch nicht genauer mit der HA auseinandergesetzt, aber ich hätte jetzt geraten, dass die Frage heißen soll: "Wie viele Einfügereihenfolgen gibt es, die zu einem völlig entarteten Baum (lineare Liste) führen?"

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

das hab ich mir auch gedacht, aber das kommt doch drauf an wie der baum vorher ausgesehen hat.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Naja, angenommen du hast eine Menge an Schlüsseln, die eingefügt werden sollen.

Wieviele Möglichkeiten - also Anordnungen der Menge als Folge - gibt es, die Schlüssel in einen (zuvor leeren) Binären Suchbaum einzufügen, damit danach ein vollkommen entarteter Suchbaum (lineare Liste) entsteht.
"Copy & Passed"

Wahlspruch der Plagiatoren

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

und wer sagt dass der suchbaum zuvor leer ist? :P

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Dein gesunder Menschenverstand? ;) Wenn er nicht leer wäre, könntest du ja keine Aussage über diese Aufgabenstellung machen, was mit einiger Sicherheit aber nicht die gewünschte Antwort ist *g*

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

okay, merk ich mir.

wenn wir in der klausur nen suchbaum implentieren sollen, is der bei mir auch leer. und wehe wenn es dann auch nur ein pünktchen abzug gibt! :roll:

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Kommt auf die Aufgabe an ;)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

HolgerF hat geschrieben:Dein gesunder Menschenverstand? ;) Wenn er nicht leer wäre, könntest du ja keine Aussage über diese Aufgabenstellung machen, was mit einiger Sicherheit aber nicht die gewünschte Antwort ist *g*
Doch, kann man:
1. Wenn der Baum vorher keine lineare Liste war, gibt es - ganz einfach - keine Möglichkeiten.
2. Wenn er eine lineare Liste war, muss man zwar ein paar Fallunterscheidungen machen (wenn ich mich recht entsinne, 8 ), aber es lassen sich dennoch für jeden Fall eindeutige Aussagen treffen: Entweder es geht gar nicht oder es geht mit *darfIchHierNichtSchreibenWeilIchDannWohlDieLösungVerratenWürde* Möglichkeiten.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Ja, aber dafür müsstest du eben etwas über den Baum wissen. Weißt du aber nicht, weil in der Aufgabe nichts dazu gesagt ist.

Du kannst dann entweder annehmen, dass die Aufgabe ein besonders raffinierter Trick ist ;) Oder dass man eben von einem leeren Baum ausgeht. Was ist wohl wahrscheinlicher?

Ja, Aufgaben im Unileben sind nicht immer ganz eindeutig gestellt. Aber oft genug kann man seinem eigenen Urteil durchaus mal trauen, wie die Aufgabe wohl gemeint war. Und die hier gehört in meinen Augen ohne Weiteres in diese Gruppe :)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

/Deswegen/ habe ich ja auch eine /Fallunterscheidung/ durchgeführt. Natürlich weiß ich nichts über den Baum, aber ich /kann/ etwas darüber sagen, /was/ los ist, /wenn/ der Baum dieunddie Struktur vorher schon hatte.

Zugegeben, ich hätte es auch lieber, dass der Baum am Anfang leer ist, aber diesmal bin ich lieber auf Nummer sicher gegangen, weil ich die HÜ endlich vom ToDo-Stack runterhaben wollte ^^
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Red*Star hat geschrieben:weil ich die HÜ endlich vom ToDo-Stack runterhaben wollte ^^
Zur ToDo Verwaltung sind Prioritaetswarteschlangen wesentlich geeigneter. Wie du die aus Heaps bauen kannst, kommt ja bald in der Vorlesung.

scnr
cw

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Red*Star hat geschrieben:/Deswegen/ habe ich ja auch eine /Fallunterscheidung/ durchgeführt. Natürlich weiß ich nichts über den Baum, aber ich /kann/ etwas darüber sagen, /was/ los ist, /wenn/ der Baum dieunddie Struktur vorher schon hatte.

Zugegeben, ich hätte es auch lieber, dass der Baum am Anfang leer ist, aber diesmal bin ich lieber auf Nummer sicher gegangen, weil ich die HÜ endlich vom ToDo-Stack runterhaben wollte ^^
Aber strenggenommen ändert das nichts an der Anzahl der möglichen Einfügereihenfolgen für deine n Elemente, falls es überhaupt möglich ist, oder? Entweder der Baum war vorher leer oder eine verkettete Liste, bei der alle einzufügenden Elemente für sich selbst an dieselbe, die Liste erhaltende Stelle einsortiert würden. Dann ist es möglich, und immer mit derselben Zahl Möglichkeiten. In allen anderen Fällen geht es nicht. Wenn es dein Gewissen beruhigt, kannst du das ja hinschreiben, kostet auch nur einen Satz :)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

wach hat geschrieben:
Red*Star hat geschrieben:weil ich die HÜ endlich vom ToDo-Stack runterhaben wollte ^^
Zur ToDo Verwaltung sind Prioritaetswarteschlangen wesentlich geeigneter. Wie du die aus Heaps bauen kannst, kommt ja bald in der Vorlesung.

scnr
cw
Hrhr... so ein Ding im RealLife zu implementieren... viel Spaß. Immerhin kommt mein Arbeitsumfeld in diesem Semester tatsächlich immer mehr einem Heap...
wikipedia hat geschrieben:ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur
...also einer Halde gleich... dank Gdi2. Naja, 2 Praktika noch, dann isses ja wohl hoffentlich geschafft.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Um weiter Offtopic zu werden: man munkelt, ein neuntes Praktikum sei in Planung - wichtig eher für die, die damit noch den Schein bekommen könnten, nicht als "wir drücken den Studenten noch mehr Arbeit auf".

Antworten

Zurück zu „Archiv“