Werkblad Algoritmen & complexiteit met antwoorden

Wat is een brute-force-algoritme?

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

Hoe werkt selection sort?

1. AHet splitst de array in helften en voegt die samen
2. BHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan
3. CHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
4. DHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren

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

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

Hoeveel stackruimte gebruikt een eenvoudige recursieve faculteitsfunctie fact(n) = n × fact(n − 1)?

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

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(mn)
4. DO(m + n)

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

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

Wat zou er volgen als iemand een algoritme in polynomiale tijd vond voor één NP-volledig probleem?

1. AHet stopprobleem zou beslisbaar worden
2. BAlleen dat ene probleem zou naar P verhuizen
3. CElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
4. DAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen

Waarom kan het algoritme van Dijkstra verkeerde resultaten geven als sommige kantgewichten negatief zijn?

1. ANegatieve getallen kunnen niet in een prioriteitswachtrij worden opgeslagen
2. BEen knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven
3. CHet werkt alleen op ongerichte grafen
4. DHet raakt bij elke negatieve kant in een oneindige lus