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

Welke van deze looptijden is polynomiaal?

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

Welke notatie beschrijft een bovengrens voor de groei?

  1. AKleine omega (little omega)
  2. BGrote Theta (Big Theta)
  3. CGrote O (Big O)
  4. DGrote Omega (Big Omega)
3.Makkelijk

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

  1. ADynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
  2. BMergesort heeft geen recursieve structuur
  3. CMergesort is al O(n)
  4. DDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
5.Gemiddeld

De ondergrens voor sorteren op basis van vergelijkingen in het slechtste geval is:

  1. AΩ(n log n)
  2. BΩ(n)
  3. CΩ(log n)
  4. DΩ(n²)
6.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(n log n + k log n)
  2. BO(k n log n)
  3. CO(nk)
  4. DO(n + k)
7.Moeilijk

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

  1. AX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
  2. BX reduceert tot een probleem in P, en X zit in NP
  3. CX zit in P, en X reduceert tot SAT
  4. DX heeft geen polynomiaal algoritme, en X is beslisbaar
8.Moeilijk

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

  1. AVergelijkingen op knopen van een gelinkte lijst zijn trager
  2. BBinair zoeken heeft minstens twee keer zoveel geheugen nodig
  3. CGelinkte lijsten kunnen niet worden gesorteerd
  4. DHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is

Antwoordenblad

  1. 1. A · O(n³)
  2. 2. C · Grote O (Big O)
  3. 3. D · O(n²)
  4. 4. D · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  5. 5. A · Ω(n log n)
  6. 6. A · O(n log n + k log n)
  7. 7. A · X zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
  8. 8. D · Het middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is

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