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 kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. ABubblesort
  2. BQuicksort
  3. CInsertion sort
  4. DMergesort
2.Makkelijk

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

  1. A4 seconden
  2. B8 seconden
  3. C1 seconde
  4. D2 seconden
4.Gemiddeld

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

  1. AOverlappende deelproblemen en optimale substructuur
  2. BHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
  3. CEén enkele lus
  4. DAlleen willekeurige invoer
5.Gemiddeld

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
6.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(E log V)
  3. CO(V × E)
  4. DO(V³ × E)
7.Moeilijk

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

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

Wat heeft de stelling van Cook-Levin vastgesteld?

  1. AP is niet gelijk aan NP
  2. BElk NP-probleem kan in exponentiële tijd worden opgelost
  3. CHet stopprobleem is onbeslisbaar
  4. DHet booleaanse vervulbaarheidsprobleem (SAT) is NP-volledig

Antwoordenblad

  1. 1. B · Quicksort
  2. 2. A · O(n²)
  3. 3. A · 4 seconden
  4. 4. A · Overlappende deelproblemen en optimale substructuur
  5. 5. D · O(n)
  6. 6. C · O(V × E)
  7. 7. B · O(n log n)
  8. 8. D · Het booleaanse vervulbaarheidsprobleem (SAT) is NP-volledig

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