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

Ruimtecomplexiteit meet:

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

Wat is een brute-force-algoritme?

  1. AEen algoritme dat op veel processoren draait
  2. BEen algoritme dat altijd recursie gebruikt
  3. CEen algoritme dat willekeurig een antwoord raadt
  4. DEen algoritme dat alle mogelijke kandidaatoplossingen probeert
3.Makkelijk

De looptijd van een algoritme is O(n). Hoe heet deze groei?

  1. AConstant
  2. BLineair
  3. CKwadratisch
  4. DLogaritmisch
4.Gemiddeld

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

  1. AO(V + E)
  2. BO(V³ × E)
  3. CO(E log V)
  4. DO(V × E)
5.Gemiddeld

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

  1. AEen array die al gesorteerd is
  2. BEen array van lengte 2
  3. CEen array in willekeurige volgorde
  4. DEen array waarvan alle elementen verschillend zijn
6.Gemiddeld

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

  1. ANee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
  2. BNee, omdat n³ voor grote n kleiner is dan n²
  3. CJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  4. DJa, maar alleen als n kleiner is dan 100
7.Moeilijk

Voor welke variant van het knapzakprobleem geeft de gulzige regel "neem items in volgorde van waarde per gewicht" altijd een optimaal antwoord?

  1. ADe 0/1-knapzak, waarbij items altijd in hun geheel moeten worden genomen
  2. BGeen van beide varianten
  3. CBeide varianten
  4. DDe fractionele knapzak, waarbij items mogen worden opgesplitst
8.Moeilijk

Welk algoritme vindt een minimaal opspannende boom door herhaaldelijk de goedkoopste kant toe te voegen die geen cyclus vormt?

  1. AHet algoritme van Dijkstra
  2. BHet algoritme van Prim vanuit één knoop
  3. CHet algoritme van Kruskal
  4. DFloyd-Warshall

Antwoordenblad

  1. 1. C · De hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
  2. 2. D · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  3. 3. B · Lineair
  4. 4. D · O(V × E)
  5. 5. A · Een array die al gesorteerd is
  6. 6. C · Ja, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  7. 7. D · De fractionele knapzak, waarbij items mogen worden opgesplitst
  8. 8. C · Het algoritme van Kruskal

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