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(n)
  3. CO(n log n)
  4. DO(1)
2.Makkelijk

Wat is een brute-force-algoritme?

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

Wat betekent f(n) = Θ(g(n))?

  1. Af groeit strikt sneller dan g
  2. Bf groeit strikt langzamer dan g
  3. Cf groeit even snel als g, van boven en van onderen begrensd door constante veelvouden van g
  4. Df is voor elke n altijd kleiner dan g, dus g begrenst f van boven maar nooit van onderen
4.Gemiddeld

Welk sorteeralgoritme is stabiel?

  1. AHeapsort
  2. BSelectionsort (gangbare versie)
  3. CQuicksort (gangbare in-place-versie)
  4. DMergesort
5.Gemiddeld

Met munten van 1, 3 en 4 en een bedrag van 6: hoeveel munten gebruikt de gulzige methode "grootste munt eerst", vergeleken met het optimum?

  1. AGulzig gebruikt 4 munten; het optimum is 3
  2. BGulzig gebruikt 3 munten; het optimum is 2
  3. CGulzig gebruikt 2 munten; het optimum is 2
  4. DGulzig gebruikt 3 munten; het optimum is 3
6.Gemiddeld

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

  1. AO(n²)
  2. BO(2ⁿ)
  3. CO(n log n)
  4. DO(n)
7.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. BHet stopprobleem zou beslisbaar worden
  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)
  2. BΘ(n log² n)
  3. CΘ(n²)
  4. DΘ(n log n)

Antwoordenblad

  1. 1. A · O(log n)
  2. 2. A · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  3. 3. C · f groeit even snel als g, van boven en van onderen begrensd door constante veelvouden van g
  4. 4. D · Mergesort
  5. 5. B · Gulzig gebruikt 3 munten; het optimum is 2
  6. 6. B · O(2ⁿ)
  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.