Werkblad Algoritmen & complexiteit met antwoorden

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

1. AQuicksort
2. BBubblesort
3. CHeapsort
4. DMergesort

Wat is de tijdcomplexiteit van binair zoeken in een gesorteerde array?

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

Hoe heet groei van O(2ⁿ)?

1. ALineair
2. BPolynomiaal
3. CExponentieel
4. DLogaritmisch

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

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

Wat is de worst-case tijdcomplexiteit van quicksort?

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

1. AJa, maar alleen als n kleiner is dan 100
2. BJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
3. CNee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
4. DNee, omdat n³ voor grote n kleiner is dan n²

Welke uitspraak over het selecteren van het k-de kleinste element van een ongesorteerde array is juist?

1. AQuickselect loopt in het slechtste geval in O(log n), omdat het maar aan één kant van de pivot recursief verdergaat
2. BQuickselect loopt verwacht in O(n), en median-of-medians garandeert O(n) in het slechtste geval
3. CSelectie heeft altijd Ω(n log n) nodig, omdat er gesorteerd moet worden
4. DSelectie is alleen mogelijk in O(n²)

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(n) ruimte
2. BO(n) tijd en O(1) ruimte
3. CO(log n) tijd en O(n) ruimte
4. DO(2ⁿ) tijd en O(1) ruimte