Werkblad Algoritmen & complexiteit met antwoorden

Wat is het basisgeval van een recursieve functie?

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

Wat is de best-case tijdcomplexiteit van insertion sort op een al gesorteerde array?

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

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Wat is de worst-case tijdcomplexiteit van quicksort?

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

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

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

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

1. AInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
2. BInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
3. CRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
4. DInsertion sort is in het slechtste geval O(n log n)

Van welk van deze vervulbaarheidsproblemen is bekend dat het in polynomiale tijd oplosbaar is?

1. ACircuitvervulbaarheid
2. B2-SAT, waarbij elke clausule hoogstens twee literalen heeft
3. CAlgemene SAT op formules in conjunctieve normaalvorm
4. D3-SAT, waarbij elke clausule precies drie literalen heeft

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

1. ABinair zoeken heeft minstens twee keer zoveel geheugen nodig
2. BGelinkte lijsten kunnen niet worden gesorteerd
3. CHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
4. DVergelijkingen op knopen van een gelinkte lijst zijn trager