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 lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Welke notatie beschrijft een bovengrens voor de groei?

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

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. AMergesort
  2. BBubblesort
  3. CInsertion sort
  4. DQuicksort
4.Gemiddeld

Wat is de tijdcomplexiteit van het vermenigvuldigen van twee n × n-matrices met de standaard drievoudige lus?

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

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

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

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

  1. AO(log n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(n)
7.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²), maar n is niet o(n)
  3. Cn² = o(n)
  4. D2n = o(n), omdat 2n langzaam groeit
8.Moeilijk

Wat zijn de geamortiseerde kosten van het ophogen van een binaire teller, als één ophoging veel bits kan omzetten?

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

Antwoordenblad

  1. 1. A · O(n)
  2. 2. A · Grote O (Big O)
  3. 3. D · Quicksort
  4. 4. B · O(n³)
  5. 5. B · Kortste paden tussen alle paren knopen in O(V³)
  6. 6. D · O(n)
  7. 7. B · n = o(n²), maar n is niet o(n)
  8. 8. B · O(1) per ophoging

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