Datenstrukturen und Algorithmen

Bei Mergesort werden die beiden sortierten Folgen 1, 4, 7, 9 und 2, 3, 8, 10 zu einer zusammengeführt (Merge), indem wiederholt die vordersten Elemente verglichen und das kleinere ausgegeben wird. Ist eine Folge leer, wird der Rest der anderen ohne Vergleich ausgegeben. Wie viele Vergleiche werden durchgeführt?

Antwort und Erläuterung anzeigen

Antwort: B. 7

Verglichen werden 1 mit 2, 4 mit 2, 4 mit 3, 4 mit 8, 7 mit 8, 9 mit 8 und 9 mit 10; danach ist die erste Folge leer, und die verbleibende 10 wird ohne Vergleich ausgegeben. Das sind 7 Vergleiche, das Maximum m + n − 1 = 7 beim Zusammenführen von Folgen der Längen m und n. Ein Merge betrachtet jedes Element der sortierten Folgen nur einmal und kostet daher O(m + n); da Mergesort dies über log₂ n Ebenen wiederholt, benötigt das gesamte Sortieren O(n log n).

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?
Ein Max-Heap, in dem der Wert jedes Elternknotens mindestens so groß ist wie die Werte seiner Kinder, wird in einem Array mit der Wurzel in a[0] gespeichert. Zum Heap 50, 30, 40, 10, 20, 35 wird 45 hinzugefügt, indem es ans Ende gesetzt und dann mit seinem Elternknoten vertauscht wird, solange es größer als dieser ist. Wie sieht das resultierende Array aus?
Wie sind die Werte der besuchten Knoten angeordnet, wenn ein binärer Suchbaum in In-Order (symmetrische Reihenfolge: erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum) durchlaufen wird? Alle Werte seien verschieden.
Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. In welcher Reihenfolge werden die Knoten besucht, wenn der Baum in Post-Order (erst der linke Teilbaum, dann der rechte Teilbaum, dann der Knoten) durchlaufen wird?
Die Werte 1, 2, 3, …, 1000 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt (ohne Rebalancierung). Mit wie vielen Knoten wird bei der Suche nach 1000, beginnend an der Wurzel, verglichen, bis der Wert gefunden ist?