Werkblad Algoritmen & complexiteit met antwoorden

Wat is het basisgeval van een recursieve functie?

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

Hoe werkt selection sort?

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

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

1. ABellman-Ford is in alle gevallen vereist
2. BDiepte-eerst zoeken (DFS)
3. CHet algoritme van Dijkstra
4. DHet algoritme van Kruskal

Hoeveel niveaus heeft de recursie van mergesort voor een array van n elementen?

1. AOngeveer √n
2. BOngeveer n / 2
3. COngeveer n
4. DOngeveer log₂ n

Wat is de tijdcomplexiteit van het vermenigvuldigen van twee n × n-matrices met de standaard drievoudige lus?

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

Kortste enkelvoudige paden kunnen in polynomiale tijd worden gevonden. Wat is bekend over het vinden van het langste enkelvoudige pad tussen twee knopen in een algemene graaf?

1. AHet is altijd oplosbaar in O(V + E)
2. BHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten
3. CHet is onbeslisbaar
4. DHet is NP-moeilijk

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