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

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

  1. AHeapsort
  2. BQuicksort
  3. CMergesort
  4. DBubblesort
2.Makkelijk

Welke notatie beschrijft een ondergrens voor de groei?

  1. AΩ (grote omega)
  2. BΘ (grote theta)
  3. CO (grote O)
  4. Do (kleine o)
3.Makkelijk

Wat is log₂ 1024?

  1. A10
  2. B512
  3. C12
  4. D32
4.Gemiddeld

Wat is de tijdcomplexiteit van: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

  1. AMergesort is al O(n)
  2. BDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
  3. CMergesort heeft geen recursieve structuur
  4. DDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
6.Gemiddeld

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

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

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

Het stopprobleem (halting problem) laat zien dat:

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

Antwoordenblad

  1. 1. D · Bubblesort
  2. 2. A · Ω (grote omega)
  3. 3. A · 10
  4. 4. B · O(n log n)
  5. 5. B · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  6. 6. B · O(n log n)
  7. 7. D · O(n)
  8. 8. D · Geen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt

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