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 de tijdcomplexiteit van binair zoeken in een gesorteerde array?

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

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

  1. AHeapsort
  2. BBubblesort
  3. CMergesort
  4. DQuicksort
3.Makkelijk

Welke van deze looptijden is polynomiaal?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n!)
  4. DO(n³)
4.Gemiddeld

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

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

  1. AAlleen willekeurige invoer
  2. BOverlappende deelproblemen en optimale substructuur
  3. CHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
  4. DEén enkele lus
6.Gemiddeld

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

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

Wat zijn de geamortiseerde kosten van het ophogen van een binaire teller, als één ophoging veel bits kan omzetten?

  1. AO(1) per ophoging
  2. BO(n) per ophoging
  3. CO(log n) per ophoging
  4. DO(n log n) per ophoging
8.Moeilijk

Wat zou er volgen als iemand een algoritme in polynomiale tijd vond voor één NP-volledig probleem?

  1. AAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen
  2. BElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
  3. CAlleen dat ene probleem zou naar P verhuizen
  4. DHet stopprobleem zou beslisbaar worden

Antwoordenblad

  1. 1. A · O(log n)
  2. 2. B · Bubblesort
  3. 3. D · O(n³)
  4. 4. A · O(log n)
  5. 5. B · Overlappende deelproblemen en optimale substructuur
  6. 6. C · Een array die al gesorteerd is
  7. 7. A · O(1) per ophoging
  8. 8. B · Elk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP

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