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 een algoritme?

  1. AEen eindige reeks goed gedefinieerde stappen die een probleem oplost
  2. BElk computerprogramma met een grafische interface
  3. CEen datastructuur die getallen opslaat
  4. DEen programmeertaal die is ontworpen om wiskundige formules te schrijven
2.Makkelijk

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

  1. AO(mn)
  2. BO(mn log n)
  3. CO(2m+n)
  4. DO(m + n)
5.Gemiddeld

Wat is de tijdcomplexiteit van: for i = 1 to n: for j = 1 to i: doe O(1) werk?

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

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

  1. ADiepte-eerst zoeken (DFS)
  2. BHet algoritme van Kruskal
  3. CBellman-Ford is in alle gevallen vereist
  4. DHet algoritme van Dijkstra
7.Moeilijk

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + n log n?

  1. AΘ(n)
  2. BΘ(n log n)
  3. CΘ(n²)
  4. DΘ(n log² n)
8.Moeilijk

Hoe verhouden n! en 2ⁿ zich voor grote n?

  1. AZe groeien even snel
  2. Bn! groeit sneller dan 2ⁿ
  3. C2ⁿ groeit sneller dan n!
  4. Dn! is O(n²)

Antwoordenblad

  1. 1. A · Een eindige reeks goed gedefinieerde stappen die een probleem oplost
  2. 2. D · O(n)
  3. 3. D · O(n²)
  4. 4. A · O(mn)
  5. 5. B · O(n²)
  6. 6. D · Het algoritme van Dijkstra
  7. 7. D · Θ(n log² n)
  8. 8. B · n! groeit sneller dan 2ⁿ

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