Werkblad Algoritmen & complexiteit met antwoorden

Gratis printbaar werkblad Algoritmen & complexiteit: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

  1. A8 seconden
  2. B2 seconden
  3. C1 seconde
  4. D4 seconden
3.Makkelijk

Wat betekent het als een bewerking in O(1) tijd loopt?

  1. AHet kan maar één keer worden uitgevoerd
  2. BHet verwerkt precies één element per seconde looptijd
  3. CHet duurt altijd precies één seconde
  4. DDe looptijd groeit niet met de invoergrootte
4.Gemiddeld

Welk sorteeralgoritme is stabiel?

  1. AMergesort
  2. BHeapsort
  3. CQuicksort (gangbare in-place-versie)
  4. DSelectionsort (gangbare versie)
5.Gemiddeld

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

  1. AAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet
  2. BLogaritmen met verschillende grondtallen verschillen alleen een constante factor
  3. CHet grondtal doet er alleen toe voor kleine n
  4. DLogaritmen worden altijd afgerond op gehele getallen
6.Gemiddeld

Wat is de worst-case tijdcomplexiteit van quicksort?

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

Wat zijn de geamortiseerde kosten van het ophogen van een binaire teller, als één ophoging veel bits kan omzetten?

  1. AO(n) per ophoging
  2. BO(log n) per ophoging
  3. CO(1) per ophoging
  4. DO(n log n) per ophoging
8.Moeilijk

Wat is de tijdcomplexiteit van: for i = 1 to n: for (j = i; j ≤ n; j = j + i) doe O(1) werk?

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

Antwoordenblad

  1. 1. D · O(n²)
  2. 2. D · 4 seconden
  3. 3. D · De looptijd groeit niet met de invoergrootte
  4. 4. A · Mergesort
  5. 5. B · Logaritmen met verschillende grondtallen verschillen alleen een constante factor
  6. 6. A · O(n²)
  7. 7. C · O(1) per ophoging
  8. 8. B · O(n log n)

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.