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

  1. AEen soort datastructuur
  2. BEen sorteermethode
  3. CEen functie die zichzelf aanroept op kleinere invoer
  4. DEen lus die nooit eindigt
2.Makkelijk

Wat betekent het als een bewerking in O(1) tijd loopt?

  1. AHet kan maar één keer worden uitgevoerd
  2. BHet verwerkt precies één element per seconde looptijd
  3. CHet duurt altijd precies één seconde
  4. DDe looptijd groeit niet met de invoergrootte
3.Makkelijk

Wat is een brute-force-algoritme?

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

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

  1. AO(n²)
  2. BO(n)
  3. CO(2ⁿ)
  4. DO(n log n)
5.Gemiddeld

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

  1. AInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  2. BInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
  3. CInsertion sort is in het slechtste geval O(n log n)
  4. DRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
6.Gemiddeld

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

  1. AMergesort is al O(n)
  2. BMergesort heeft geen recursieve structuur
  3. CDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
  4. DDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
7.Moeilijk

Hoe wordt het handelsreizigersprobleem geclassificeerd?

  1. ADe beslissingsversie zit in P, maar de optimalisatieversie is NP-volledig
  2. BDe beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
  3. CHet is onbeslisbaar
  4. DHet zit in P, omdat het algoritme van Dijkstra het oplost door elke stad één keer te bezoeken
8.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. AJa, maar alleen voor arrays korter dan 100
  2. BNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
  3. CJa, de ondergrens is dus fout
  4. DNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer

Antwoordenblad

  1. 1. C · Een functie die zichzelf aanroept op kleinere invoer
  2. 2. D · De looptijd groeit niet met de invoergrootte
  3. 3. D · Een algoritme dat alle mogelijke kandidaatoplossingen probeert
  4. 4. C · O(2ⁿ)
  5. 5. A · Insertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  6. 6. D · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  7. 7. B · De beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
  8. 8. D · Nee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer

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