Werkblad Algoritmen & complexiteit met antwoorden

Wat is recursie?

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

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

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)

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

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

In een gesorteerde array zoek je twee elementen die samen een doelwaarde opleveren door vanaf elk uiteinde een pointer naar binnen te bewegen. Wat is de tijdcomplexiteit?

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

Wat betekent het dat een probleem een optimale deelstructuur heeft?

1. AHet probleem kan in constante tijd worden opgelost
2. BElk deelprobleem heeft dezelfde grootte
3. CHet probleem heeft precies één optimale oplossing, die alle deelproblemen delen
4. DEen optimale oplossing kan worden opgebouwd uit optimale oplossingen van de deelproblemen

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. CDe pivot uniform willekeurig kiezen
4. DAlleen recursie aan de linkerkant gebruiken

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² 2ⁿ)
3. CO(2^n²)
4. DO(n!)