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 is log₂ 1024?

  1. A32
  2. B12
  3. C512
  4. D10
2.Makkelijk

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Wat is de worst-case tijdcomplexiteit van mergesort?

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

Welk sorteeralgoritme is stabiel?

  1. ASelectionsort (gangbare versie)
  2. BMergesort
  3. CQuicksort (gangbare in-place-versie)
  4. DHeapsort
5.Gemiddeld

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

  1. ARecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
  2. BInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  3. CInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
  4. DInsertion sort is in het slechtste geval O(n log n)
6.Gemiddeld

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

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

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

  1. AX reduceert tot een probleem in P, en X zit in NP
  2. BX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
  3. CX zit in P, en X reduceert tot SAT
  4. DX heeft geen polynomiaal algoritme, en X is beslisbaar
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. D · 10
  2. 2. B · O(n²)
  3. 3. C · O(n log n)
  4. 4. B · Mergesort
  5. 5. B · Insertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  6. 6. B · O(n)
  7. 7. B · X zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
  8. 8. A · O(n² 2ⁿ)

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