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 memoisatie?

  1. ACommentaar schrijven naast elke regel code
  2. BRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
  3. CGeheugen vrijgeven nadat een functie is teruggekeerd
  4. DResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
2.Makkelijk

De looptijd van een algoritme is O(n). Hoe heet deze groei?

  1. ALineair
  2. BConstant
  3. CLogaritmisch
  4. DKwadratisch
3.Makkelijk

Wat is een brute-force-algoritme?

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

Wat meet geamortiseerde analyse?

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

  1. ANee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
  2. BJa, maar alleen als n kleiner is dan 100
  3. CJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  4. DNee, omdat n³ voor grote n kleiner is dan n²
6.Gemiddeld

Wat is de tijdcomplexiteit van het berekenen van het n-de Fibonaccigetal met een bottom-uptabel?

  1. AO(log n)
  2. BO(n)
  3. CO(2ⁿ)
  4. DO(n²)
7.Moeilijk

Waarom heeft elke zoekmethode op basis van vergelijkingen in een gesorteerde array in het slechtste geval Ω(log n) vergelijkingen nodig?

  1. AEen beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
  2. BElk element moet minstens één keer worden vergeleken
  3. CElke vergelijking kost logaritmische tijd
  4. DBinair zoeken is het enige mogelijke algoritme en heeft log₂ n vergelijkingen nodig
8.Moeilijk

Een probleem is NP-volledig als het:

  1. AIn polynomiale tijd oplosbaar is
  2. BIn NP zit en elk NP-probleem er in polynomiale tijd naar te reduceren is
  3. COnmogelijk op te lossen is
  4. DBuiten NP valt maar moeilijker is dan alle NP-problemen, zoals het stopprobleem

Antwoordenblad

  1. 1. D · Resultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
  2. 2. A · Lineair
  3. 3. A · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  4. 4. B · De gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
  5. 5. C · Ja, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  6. 6. B · O(n)
  7. 7. A · Een beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
  8. 8. B · In NP zit en elk NP-probleem er in polynomiale tijd naar te reduceren is

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