Werkblad Algoritmen & complexiteit met antwoorden

Welke ontwerpstrategie gebruikt mergesort?

1. AVerdeel en heers
2. BDynamisch programmeren
3. CBrute kracht
4. DGulzige keuze (greedy)

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

1. AMergesort
2. BBubblesort
3. CInsertion sort
4. DQuicksort

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

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

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

Wat betekent het dat een probleem een optimale deelstructuur heeft?

1. AElk deelprobleem heeft dezelfde grootte
2. BHet probleem heeft precies één optimale oplossing, die alle deelproblemen delen
3. CHet probleem kan in constante tijd worden opgelost
4. DEen optimale oplossing kan worden opgebouwd uit optimale oplossingen van de deelproblemen

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

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

Waarom heeft elke zoekmethode op basis van vergelijkingen in een gesorteerde array in het slechtste geval Ω(log n) vergelijkingen nodig?

1. AEen beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
2. BElk element moet minstens één keer worden vergeleken
3. CElke vergelijking kost logaritmische tijd
4. DBinair zoeken is het enige mogelijke algoritme en heeft log₂ n vergelijkingen nodig

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 NP-moeilijk
2. BHet is onbeslisbaar
3. CHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten
4. DHet is altijd oplosbaar in O(V + E)