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 grote O van 3n² + 5n + 2?

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

Welke van deze looptijden is polynomiaal?

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

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

  1. A1 seconde
  2. B4 seconden
  3. C8 seconden
  4. D2 seconden
4.Gemiddeld

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

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

  1. AO(n log n)
  2. BO(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

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

  1. ANee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
  2. BJa, de ondergrens is dus fout
  3. CNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
  4. DJa, maar alleen voor arrays korter dan 100
8.Moeilijk

Wat is de tijdcomplexiteit van het opbouwen van een binaire heap uit n ongesorteerde elementen met de bottom-upmethode?

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

Antwoordenblad

  1. 1. D · O(n²)
  2. 2. A · O(n³)
  3. 3. B · 4 seconden
  4. 4. C · O(n log n)
  5. 5. B · O(n)
  6. 6. A · Kortste paden tussen alle paren knopen in O(V³)
  7. 7. C · Nee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
  8. 8. B · O(n)

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