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 diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

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

Welke complexiteitsklasse groeit het snelst voor grote n?

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

Een O(n)-algoritme doet 3 seconden over n = 1 miljoen. Hoe lang doet het ongeveer over n = 2 miljoen?

  1. A9 seconden
  2. B3 seconden
  3. C6 seconden
  4. D12 seconden
4.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²)
5.Gemiddeld

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

  1. AZe blijft zichzelf aanroepen totdat de call stack overloopt
  2. BZe loopt in O(1) tijd
  3. CDe compiler maakt er altijd een lus van die veilig eindigt
  4. DZe geeft automatisch 0 terug
6.Gemiddeld

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

  1. AKortste paden vanuit één bronknoop naar alle andere in O(V + E)
  2. BKortste paden tussen alle paren knopen in O(V³)
  3. CEen minimale opspannende boom in O(E log V)
  4. DEen topologische ordening in O(V²)
7.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³)
  3. CO(V × E)
  4. DO((V + E) log V)
8.Moeilijk

Welke definitie van de klasse P is juist?

  1. AProblemen waarvan oplossingen wel kunnen worden gecontroleerd maar nooit in polynomiale tijd gevonden
  2. BProblemen die op elke computer exponentiële tijd nodig hebben
  3. CProblemen die parallel kunnen worden opgelost
  4. DBeslissingsproblemen die door een deterministisch algoritme in polynomiale tijd kunnen worden opgelost

Antwoordenblad

  1. 1. D · O(V + E)
  2. 2. C · O(2ⁿ)
  3. 3. C · 6 seconden
  4. 4. D · O(n²)
  5. 5. A · Ze blijft zichzelf aanroepen totdat de call stack overloopt
  6. 6. B · Kortste paden tussen alle paren knopen in O(V³)
  7. 7. D · O((V + E) log V)
  8. 8. D · Beslissingsproblemen die door een deterministisch algoritme in polynomiale tijd kunnen worden opgelost

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