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 de tijdcomplexiteit van diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

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

Wat is recursie?

  1. AEen functie die zichzelf aanroept op kleinere invoer
  2. BEen sorteermethode
  3. CEen lus die nooit eindigt
  4. DEen soort datastructuur
3.Makkelijk

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

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

De ondergrens voor sorteren op basis van vergelijkingen in het slechtste geval is:

  1. AΩ(n²)
  2. BΩ(n)
  3. CΩ(n log n)
  4. DΩ(log n)
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²)
  4. DO(n² log n)
6.Gemiddeld

Een functie voert één lus van n iteraties uit en daarna, los daarvan, nog een lus van n iteraties. Wat is de tijdcomplexiteit?

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

Wat zijn de geamortiseerde kosten van het ophogen van een binaire teller, als één ophoging veel bits kan omzetten?

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

Antwoordenblad

  1. 1. D · O(V + E)
  2. 2. A · Een functie die zichzelf aanroept op kleinere invoer
  3. 3. D · O(log n)
  4. 4. C · Ω(n log n)
  5. 5. B · O(n³)
  6. 6. A · O(n)
  7. 7. C · Het is NP-moeilijk
  8. 8. A · O(1) per ophoging

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