Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur 21 Februar 2008 Aufgab 7 g - Fragen zur HeapSortierung
Hallo
Die Fragestellung lautet:
Kreuzen sie an, ob folgende Aussagen richtig sind:
Ein Knoten in einem Heap muss zwei Kindknoten haben. —> Nein, kann ja auch nur einen haben.
Das Einfügen eines Knotens in einen Suchbaum kann nur mit einer rekursiven Methode erfolgen. —> Nein, wüsste nicht was beim Einfügen rekursiv sein sollte.(Oder??)
In einem Heap kann der kleinste Wert in der Wurzel stehen. —> Da weiß ich nicht was man ankreuzen soll, der kleinste Wert in einen Heap steht doch in der Wurzel, also muss er in der Wurzel stehen. Also ist die Aussage doch falsch, oder?
Um die in einem Suchbaum gespeicherten Werte sortiert auszugeben, muss man eine Breitensuche verwenden. —> was ist eine Breitensuche?
Ist die Aussage jetzt korrekt oder falsch? Ich würde sagen sie ist korrekt, denn wenn nur 1 Wert im Heap steht, wäre sowohl der größte als auch der kleinste in der Wurzel. Ansonsten bei mehr als einem Element im Heap muss der größte in der Wurzel stehen.
Bei einem min-heap steht immer das kleinste Element in der Wurzel, bei einem max-heap immer das größte. Die Aussage wirkt, als würde sie genau darauf abzielen, ist also korrekt.
Über “kann”/“muss” könnte man höchstens streiten, wenn es bei der Aufgabe eindeutig und einen min-heap ginge.
Das ist Definitionssache, ob der kleinste oder größte in der Wurzel stehen soll. Es gibt sowohl Min- als auch Max-Heaps. Hier wird allgemein nach einem Heap gefragt, von daher ist die Aussage korrekt.