Werkblad Algoritmen & complexiteit met antwoorden

Hoe heet groei van O(2ⁿ)?

1. ALineair
2. BLogaritmisch
3. CExponentieel
4. DPolynomiaal

Wat is het basisgeval van een recursieve functie?

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

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(1)
4. DO(n²)

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

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

1. AOverlappende deelproblemen en optimale substructuur
2. BEén enkele lus
3. CAlleen willekeurige invoer
4. DHelemaal geen deelproblemen, dus het kan in één stap worden opgelost

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

1. AKortste paden in grafen met negatieve kantgewichten
2. BEen topologische volgorde in alle grafen
3. CKortste paden in aantal kanten vanaf de startknoop
4. DDe minimaal opspannende boom

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

1. AO(2^n²)
2. BO(n³)
3. CO(n!)
4. DO(n² 2ⁿ)

Wat zijn de tijd- en ruimtekosten van het berekenen van het n-de Fibonaccigetal met een lus die alleen de laatste twee waarden bewaart?

1. AO(n) tijd en O(1) ruimte
2. BO(log n) tijd en O(n) ruimte
3. CO(2ⁿ) tijd en O(1) ruimte
4. DO(n) tijd en O(n) ruimte