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

Welke complexiteitsklasse groeit het snelst voor grote n?

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

Ruimtecomplexiteit meet:

  1. ADe schijfruimte van het programmabestand nadat het is gecompileerd
  2. BDe fysieke grootte van de computer
  3. CDe hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
  4. DHet aantal regels code
3.Makkelijk

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

  1. AQuicksort
  2. BBubblesort
  3. CHeapsort
  4. DMergesort
4.Gemiddeld

Wat is de tijdcomplexiteit van: for i = 1 to n: for j = 1 to i: doe O(1) werk?

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

Welk sorteeralgoritme is stabiel?

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

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

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

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

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

Waarom kan het algoritme van Dijkstra verkeerde resultaten geven als sommige kantgewichten negatief zijn?

  1. AHet werkt alleen op ongerichte grafen
  2. BEen knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven
  3. CNegatieve getallen kunnen niet in een prioriteitswachtrij worden opgeslagen
  4. DHet raakt bij elke negatieve kant in een oneindige lus

Antwoordenblad

  1. 1. C · O(2ⁿ)
  2. 2. C · De hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
  3. 3. B · Bubblesort
  4. 4. D · O(n²)
  5. 5. B · Mergesort
  6. 6. C · Kortste paden tussen alle paren knopen in O(V³)
  7. 7. D · Θ(n log² n)
  8. 8. B · Een knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven

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