Datastructuren en algoritmen

Lineair zoeken vergelijkt de elementen van een array met 100 verschillende waarden één voor één vanaf het begin om een gezochte waarde te vinden. De gezochte waarde staat altijd in de array en heeft op elke positie dezelfde kans. Wat is het gemiddelde aantal vergelijkingen?

AOngeveer 7
B50,5
C100

Antwoord en toelichting tonen

Antwoord: B. 50,5

Staat de gezochte waarde op positie k, dan zijn er k vergelijkingen nodig. Het gemiddelde is dus (1 + 2 + … + 100) / 100 = 50,5, in het algemeen (n + 1)/2. In het beste geval (waarde vooraan) is er 1 vergelijking nodig, in het slechtste geval (waarde achteraan) 100. Zowel het gemiddelde als het slechtste geval is evenredig met n, dus de tijdcomplexiteit is O(n). Ongeveer 7 komt overeen met log₂ 100 ≈ 6,6, het aantal stappen van binair zoeken, dat alleen werkt als de gegevens gesorteerd zijn.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?
Op een lege stack worden achtereenvolgens push 1, push 2, pop, push 3, push 4, pop, pop uitgevoerd. In welke volgorde komen de waarden die pop verwijdert eruit?
In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?
De expressie „3 4 + 2 * 5 −” in omgekeerde Poolse notatie (postfixnotatie) wordt geëvalueerd door elk getal op een stack te leggen en bij elke operator twee waarden eraf te halen, het resultaat te berekenen en dat weer op de stack te leggen. Wat is het resultaat? De linkeroperand van een operator is de waarde die het eerst op de stack is gelegd.
Welke beschrijving van een botsing (collision) in een hashtabel is juist?