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

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

  1. AOngeveer n
  2. BOngeveer n²
  3. COngeveer n / 2
  4. DOngeveer log₂ n
2.Makkelijk

Welke notatie beschrijft een bovengrens voor de groei?

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

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

  1. ABubblesort
  2. BQuicksort
  3. CHeapsort
  4. DMergesort
4.Gemiddeld

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

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

Wat berekent het algoritme van Floyd-Warshall, en hoe snel?

  1. AKortste paden tussen alle paren knopen in O(V³)
  2. BEen minimale opspannende boom in O(E log V)
  3. CKortste paden vanuit één bronknoop naar alle andere in O(V + E)
  4. DEen topologische ordening in O(V²)
6.Gemiddeld

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(n)
  4. DO(2ⁿ)
7.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. CHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  4. DGelinkte lijsten kunnen niet worden gesorteerd
8.Moeilijk

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

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

Antwoordenblad

  1. 1. D · Ongeveer log₂ n
  2. 2. D · Grote O (Big O)
  3. 3. A · Bubblesort
  4. 4. B · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  5. 5. A · Kortste paden tussen alle paren knopen in O(V³)
  6. 6. A · O(n²)
  7. 7. C · Het middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  8. 8. A · n = o(n²), maar n is niet o(n)

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