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 heet groei van O(2ⁿ)?

  1. ALineair
  2. BPolynomiaal
  3. CLogaritmisch
  4. DExponentieel
2.Makkelijk

Wat is een brute-force-algoritme?

  1. AEen algoritme dat alle mogelijke kandidaatoplossingen probeert
  2. BEen algoritme dat altijd recursie gebruikt
  3. CEen algoritme dat willekeurig een antwoord raadt
  4. DEen algoritme dat op veel processoren draait
3.Makkelijk

Wat is recursie?

  1. AEen functie die zichzelf aanroept op kleinere invoer
  2. BEen sorteermethode
  3. CEen soort datastructuur
  4. DEen lus die nooit eindigt
4.Gemiddeld

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

  1. AZe loopt in O(1) tijd
  2. BDe compiler maakt er altijd een lus van die veilig eindigt
  3. CZe blijft zichzelf aanroepen totdat de call stack overloopt
  4. DZe geeft automatisch 0 terug
5.Gemiddeld

Hoeveel stackruimte gebruikt een eenvoudige recursieve faculteitsfunctie fact(n) = n × fact(n − 1)?

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

Wat is de worst-case tijdcomplexiteit van quicksort?

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

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

  1. AVergelijkingen op knopen van een gelinkte lijst zijn trager
  2. BGelinkte lijsten kunnen niet worden gesorteerd
  3. CHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  4. DBinair zoeken heeft minstens twee keer zoveel geheugen nodig
8.Moeilijk

Wat moet je doen om aan te tonen dat een nieuw probleem X NP-moeilijk is?

  1. AAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer
  2. BAantonen dat X in polynomiale tijd kan worden geverifieerd
  3. CX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem
  4. DEen bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X

Antwoordenblad

  1. 1. D · Exponentieel
  2. 2. A · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  3. 3. A · Een functie die zichzelf aanroept op kleinere invoer
  4. 4. C · Ze blijft zichzelf aanroepen totdat de call stack overloopt
  5. 5. D · O(n)
  6. 6. D · O(n²)
  7. 7. C · Het middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  8. 8. D · Een bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X

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