Werkblad Algoritmen & complexiteit met antwoorden

Wat is het basisgeval van een recursieve functie?

1. ADe eerste regel van de functie
2. BEen geval dat direct wordt beantwoord zonder nog een recursieve aanroep
3. CDe aanroep die het meeste geheugen gebruikt
4. DHet geval met de grootste invoer, dat vóór alle recursieve aanroepen wordt afgehandeld

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Wat is een brute-force-algoritme?

1. AEen algoritme dat altijd recursie gebruikt
2. BEen algoritme dat op veel processoren draait
3. CEen algoritme dat alle mogelijke kandidaatoplossingen probeert
4. DEen algoritme dat willekeurig een antwoord raadt

Ongeveer hoeveel vergelijkingen heeft binair zoeken in het slechtste geval nodig in een gesorteerde array van 1,000,000 elementen?

1. AOngeveer 1,000
2. BOngeveer 20
3. COngeveer 500,000
4. DOngeveer 100

Een functie voert één lus van n iteraties uit en daarna, los daarvan, nog een lus van n iteraties. Wat is de tijdcomplexiteit?

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. AMergesort is al O(n)
2. BDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
3. CDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
4. DMergesort heeft geen recursieve structuur

Topologisch sorteren is alleen mogelijk voor:

1. AGerichte acyclische grafen (DAG)
2. BVolledige grafen
3. COngerichte grafen
4. DGrafen met negatieve gewichten

Wat heeft de stelling van Cook-Levin vastgesteld?

1. AHet booleaanse vervulbaarheidsprobleem (SAT) is NP-volledig
2. BHet stopprobleem is onbeslisbaar
3. CElk NP-probleem kan in exponentiële tijd worden opgelost
4. DP is niet gelijk aan NP