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 tijd voor een invoer van gemiddelde lengte
  2. BDe verwachte tijd over een gegeven verdeling van invoeren van grootte n
  3. CDe tijd op de meest gebruikte computer
  4. DDe middelste waarde tussen de looptijden in het beste en het slechtste geval
2.Makkelijk

Welke notatie beschrijft een bovengrens voor de groei?

  1. AGrote Theta (Big Theta)
  2. BKleine omega (little omega)
  3. CGrote O (Big O)
  4. DGrote Omega (Big Omega)
3.Makkelijk

Een element in een array via de index benaderen kost:

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

Een gretig (greedy) algoritme:

  1. AGebruikt alleen recursie
  2. BGeeft altijd de optimale oplossing
  3. CProbeert elke mogelijke oplossing
  4. DMaakt bij elke stap de lokaal beste keuze
5.Gemiddeld

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

  1. AEen array in willekeurige volgorde
  2. BEen array van lengte 2
  3. CEen array die al gesorteerd is
  4. DEen array waarvan alle elementen verschillend zijn
6.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 is in het slechtste geval O(n log n)
  3. CInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
  4. DRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
7.Moeilijk

Welke techniek geeft quicksort een verwachte looptijd van O(n log n) voor elke invoer?

  1. ADe pivot uniform willekeurig kiezen
  2. BAltijd het eerste element kiezen
  3. CAlleen recursie aan de linkerkant gebruiken
  4. DDe invoer sorteren voordat je quicksort uitvoert
8.Moeilijk

Wat zou er volgen als iemand een algoritme in polynomiale tijd vond voor één NP-volledig probleem?

  1. AAlleen dat ene probleem zou naar P verhuizen
  2. BAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen
  3. CElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
  4. DHet stopprobleem zou beslisbaar worden

Antwoordenblad

  1. 1. B · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  2. 2. C · Grote O (Big O)
  3. 3. D · O(1)
  4. 4. D · Maakt bij elke stap de lokaal beste keuze
  5. 5. C · Een array die al gesorteerd is
  6. 6. A · Insertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  7. 7. A · De pivot uniform willekeurig kiezen
  8. 8. C · Elk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP

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