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 binair zoeken in een gesorteerde array?

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

Wat vereist binair zoeken van de invoer?

  1. ADe array moet gesorteerd zijn
  2. BDe array mag alleen positieve getallen bevatten
  3. CDe array mag niet meer dan 1000 elementen hebben
  4. DDe lengte van de array moet een macht van twee zijn
3.Makkelijk

Een element in een array via de index benaderen kost:

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

  1. AJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  2. BNee, omdat n³ voor grote n kleiner is dan n²
  3. CNee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
  4. DJa, maar alleen als n kleiner is dan 100
5.Gemiddeld

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

  1. AO(2ⁿ)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
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²)
  4. DO(n log n)
7.Moeilijk

Hoe detecteert het algoritme van Bellman-Ford een cykel met negatief gewicht die vanuit de bron bereikbaar is?

  1. ANa V − 1 rondes controleert het of er nog een kant kan worden gerelaxeerd
  2. BHet telt de cykels met diepte-eerst zoeken
  3. CHet controleert of er een kant met negatief gewicht is
  4. DHet voert het algoritme van Dijkstra twee keer uit en vergelijkt de twee afstandsresultaten
8.Moeilijk

Topologisch sorteren is alleen mogelijk voor:

  1. AGerichte acyclische grafen (DAG)
  2. BVolledige grafen
  3. CGrafen met negatieve gewichten
  4. DOngerichte grafen

Antwoordenblad

  1. 1. A · O(log n)
  2. 2. A · De array moet gesorteerd zijn
  3. 3. C · O(1)
  4. 4. A · Ja, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  5. 5. C · O(n²)
  6. 6. B · O(n)
  7. 7. A · Na V − 1 rondes controleert het of er nog een kant kan worden gerelaxeerd
  8. 8. A · Gerichte acyclische grafen (DAG)

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