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 betekent het als een bewerking in O(1) tijd loopt?

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

Wat zijn de drie stappen van een verdeel-en-heersalgoritme?

  1. AVerdelen, oplossen (heersen), combineren
  2. BRaden, controleren, herhalen
  3. CSorteren, zoeken, teruggeven
  4. DLezen, berekenen, schrijven
3.Makkelijk

Een O(n)-algoritme doet 3 seconden over n = 1 miljoen. Hoe lang doet het ongeveer over n = 2 miljoen?

  1. A3 seconden
  2. B9 seconden
  3. C6 seconden
  4. D12 seconden
4.Gemiddeld

Welke gulzige regel geeft bij het activiteitenselectieprobleem altijd een maximaal aantal niet-overlappende activiteiten?

  1. AKies eerst de kortste activiteit
  2. BKies de activiteit die het vroegst begint
  3. CKies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  4. DKies eerst de activiteit met de minste overlappingen en herhaal dat met de compatibele activiteiten
5.Gemiddeld

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

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

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

  1. AHet algoritme van Kruskal
  2. BHet algoritme van Dijkstra
  3. CBellman-Ford is in alle gevallen vereist
  4. DDiepte-eerst zoeken (DFS)
7.Moeilijk

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

  1. ABinair zoeken heeft minstens twee keer zoveel geheugen nodig
  2. BHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  3. CGelinkte lijsten kunnen niet worden gesorteerd
  4. DVergelijkingen op knopen van een gelinkte lijst zijn trager
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. BHet stopprobleem zou beslisbaar worden
  3. CAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen
  4. DElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP

Antwoordenblad

  1. 1. C · De looptijd groeit niet met de invoergrootte
  2. 2. A · Verdelen, oplossen (heersen), combineren
  3. 3. C · 6 seconden
  4. 4. C · Kies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  5. 5. B · O(n)
  6. 6. B · Het algoritme van Dijkstra
  7. 7. B · Het middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
  8. 8. D · Elk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP

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