Nederlands
Menu

Datastructuren en algoritmen

De records (naam, score) (A, 80), (B, 70), (C, 80), (D, 70) staan in deze volgorde. In welke volgorde staan de namen als ze met een stabiel sorteeralgoritme oplopend op score worden gesorteerd?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Antwoord en toelichting tonen

Antwoord: A. B, D, A, C

Een stabiel sorteeralgoritme houdt elementen met dezelfde sleutel (hier de score) in hun oorspronkelijke onderlinge volgorde. B en D, allebei 70, blijven in de volgorde B, D, en A en C, allebei 80, in de volgorde A, C; dat geeft B, D, A, C. Bubblesort, insertion sort en mergesort zijn stabiel, terwijl selection sort, quicksort en heapsort dat in het algemeen niet zijn. Met een stabiel sorteeralgoritme kan op meerdere sleutels worden gesorteerd, bijvoorbeeld eerst op naam en daarna op score.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. In welk typisch geval heeft quicksort tijdcomplexiteit O(n²)?
  2. Bij mergesort worden de twee gesorteerde reeksen 1, 4, 7, 9 en 2, 3, 8, 10 samengevoegd (merge) tot één reeks door herhaaldelijk de voorste elementen te vergelijken en het kleinste uit te voeren. Is één reeks leeg, dan wordt de rest van de andere zonder vergelijking uitgevoerd. Hoeveel vergelijkingen zijn er nodig?
  3. Een binaire heap wordt opgeslagen in een array a[0], a[1], a[2], … met de wortel in a[0], waarbij elk niveau van bovenaf van links naar rechts wordt gevuld. Wat zijn de kinderen en de ouder van a[4]?
  4. Een max-heap, waarin de waarde van elke ouder minstens zo groot is als die van zijn kinderen, wordt opgeslagen in een array met de wortel in a[0]. Aan de heap 50, 30, 40, 10, 20, 35 wordt 45 toegevoegd door de waarde achteraan te plaatsen en haar met haar ouder te verwisselen zolang ze groter is dan die ouder. Hoe ziet de array er daarna uit?
  5. Een binaire zoekboom wordt in in-order doorlopen (symmetrische volgorde: eerst de linkerdeelboom, dan de knoop zelf, dan de rechterdeelboom). In welke volgorde staan de waarden van de bezochte knopen? Neem aan dat alle waarden verschillend zijn.