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 verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

  1. AQuicksort
  2. BHeapsort
  3. CBubblesort
  4. DMergesort
2.Makkelijk

Wat beschrijft de average-case looptijd?

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

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

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

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

Welk sorteeralgoritme is stabiel?

  1. ASelectionsort (gangbare versie)
  2. BQuicksort (gangbare in-place-versie)
  3. CHeapsort
  4. DMergesort
7.Moeilijk

Van welk van deze vervulbaarheidsproblemen is bekend dat het in polynomiale tijd oplosbaar is?

  1. A2-SAT, waarbij elke clausule hoogstens twee literalen heeft
  2. B3-SAT, waarbij elke clausule precies drie literalen heeft
  3. CCircuitvervulbaarheid
  4. DAlgemene SAT op formules in conjunctieve normaalvorm
8.Moeilijk

Het stopprobleem (halting problem) laat zien dat:

  1. AGeen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt
  2. BSommige programma's sneller draaien op snellere computers, dus stoppen hangt van de hardware af
  3. CElk programma uiteindelijk stopt
  4. DLussen vermeden moeten worden

Antwoordenblad

  1. 1. C · Bubblesort
  2. 2. C · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  3. 3. B · O(n²)
  4. 4. D · O(1)
  5. 5. C · O(n)
  6. 6. D · Mergesort
  7. 7. A · 2-SAT, waarbij elke clausule hoogstens twee literalen heeft
  8. 8. A · Geen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt

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