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

Wat betekent het als een bewerking in O(1) tijd loopt?

  1. ADe looptijd groeit niet met de invoergrootte
  2. BHet verwerkt precies één element per seconde looptijd
  3. CHet duurt altijd precies één seconde
  4. DHet kan maar één keer worden uitgevoerd
2.Makkelijk

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Welke ontwerpstrategie gebruikt mergesort?

  1. ADynamisch programmeren
  2. BVerdeel en heers
  3. CBrute kracht
  4. DGulzige keuze (greedy)
4.Gemiddeld

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

  1. AHet algoritme van Dijkstra
  2. BHet algoritme van Kruskal
  3. CBellman-Ford is in alle gevallen vereist
  4. DDiepte-eerst zoeken (DFS)
5.Gemiddeld

De tijdcomplexiteit van naïef recursief Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

  1. AExponentieel
  2. BLogaritmisch
  3. CConstant
  4. DLineair
6.Gemiddeld

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

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

Wat zijn de geamortiseerde kosten van het ophogen van een binaire teller, als één ophoging veel bits kan omzetten?

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

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

  1. AΘ(n log n)
  2. BΘ(n log² n)
  3. CΘ(n²)
  4. DΘ(n)

Antwoordenblad

  1. 1. A · De looptijd groeit niet met de invoergrootte
  2. 2. A · O(n²)
  3. 3. B · Verdeel en heers
  4. 4. A · Het algoritme van Dijkstra
  5. 5. A · Exponentieel
  6. 6. D · O(log n)
  7. 7. B · O(1) per ophoging
  8. 8. B · Θ(n log² n)

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