Datastructuren en algoritmen

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?

Antwoord en toelichting tonen

Antwoord: B. 7

De vergelijkingen zijn 1 met 2, 4 met 2, 4 met 3, 4 met 8, 7 met 8, 9 met 8 en 9 met 10; op dat moment is de eerste reeks leeg, dus de resterende 10 wordt zonder vergelijking uitgevoerd. Dat zijn 7 vergelijkingen, het maximum m + n − 1 = 7 bij het samenvoegen van reeksen met lengte m en n. Een merge bekijkt elk element van de gesorteerde reeksen maar één keer en kost dus O(m + n); mergesort herhaalt dit over log₂ n niveaus, zodat het hele sorteerproces O(n log n) kost.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

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]?
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?
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.
De waarden 50, 30, 70, 20, 40, 60, 80 worden in deze volgorde ingevoegd in een lege binaire zoekboom. In welke volgorde worden de knopen bezocht als de boom in post-order wordt doorlopen (eerst de linkerdeelboom, dan de rechterdeelboom, dan de knoop zelf)?
De waarden 1, 2, 3, …, 1000 worden in deze volgorde ingevoegd in een lege binaire zoekboom (zonder herbalancering). Met hoeveel knopen wordt, vanaf de wortel, vergeleken voordat 1000 wordt gevonden?