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. AExponentieel
  2. BPolynomiaal
  3. CLogaritmisch
  4. DLineair
2.Makkelijk

Een probleem heet meestal handelbaar (tractable) als:

  1. AHet geen oplossing heeft
  2. BHet in constante tijd kan worden opgelost
  3. CHet alleen kan worden opgelost door elke mogelijkheid te proberen
  4. DHet in polynomiale tijd kan worden opgelost
3.Makkelijk

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

  1. AHeapsort
  2. BMergesort
  3. CBubblesort
  4. DQuicksort
4.Gemiddeld

Ongeveer hoeveel vergelijkingen heeft binair zoeken in het slechtste geval nodig in een gesorteerde array van 1,000,000 elementen?

  1. AOngeveer 20
  2. BOngeveer 100
  3. COngeveer 1,000
  4. DOngeveer 500,000
5.Gemiddeld

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V³ × E)
6.Gemiddeld

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

  1. AJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  2. BNee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
  3. CNee, omdat n³ voor grote n kleiner is dan n²
  4. DJa, maar alleen als n kleiner is dan 100
7.Moeilijk

Wat is de tijdcomplexiteit van: for i = 1 to n: for (j = i; j ≤ n; j = j + i) doe O(1) werk?

  1. AO(n log n)
  2. BO(n²)
  3. CO(n √n)
  4. DO(n)
8.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. BAlgemene SAT op formules in conjunctieve normaalvorm
  3. CCircuitvervulbaarheid
  4. D3-SAT, waarbij elke clausule precies drie literalen heeft

Antwoordenblad

  1. 1. A · Exponentieel
  2. 2. D · Het in polynomiale tijd kan worden opgelost
  3. 3. C · Bubblesort
  4. 4. A · Ongeveer 20
  5. 5. A · O(V × E)
  6. 6. A · Ja, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  7. 7. A · O(n log n)
  8. 8. A · 2-SAT, waarbij elke clausule hoogstens twee literalen heeft

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