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 soort datastructuur
  2. BEen functie die zichzelf aanroept op kleinere invoer
  3. CEen sorteermethode
  4. DEen lus die nooit eindigt
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. B12 seconden
  3. C3 seconden
  4. D9 seconden
3.Makkelijk

Wat is memoisatie?

  1. AGeheugen vrijgeven nadat een functie is teruggekeerd
  2. BCommentaar schrijven naast elke regel code
  3. CRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
  4. DResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
4.Gemiddeld

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

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

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

  1. AO(V³ × E)
  2. BO(V × E)
  3. CO(E log V)
  4. DO(V + E)
6.Gemiddeld

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

  1. AEén enkele lus
  2. BAlleen willekeurige invoer
  3. COverlappende deelproblemen en optimale substructuur
  4. DHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
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. AJa, de ondergrens is dus fout
  2. BJa, maar alleen voor arrays korter dan 100
  3. CNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
  4. DNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
8.Moeilijk

Welke techniek geeft quicksort een verwachte looptijd van O(n log n) voor elke invoer?

  1. AAltijd het eerste element kiezen
  2. BDe invoer sorteren voordat je quicksort uitvoert
  3. CAlleen recursie aan de linkerkant gebruiken
  4. DDe pivot uniform willekeurig kiezen

Antwoordenblad

  1. 1. B · Een functie die zichzelf aanroept op kleinere invoer
  2. 2. A · 6 seconden
  3. 3. D · Resultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
  4. 4. C · O(2ⁿ)
  5. 5. B · O(V × E)
  6. 6. C · Overlappende deelproblemen en optimale substructuur
  7. 7. C · Nee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
  8. 8. D · De pivot uniform willekeurig kiezen

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