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 beschrijft de average-case looptijd?

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

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. AInsertion sort
  2. BBubblesort
  3. CQuicksort
  4. DMergesort
3.Makkelijk

Wat is log₂ 1024?

  1. A12
  2. B512
  3. C10
  4. D32
4.Gemiddeld

Wat is de tijdcomplexiteit van: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Welk sorteeralgoritme is stabiel?

  1. AMergesort
  2. BHeapsort
  3. CSelectionsort (gangbare versie)
  4. DQuicksort (gangbare in-place-versie)
6.Gemiddeld

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

  1. AEen array die al gesorteerd is
  2. BEen array waarvan alle elementen verschillend zijn
  3. CEen array in willekeurige volgorde
  4. DEen array van lengte 2
7.Moeilijk

Hoe verhouden n! en 2ⁿ zich voor grote n?

  1. AZe groeien even snel
  2. B2ⁿ groeit sneller dan n!
  3. Cn! is O(n²)
  4. Dn! groeit sneller dan 2ⁿ
8.Moeilijk

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

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

Antwoordenblad

  1. 1. D · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  2. 2. C · Quicksort
  3. 3. C · 10
  4. 4. D · O(n log n)
  5. 5. A · Mergesort
  6. 6. A · Een array die al gesorteerd is
  7. 7. D · n! groeit sneller dan 2ⁿ
  8. 8. C · 2-SAT, waarbij elke clausule hoogstens twee literalen heeft

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