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(n³)
  4. DO(3n²)
2.Makkelijk

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

  1. A6 seconden
  2. B9 seconden
  3. C3 seconden
  4. D12 seconden
3.Makkelijk

Een probleem heet meestal handelbaar (tractable) als:

  1. AHet geen oplossing heeft
  2. BHet in constante tijd kan worden opgelost
  3. CHet in polynomiale tijd kan worden opgelost
  4. DHet alleen kan worden opgelost door elke mogelijkheid te proberen
4.Gemiddeld

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

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

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

  1. AEen topologische volgorde in alle grafen
  2. BKortste paden in grafen met negatieve kantgewichten
  3. CDe minimaal opspannende boom
  4. DKortste paden in aantal kanten vanaf de startknoop
6.Gemiddeld

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

  1. AO(n log n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
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. BDe pivot uniform willekeurig kiezen
  3. CDe invoer sorteren voordat je quicksort uitvoert
  4. DAltijd het eerste element kiezen
8.Moeilijk

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

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

Antwoordenblad

  1. 1. A · O(n²)
  2. 2. A · 6 seconden
  3. 3. C · Het in polynomiale tijd kan worden opgelost
  4. 4. B · Ze blijft zichzelf aanroepen totdat de call stack overloopt
  5. 5. D · Kortste paden in aantal kanten vanaf de startknoop
  6. 6. A · O(n log n)
  7. 7. B · De pivot uniform willekeurig kiezen
  8. 8. B · n = o(n²), maar n is niet o(n)

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