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

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

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

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

  1. A12 seconden
  2. B6 seconden
  3. C3 seconden
  4. D9 seconden
3.Makkelijk

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. ABubblesort
  2. BInsertion sort
  3. CMergesort
  4. DQuicksort
4.Gemiddeld

Hoeveel niveaus heeft de recursie van mergesort voor een array van n elementen?

  1. AOngeveer log₂ n
  2. BOngeveer n
  3. COngeveer n / 2
  4. DOngeveer √n
5.Gemiddeld

Een gretig (greedy) algoritme:

  1. AGebruikt alleen recursie
  2. BMaakt bij elke stap de lokaal beste keuze
  3. CGeeft altijd de optimale oplossing
  4. DProbeert elke mogelijke oplossing
6.Gemiddeld

Met munten van 1, 3 en 4 en een bedrag van 6: hoeveel munten gebruikt de gulzige methode "grootste munt eerst", vergeleken met het optimum?

  1. AGulzig gebruikt 3 munten; het optimum is 3
  2. BGulzig gebruikt 3 munten; het optimum is 2
  3. CGulzig gebruikt 2 munten; het optimum is 2
  4. DGulzig gebruikt 4 munten; het optimum is 3
7.Moeilijk

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + n log n?

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

Welke uitspraak over de kleine-o-notatie is juist?

  1. An = o(n), omdat elke functie kleine o van zichzelf is
  2. Bn = o(n²), maar n is niet o(n)
  3. Cn² = o(n)
  4. D2n = o(n), omdat 2n langzaam groeit

Antwoordenblad

  1. 1. D · O(log n)
  2. 2. B · 6 seconden
  3. 3. D · Quicksort
  4. 4. A · Ongeveer log₂ n
  5. 5. B · Maakt bij elke stap de lokaal beste keuze
  6. 6. B · Gulzig gebruikt 3 munten; het optimum is 2
  7. 7. C · Θ(n log² n)
  8. 8. B · n = o(n²), maar n is niet o(n)

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