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

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. C12 seconden
  4. D6 seconden
2.Makkelijk

Wat is de grote O van 3n² + 5n + 2?

  1. AO(5n)
  2. BO(n²)
  3. CO(n³)
  4. DO(3n²)
3.Makkelijk

Welke ontwerpstrategie gebruikt mergesort?

  1. ADynamisch programmeren
  2. BBrute kracht
  3. CGulzige keuze (greedy)
  4. DVerdeel en heers
4.Gemiddeld

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

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

  1. AEén enkele lus
  2. BOverlappende deelproblemen en optimale substructuur
  3. CHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
  4. DAlleen willekeurige invoer
6.Gemiddeld

Welk sorteeralgoritme is stabiel?

  1. AMergesort
  2. BQuicksort (gangbare in-place-versie)
  3. CSelectionsort (gangbare versie)
  4. DHeapsort
7.Moeilijk

Wat is de tijdcomplexiteit van het opbouwen van een binaire heap uit n ongesorteerde elementen met de bottom-upmethode?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(n log n)
8.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. BVergelijkingen op knopen van een gelinkte lijst zijn trager
  3. CGelinkte lijsten kunnen niet worden gesorteerd
  4. DHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is

Antwoordenblad

  1. 1. D · 6 seconden
  2. 2. B · O(n²)
  3. 3. D · Verdeel en heers
  4. 4. A · Kies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  5. 5. B · Overlappende deelproblemen en optimale substructuur
  6. 6. A · Mergesort
  7. 7. B · O(n)
  8. 8. D · Het middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is

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