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

Welke notatie beschrijft een ondergrens voor de groei?

  1. AΘ (grote theta)
  2. BΩ (grote omega)
  3. CO (grote O)
  4. Do (kleine o)
2.Makkelijk

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

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

Wat is een brute-force-algoritme?

  1. AEen algoritme dat op veel processoren draait
  2. BEen algoritme dat alle mogelijke kandidaatoplossingen probeert
  3. CEen algoritme dat altijd recursie gebruikt
  4. DEen algoritme dat willekeurig een antwoord raadt
4.Gemiddeld

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

  1. AKortste paden in grafen met negatieve kantgewichten
  2. BDe minimaal opspannende boom
  3. CKortste paden in aantal kanten vanaf de startknoop
  4. DEen topologische volgorde in alle grafen
5.Gemiddeld

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

  1. AAlleen willekeurige invoer
  2. BOverlappende deelproblemen en optimale substructuur
  3. CHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
  4. DEén enkele lus
6.Gemiddeld

Ongeveer hoeveel vergelijkingen heeft binair zoeken in het slechtste geval nodig in een gesorteerde array van 1,000,000 elementen?

  1. AOngeveer 20
  2. BOngeveer 500,000
  3. COngeveer 100
  4. DOngeveer 1,000
7.Moeilijk

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

  1. ANee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
  2. BJa, maar alleen voor arrays korter dan 100
  3. CJa, de ondergrens is dus fout
  4. DNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
8.Moeilijk

Hoe detecteert het algoritme van Bellman-Ford een cykel met negatief gewicht die vanuit de bron bereikbaar is?

  1. AHet voert het algoritme van Dijkstra twee keer uit en vergelijkt de twee afstandsresultaten
  2. BNa V − 1 rondes controleert het of er nog een kant kan worden gerelaxeerd
  3. CHet telt de cykels met diepte-eerst zoeken
  4. DHet controleert of er een kant met negatief gewicht is

Antwoordenblad

  1. 1. B · Ω (grote omega)
  2. 2. C · O(n)
  3. 3. B · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  4. 4. C · Kortste paden in aantal kanten vanaf de startknoop
  5. 5. B · Overlappende deelproblemen en optimale substructuur
  6. 6. A · Ongeveer 20
  7. 7. D · Nee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
  8. 8. B · Na V − 1 rondes controleert het of er nog een kant kan worden gerelaxeerd

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