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 recursie?

  1. AEen sorteermethode
  2. BEen soort datastructuur
  3. CEen lus die nooit eindigt
  4. DEen functie die zichzelf aanroept op kleinere invoer
2.Makkelijk

Een probleem heet meestal handelbaar (tractable) als:

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

Wat is de tijdcomplexiteit van binair zoeken in een gesorteerde array?

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

Hoe bouwt het algoritme van Prim een minimale opspannende boom?

  1. AHet verwijdert de duurste kant totdat er geen cykels meer zijn
  2. BHet sorteert alle kanten op gewicht en voegt elke kant toe, tenzij die een cykel in het bos zou vormen
  3. CHet voert breedte-eerst zoeken uit en houdt de BFS-boom over
  4. DHet laat één boom groeien vanaf een startknoop en voegt de goedkoopste kant toe die de boom verlaat
5.Gemiddeld

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

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

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

  1. AO(dn log k)
  2. BO(n²)
  3. CO(n log n)
  4. DO(d(n + k))
7.Moeilijk

Het algoritme van Held-Karp voor dynamisch programmeren lost het handelsreizigersprobleem exact op. Wat is de looptijd voor n steden?

  1. AO(n³)
  2. BO(n!)
  3. CO(n² 2ⁿ)
  4. DO(2n²)
8.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³)
  2. BO(V + E)
  3. CO(V × E)
  4. DO((V + E) log V)

Antwoordenblad

  1. 1. D · Een functie die zichzelf aanroept op kleinere invoer
  2. 2. A · Het in polynomiale tijd kan worden opgelost
  3. 3. B · O(log n)
  4. 4. D · Het laat één boom groeien vanaf een startknoop en voegt de goedkoopste kant toe die de boom verlaat
  5. 5. C · Ze blijft zichzelf aanroepen totdat de call stack overloopt
  6. 6. D · O(d(n + k))
  7. 7. C · O(n² 2ⁿ)
  8. 8. D · O((V + E) log V)

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