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 log₂ 1024?

  1. A32
  2. B10
  3. C512
  4. D12
2.Makkelijk

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

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

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

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

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

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

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

  1. AO(n²)
  2. BO(n)
  3. CO(n log n)
  4. DO(n³)
6.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 3 munten; het optimum is 2
  2. BGulzig gebruikt 2 munten; het optimum is 2
  3. CGulzig gebruikt 3 munten; het optimum is 3
  4. DGulzig gebruikt 4 munten; het optimum is 3
7.Moeilijk

Welke uitspraak over de kleine-o-notatie is juist?

  1. A2n = o(n), omdat 2n langzaam groeit
  2. Bn = o(n²), maar n is niet o(n)
  3. Cn = o(n), omdat elke functie kleine o van zichzelf is
  4. Dn² = o(n)
8.Moeilijk

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

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

Antwoordenblad

  1. 1. B · 10
  2. 2. A · O(n)
  3. 3. D · f groeit even snel als g, van boven en van onderen begrensd door constante veelvouden van g
  4. 4. C · O(n log n + k log n)
  5. 5. A · O(n²)
  6. 6. A · Gulzig gebruikt 3 munten; het optimum is 2
  7. 7. B · n = o(n²), maar n is niet o(n)
  8. 8. A · Θ(n³)

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