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 het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

De looptijd van een algoritme is O(n). Hoe heet deze groei?

  1. AKwadratisch
  2. BLineair
  3. CLogaritmisch
  4. DConstant
3.Makkelijk

Wat is de grote O van 3n² + 5n + 2?

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

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

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

Wat is de worst-case tijdcomplexiteit van quicksort?

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

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

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

Welke techniek geeft quicksort een verwachte looptijd van O(n log n) voor elke invoer?

  1. AAlleen recursie aan de linkerkant gebruiken
  2. BAltijd het eerste element kiezen
  3. CDe pivot uniform willekeurig kiezen
  4. DDe invoer sorteren voordat je quicksort uitvoert
8.Moeilijk

Wat is de looptijd van het algoritme van Dijkstra met een binaire heap op een graaf met V knopen en E kanten?

  1. AO(V × E)
  2. BO(V + E)
  3. CO((V + E) log V)
  4. DO(V³)

Antwoordenblad

  1. 1. D · O(n)
  2. 2. B · Lineair
  3. 3. A · O(n²)
  4. 4. C · Het algoritme van Dijkstra
  5. 5. A · O(n²)
  6. 6. A · Kortste paden tussen alle paren knopen in O(V³)
  7. 7. C · De pivot uniform willekeurig kiezen
  8. 8. C · O((V + E) log V)

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