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

Hoe werkt selection sort?

  1. AHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
  2. BHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  3. CHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan
  4. DHet splitst de array in helften en voegt die samen
2.Makkelijk

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

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

Welke hiervan groeit het langzaamst als n groot wordt?

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

Wat is de worst-case tijdcomplexiteit van quicksort?

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

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

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

Een gretig (greedy) algoritme:

  1. AMaakt bij elke stap de lokaal beste keuze
  2. BGebruikt alleen recursie
  3. CGeeft altijd de optimale oplossing
  4. DProbeert elke mogelijke oplossing
7.Moeilijk

Wat is het verschil tussen een onbeslisbaar en een onhandelbaar probleem?

  1. AEen onbeslisbaar probleem heeft geen algoritme voor alle invoer; een onhandelbaar probleem wel, maar dat is te traag
  2. BBeide betekenen dat het probleem helemaal geen algoritme heeft
  3. COnbeslisbare problemen zitten in NP, terwijl onhandelbare problemen in P zitten
  4. DOnhandelbare problemen kunnen door geen enkel algoritme worden opgelost, terwijl onbeslisbare alleen exponentiële tijd nodig hebben
8.Moeilijk

Welke bewering over P en NP is juist?

  1. AElk probleem in P zit ook in NP
  2. BOplossingen van NP-problemen kunnen niet snel worden geverifieerd
  3. CEr is bewezen dat P ≠ NP
  4. DNP betekent "niet polynomiaal"

Antwoordenblad

  1. 1. B · Het zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  2. 2. D · O(n²)
  3. 3. C · O(log n)
  4. 4. B · O(n²)
  5. 5. A · O(n log n)
  6. 6. A · Maakt bij elke stap de lokaal beste keuze
  7. 7. A · Een onbeslisbaar probleem heeft geen algoritme voor alle invoer; een onhandelbaar probleem wel, maar dat is te traag
  8. 8. A · Elk probleem in P zit ook in NP

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