Deutsch
Menü

Datenstrukturen und Algorithmen

Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Antwort und Erläuterung anzeigen

Antwort: A. B, D, A, C

Ein stabiles Sortierverfahren behält die ursprüngliche Reihenfolge von Elementen mit gleichem Schlüssel (hier der Punktzahl) bei. B und D, beide mit 70, bleiben in der Reihenfolge B, D, und A und C, beide mit 80, in der Reihenfolge A, C; es ergibt sich B, D, A, C. Bubblesort, Insertionsort und Mergesort sind stabil, Selectionsort, Quicksort und Heapsort im Allgemeinen nicht. Mit einem stabilen Verfahren lässt sich nach mehreren Schlüsseln sortieren, etwa zuerst nach Namen und dann nach Punktzahl.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. In welchem typischen Fall benötigt Quicksort O(n²) Zeit?
  2. 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?
  3. 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]?
  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?
  5. 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.