Datastructuren en algoritmen

Binair zoeken zoekt 38 in de oplopende array a[0] tot a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Het zoekbereik begint met lo = 0 en hi = 9, en de middelste positie is (lo + hi) ÷ 2, naar beneden afgerond. Welke reeks geeft, in volgorde, de waarden van de elementen waarmee 38 wordt vergeleken?

A23, 38
B31, 52, 45, 38
C23, 45, 31, 38

Antwoord en toelichting tonen

Antwoord: C. 23, 45, 31, 38

Eerst is (0 + 9) ÷ 2 = 4, dus 38 wordt vergeleken met a[4] = 23; 38 is groter, dus lo = 5. Daarna is (5 + 9) ÷ 2 = 7, dus de vergelijking is met a[7] = 45; 38 is kleiner, dus hi = 6. Dan geeft (5 + 6) ÷ 2 = 5 het element a[5] = 31, dus lo = 6, en ten slotte komt a[6] = 38 overeen. Dat zijn 4 vergelijkingen, het maximum voor 10 elementen: ⌊log₂ 10⌋ + 1 = 4. De volgorde 31, 52, 45, 38 ontstaat als het midden naar boven wordt afgerond, en dat is niet de regel uit de vraag.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

De array 5, 3, 8, 1, 4 wordt met bubblesort oplopend gesorteerd. Hoe ziet de array eruit na één doorgang (pass), waarin vanaf het begin tot het eind telkens twee buren worden vergeleken en verwisseld als het linkerelement groter is?
De array 29, 10, 14, 37, 13 wordt met selection sort oplopend gesorteerd: het minimum van het ongesorteerde deel wordt gezocht en verwisseld met het eerste element van het ongesorteerde deel. Hoe ziet de array eruit nadat deze stap twee keer is uitgevoerd?
Een array van 10 elementen wordt met insertion sort oplopend gesorteerd. Elk element vanaf het tweede wordt eruit gehaald en vergeleken met de elementen links ervan, te beginnen bij de linkerbuur, tot een element kleiner dan of gelijk aan de waarde is gevonden of het begin is bereikt. Hoeveel vergelijkingen zijn er nodig als de array al oplopend staat, en als hij aflopend staat?
Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?
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?