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

Wat is de looptijd van counting sort voor n gehele getallen in het bereik 0 tot k?

  1. AO(k log n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(n + k)
3.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
  2. BOngeveer n²
  3. COngeveer n
  4. DOngeveer log₂ n
4.Gemiddeld

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

  1. AHet algoritme van Kruskal
  2. BHet algoritme van Dijkstra
  3. CDiepte-eerst zoeken (DFS)
  4. DBellman-Ford is in alle gevallen vereist
5.Gemiddeld

Wat is de tijdcomplexiteit van: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

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

Hoe wordt het handelsreizigersprobleem geclassificeerd?

  1. ADe beslissingsversie zit in P, maar de optimalisatieversie is NP-volledig
  2. BDe beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
  3. CHet zit in P, omdat het algoritme van Dijkstra het oplost door elke stad één keer te bezoeken
  4. DHet is onbeslisbaar
8.Moeilijk

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

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

Antwoordenblad

  1. 1. B · O(log n)
  2. 2. D · O(n + k)
  3. 3. D · Ongeveer log₂ n
  4. 4. B · Het algoritme van Dijkstra
  5. 5. D · O(n log n)
  6. 6. A · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  7. 7. B · De beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
  8. 8. D · n = o(n²), maar n is niet o(n)

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