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

Hoe heet groei van O(2ⁿ)?

  1. ALineair
  2. BPolynomiaal
  3. CExponentieel
  4. DLogaritmisch
2.Makkelijk

Wat is het basisgeval van een recursieve functie?

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

Wat beschrijft de average-case looptijd?

  1. ADe middelste waarde tussen de looptijden in het beste en het slechtste geval
  2. BDe verwachte tijd over een gegeven verdeling van invoeren van grootte n
  3. CDe tijd voor een invoer van gemiddelde lengte
  4. DDe tijd op de meest gebruikte computer
4.Gemiddeld

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

  1. AHet grondtal doet er alleen toe voor kleine n
  2. BLogaritmen worden altijd afgerond op gehele getallen
  3. CLogaritmen met verschillende grondtallen verschillen alleen een constante factor
  4. DAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet
5.Gemiddeld

Wat is de oplossing van de recurrente betrekking T(n) = T(n − 1) + O(n)?

  1. AO(2ⁿ)
  2. BO(n²)
  3. CO(n log n)
  4. DO(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(log n)
  3. CO(n²)
  4. DO(2ⁿ)
7.Moeilijk

Waarom is een opzoeking in een hashtabel gemiddeld O(1) maar in het slechtste geval O(n)?

  1. AVeel sleutels kunnen in dezelfde bucket botsen
  2. BHashfuncties zijn traag
  3. CSleutels moeten eerst gesorteerd worden
  4. DArrays hebben O(n) toegang
8.Moeilijk

Het 0/1-knapzakprobleem opgelost met dynamisch programmeren kost O(nW) tijd. Waarom heet dit pseudo-polynomiaal?

  1. AOmdat het algoritme gerandomiseerd is en de looptijd per invoer verschilt
  2. BW is een getal, dus de tijd is exponentieel in het aantal bits waarmee W wordt genoteerd
  3. COmdat het alleen werkt voor W = 0
  4. DOmdat n altijd klein is

Antwoordenblad

  1. 1. C · Exponentieel
  2. 2. C · Een geval dat direct wordt beantwoord zonder nog een recursieve aanroep
  3. 3. B · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  4. 4. C · Logaritmen met verschillende grondtallen verschillen alleen een constante factor
  5. 5. B · O(n²)
  6. 6. A · O(n)
  7. 7. A · Veel sleutels kunnen in dezelfde bucket botsen
  8. 8. B · W is een getal, dus de tijd is exponentieel in het aantal bits waarmee W wordt genoteerd

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