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 het basisgeval van een recursieve functie?

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

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

  1. AOngeveer n²
  2. BOngeveer n / 2
  3. COngeveer n
  4. DOngeveer log₂ n
3.Makkelijk

Hoe heet groei van O(2ⁿ)?

  1. ALineair
  2. BExponentieel
  3. CPolynomiaal
  4. DLogaritmisch
4.Gemiddeld

Een gretig (greedy) algoritme:

  1. AGeeft altijd de optimale oplossing
  2. BMaakt bij elke stap de lokaal beste keuze
  3. CProbeert elke mogelijke oplossing
  4. DGebruikt alleen recursie
5.Gemiddeld

Welke gulzige regel geeft bij het activiteitenselectieprobleem altijd een maximaal aantal niet-overlappende activiteiten?

  1. AKies eerst de kortste activiteit
  2. BKies eerst de activiteit met de minste overlappingen en herhaal dat met de compatibele activiteiten
  3. CKies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  4. DKies de activiteit die het vroegst begint
6.Gemiddeld

Welk sorteeralgoritme is stabiel?

  1. AMergesort
  2. BSelectionsort (gangbare versie)
  3. CHeapsort
  4. DQuicksort (gangbare in-place-versie)
7.Moeilijk

Zit 22n in O(2ⁿ)?

  1. AJa, want constante factoren in de exponent worden in grote O altijd genegeerd
  2. BNee, want 22n groeit langzamer dan 2ⁿ
  3. CNee, want 22n = 4ⁿ en 4ⁿ / 2ⁿ = 2ⁿ groeit onbegrensd
  4. DJa, want beide zijn exponentieel
8.Moeilijk

Welke definitie van de klasse NP is juist?

  1. AProblemen die geen enkel algoritme kan oplossen
  2. BProblemen die niet polynomiaal zijn
  3. CProblemen die niet in polynomiale tijd kunnen worden opgelost
  4. DBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd

Antwoordenblad

  1. 1. D · Een geval dat direct wordt beantwoord zonder nog een recursieve aanroep
  2. 2. D · Ongeveer log₂ n
  3. 3. B · Exponentieel
  4. 4. B · Maakt bij elke stap de lokaal beste keuze
  5. 5. C · Kies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  6. 6. A · Mergesort
  7. 7. C · Nee, want 22n = 4ⁿ en 4ⁿ / 2ⁿ = 2ⁿ groeit onbegrensd
  8. 8. D · Beslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd

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