Werkblad Algoritmen & complexiteit met antwoorden

Gratis printbaar werkblad Algoritmen & complexiteit: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Wat is memoisatie?

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

Welke complexiteitsklasse groeit het snelst voor grote n?

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

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

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(V³ × E)
  3. CO(E log V)
  4. DO(V + E)
5.Gemiddeld

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)
6.Gemiddeld

Wat betekent het dat een probleem een optimale deelstructuur heeft?

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

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

Welke bewering over P en NP is juist?

  1. AOplossingen van NP-problemen kunnen niet snel worden geverifieerd
  2. BNP betekent "niet polynomiaal"
  3. CEr is bewezen dat P ≠ NP
  4. DElk probleem in P zit ook in NP

Antwoordenblad

  1. 1. C · Resultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
  2. 2. C · O(2ⁿ)
  3. 3. C · O(n²)
  4. 4. A · O(V × E)
  5. 5. B · O(n³)
  6. 6. B · Een optimale oplossing kan worden opgebouwd uit optimale oplossingen van de deelproblemen
  7. 7. C · Het is NP-moeilijk
  8. 8. D · Elk probleem in P zit ook in NP

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.