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. ALogaritmisch
  2. BExponentieel
  3. CLineair
  4. DPolynomiaal
2.Makkelijk

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

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

Wat is recursie?

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

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

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

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

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

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

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

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

Het algoritme van Held-Karp voor dynamisch programmeren lost het handelsreizigersprobleem exact op. Wat is de looptijd voor n steden?

  1. AO(n² 2ⁿ)
  2. BO(n!)
  3. CO(2n²)
  4. DO(n³)

Antwoordenblad

  1. 1. B · Exponentieel
  2. 2. A · De looptijd groeit niet met de invoergrootte
  3. 3. C · Een functie die zichzelf aanroept op kleinere invoer
  4. 4. D · O(1)
  5. 5. B · O(n)
  6. 6. B · O(log n)
  7. 7. C · O(1) per ophoging
  8. 8. A · O(n² 2ⁿ)

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