Werkblad Algoritmen & complexiteit met antwoorden

Wat is memoisatie?

1. AResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
2. BRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
3. CGeheugen vrijgeven nadat een functie is teruggekeerd
4. DCommentaar schrijven naast elke regel code

Welke ontwerpstrategie gebruikt mergesort?

1. AGulzige keuze (greedy)
2. BDynamisch programmeren
3. CBrute kracht
4. DVerdeel en heers

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Hoeveel niveaus heeft de recursie van mergesort voor een array van n elementen?

1. AOngeveer √n
2. BOngeveer n
3. COngeveer log₂ n
4. DOngeveer n / 2

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²)

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

Welke uitspraak over de kleine-o-notatie is juist?

1. An² = o(n)
2. Bn = o(n), omdat elke functie kleine o van zichzelf is
3. Cn = o(n²), maar n is niet o(n)
4. D2n = o(n), omdat 2n langzaam groeit

Welke definitie van de klasse NP is juist?

1. AProblemen die niet in polynomiale tijd kunnen worden opgelost
2. BProblemen die niet polynomiaal zijn
3. CProblemen die geen enkel algoritme kan oplossen
4. DBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd