Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van binair zoeken in een gesorteerde array?

1. AO(n log n)
2. BO(1)
3. CO(n)
4. DO(log n)

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. AConstant
2. BLogaritmisch
3. CLineair
4. DKwadratisch

Hoe werkt selection sort?

1. AHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
2. BHet splitst de array in helften en voegt die samen
3. CHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan
4. DHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

1. AEen array in willekeurige volgorde
2. BEen array van lengte 2
3. CEen array die al gesorteerd is
4. DEen array waarvan alle elementen verschillend zijn

In een gesorteerde array zoek je twee elementen die samen een doelwaarde opleveren door vanaf elk uiteinde een pointer naar binnen te bewegen. Wat is de tijdcomplexiteit?

1. AO(n log n)
2. BO(log n)
3. CO(n²)
4. DO(n)

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

1. AO(n)
2. BO(n²)
3. CO(1)
4. DO(log n)

Welke grens is juist voor log(n!)?

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(n log n)

Wat zijn de tijd- en ruimtekosten van het berekenen van het n-de Fibonaccigetal met een lus die alleen de laatste twee waarden bewaart?

1. AO(log n) tijd en O(n) ruimte
2. BO(n) tijd en O(1) ruimte
3. CO(2ⁿ) tijd en O(1) ruimte
4. DO(n) tijd en O(n) ruimte