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

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. AMergesort
  2. BInsertion sort
  3. CBubblesort
  4. DQuicksort
2.Makkelijk

Wat is het basisgeval van een recursieve functie?

  1. AEen geval dat direct wordt beantwoord zonder nog een recursieve aanroep
  2. BHet geval met de grootste invoer, dat vóór alle recursieve aanroepen wordt afgehandeld
  3. CDe eerste regel van de functie
  4. DDe aanroep die het meeste geheugen gebruikt
3.Makkelijk

Hoe werkt selection sort?

  1. AHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan
  2. BHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  3. CHet splitst de array in helften en voegt die samen
  4. DHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
4.Gemiddeld

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

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

Wat meet geamortiseerde analyse?

  1. ADe verwachte kosten over willekeurige invoer
  2. BDe kosten van de ene duurste bewerking ergens in de reeks
  3. CDe kosten van een algoritme bij de beste invoer
  4. DDe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
6.Gemiddeld

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

  1. AHet algoritme van Kruskal
  2. BBellman-Ford is in alle gevallen vereist
  3. CHet algoritme van Dijkstra
  4. DDiepte-eerst zoeken (DFS)
7.Moeilijk

Welke definitie van de klasse NP is juist?

  1. ABeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
  2. BProblemen die geen enkel algoritme kan oplossen
  3. CProblemen die niet polynomiaal zijn
  4. DProblemen die niet in polynomiale tijd kunnen worden opgelost
8.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 NP-moeilijk
  2. BHet is onbeslisbaar
  3. CHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten
  4. DHet is altijd oplosbaar in O(V + E)

Antwoordenblad

  1. 1. D · Quicksort
  2. 2. A · Een geval dat direct wordt beantwoord zonder nog een recursieve aanroep
  3. 3. B · Het zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  4. 4. A · Ongeveer log₂ n
  5. 5. D · De gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
  6. 6. C · Het algoritme van Dijkstra
  7. 7. A · Beslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
  8. 8. A · Het is NP-moeilijk

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