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 grote O van 3n² + 5n + 2?

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

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

Wat is de tijdcomplexiteit van het vermenigvuldigen van twee n × n-matrices met de standaard drievoudige lus?

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

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

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

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

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

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

  1. AHet stopprobleem zou beslisbaar worden
  2. BAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen
  3. CElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
  4. DAlleen dat ene probleem zou naar P verhuizen
8.Moeilijk

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

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

Antwoordenblad

  1. 1. A · O(n²)
  2. 2. B · O(n)
  3. 3. B · O(n)
  4. 4. C · O(n³)
  5. 5. B · O(2ⁿ)
  6. 6. A · O(d(n + k))
  7. 7. C · Elk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
  8. 8. B · Θ(n log² n)

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