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

Welke van deze looptijden is polynomiaal?

  1. AO(n!)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(2ⁿ)
2.Makkelijk

Een O(n)-algoritme doet 3 seconden over n = 1 miljoen. Hoe lang doet het ongeveer over n = 2 miljoen?

  1. A6 seconden
  2. B12 seconden
  3. C9 seconden
  4. D3 seconden
3.Makkelijk

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

De tijdcomplexiteit van naïef recursief Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

  1. ALineair
  2. BExponentieel
  3. CConstant
  4. DLogaritmisch
5.Gemiddeld

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

  1. AO(V³ × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V × E)
6.Gemiddeld

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

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

Het stopprobleem (halting problem) laat zien dat:

  1. ALussen vermeden moeten worden
  2. BSommige programma's sneller draaien op snellere computers, dus stoppen hangt van de hardware af
  3. CElk programma uiteindelijk stopt
  4. DGeen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt
8.Moeilijk

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(2ⁿ) tijd en O(1) ruimte
  2. BO(log n) tijd en O(n) ruimte
  3. CO(n) tijd en O(1) ruimte
  4. DO(n) tijd en O(n) ruimte

Antwoordenblad

  1. 1. C · O(n³)
  2. 2. A · 6 seconden
  3. 3. C · O(n)
  4. 4. B · Exponentieel
  5. 5. D · O(V × E)
  6. 6. C · O(n²)
  7. 7. D · Geen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt
  8. 8. C · O(n) tijd en O(1) ruimte

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