Werkblad Algoritmen & complexiteit met antwoorden

Wat beschrijft de worst-case looptijd van een algoritme?

1. ADe tijd die het nodig heeft voor de kleinste invoer
2. BDe tijd die het nodig heeft op een trage computer
3. CDe verwachte tijd die het nodig heeft voor een willekeurige invoer van grootte n
4. DDe maximale tijd die het nodig heeft over alle invoeren van grootte n

Wat vereist binair zoeken van de invoer?

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

Wat is een brute-force-algoritme?

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

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + O(1)?

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

Een gretig (greedy) algoritme:

1. AGeeft altijd de optimale oplossing
2. BMaakt bij elke stap de lokaal beste keuze
3. CGebruikt alleen recursie
4. DProbeert elke mogelijke oplossing

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(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

Het stopprobleem (halting problem) laat zien dat:

1. ASommige programma's sneller draaien op snellere computers, dus stoppen hangt van de hardware af
2. BGeen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt
3. CElk programma uiteindelijk stopt
4. DLussen vermeden moeten worden

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

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