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 notatie beschrijft een bovengrens voor de groei?

  1. AGrote Theta (Big Theta)
  2. BGrote O (Big O)
  3. CGrote Omega (Big Omega)
  4. DKleine omega (little omega)
2.Makkelijk

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

  1. ABubblesort
  2. BMergesort
  3. CInsertion sort
  4. DQuicksort
3.Makkelijk

Een element in een array via de index benaderen kost:

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

Wat is de oplossing van de recurrente betrekking T(n) = T(n − 1) + O(n)?

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

Een gretig (greedy) algoritme:

  1. AMaakt bij elke stap de lokaal beste keuze
  2. BGebruikt alleen recursie
  3. CProbeert elke mogelijke oplossing
  4. DGeeft altijd de optimale oplossing
6.Gemiddeld

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

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

Hoe verhouden n! en 2ⁿ zich voor grote n?

  1. AZe groeien even snel
  2. Bn! is O(n²)
  3. C2ⁿ groeit sneller dan n!
  4. Dn! groeit sneller dan 2ⁿ
8.Moeilijk

Wat is de tijdcomplexiteit van het opbouwen van een binaire heap uit n ongesorteerde elementen met de bottom-upmethode?

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

Antwoordenblad

  1. 1. B · Grote O (Big O)
  2. 2. D · Quicksort
  3. 3. C · O(1)
  4. 4. A · O(n²)
  5. 5. A · Maakt bij elke stap de lokaal beste keuze
  6. 6. C · O(d(n + k))
  7. 7. D · n! groeit sneller dan 2ⁿ
  8. 8. B · O(n)

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