Werkblad Algoritmen & complexiteit met antwoorden

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

1. AInsertion sort
2. BBubblesort
3. CQuicksort
4. DMergesort

Wat vereist binair zoeken van de invoer?

1. ADe lengte van de array moet een macht van twee zijn
2. BDe array moet gesorteerd zijn
3. CDe array mag niet meer dan 1000 elementen hebben
4. DDe array mag alleen positieve getallen bevatten

Ruimtecomplexiteit meet:

1. ADe fysieke grootte van de computer
2. BDe schijfruimte van het programmabestand nadat het is gecompileerd
3. CDe hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
4. DHet aantal regels code

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

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

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

Wat meet geamortiseerde analyse?

1. ADe verwachte kosten over willekeurige invoer
2. BDe kosten van een algoritme bij de beste invoer
3. CDe kosten van de ene duurste bewerking ergens in de reeks
4. DDe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen

Wat is de looptijd van het algoritme van Dijkstra met een binaire heap op een graaf met V knopen en E kanten?

1. AO(V³)
2. BO(V × E)
3. CO((V + E) log V)
4. DO(V + E)

Waarom is een opzoeking in een hashtabel gemiddeld O(1) maar in het slechtste geval O(n)?

1. AHashfuncties zijn traag
2. BVeel sleutels kunnen in dezelfde bucket botsen
3. CSleutels moeten eerst gesorteerd worden
4. DArrays hebben O(n) toegang