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. BInsertion sort
  3. CQuicksort
  4. DMergesort
2.Makkelijk

Wat is de grote O van 3n² + 5n + 2?

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

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

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

Wat is de tijdcomplexiteit van: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Wat berekent het algoritme van Floyd-Warshall, en hoe snel?

  1. AEen topologische ordening in O(V²)
  2. BKortste paden vanuit één bronknoop naar alle andere in O(V + E)
  3. CKortste paden tussen alle paren knopen in O(V³)
  4. DEen minimale opspannende boom in O(E log V)
6.Gemiddeld

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

Karatsuba-vermenigvuldiging voldoet aan T(n) = 3T(n/2) + O(n). Wat is de oplossing?

  1. AΘ(n²)
  2. BΘ(nlog₂ 3), ongeveer n1,585
  3. CΘ(n log n)
  4. DΘ(n3)
8.Moeilijk

Hoe verhouden n! en 2ⁿ zich voor grote n?

  1. A2ⁿ groeit sneller dan n!
  2. Bn! groeit sneller dan 2ⁿ
  3. CZe groeien even snel
  4. Dn! is O(n²)

Antwoordenblad

  1. 1. C · Quicksort
  2. 2. A · O(n²)
  3. 3. B · De looptijd groeit niet met de invoergrootte
  4. 4. B · O(n log n)
  5. 5. C · Kortste paden tussen alle paren knopen in O(V³)
  6. 6. D · O(n log n)
  7. 7. B · Θ(nlog₂ 3), ongeveer n1,585
  8. 8. B · n! groeit sneller dan 2ⁿ

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