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. APolynomiaal
  2. BLogaritmisch
  3. CExponentieel
  4. DLineair
2.Makkelijk

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

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

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

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

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

Een gretig (greedy) algoritme:

  1. AGeeft altijd de optimale oplossing
  2. BProbeert elke mogelijke oplossing
  3. CMaakt bij elke stap de lokaal beste keuze
  4. DGebruikt alleen recursie
6.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(1)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
7.Moeilijk

Wat heeft de stelling van Cook-Levin vastgesteld?

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

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

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

Antwoordenblad

  1. 1. C · Exponentieel
  2. 2. D · O(n)
  3. 3. C · De looptijd groeit niet met de invoergrootte
  4. 4. B · O(2ⁿ)
  5. 5. C · Maakt bij elke stap de lokaal beste keuze
  6. 6. A · O(1)
  7. 7. D · Het booleaanse vervulbaarheidsprobleem (SAT) is NP-volledig
  8. 8. B · Θ(n log² n)

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