Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

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

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 alle mogelijke kandidaatoplossingen probeert
4. DEen algoritme dat op veel processoren draait

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

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

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)

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

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

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

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

Karatsuba-vermenigvuldiging voldoet aan T(n) = 3T(n/2) + O(n). Wat is de oplossing?

1. AΘ(n^{log₂ 3}), ongeveer n^1,585
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n log n)

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. CVergelijkingen op knopen van een gelinkte lijst zijn trager
4. DHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is