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

Welke ontwerpstrategie gebruikt mergesort?

  1. AVerdeel en heers
  2. BDynamisch programmeren
  3. CBrute kracht
  4. DGulzige keuze (greedy)
2.Makkelijk

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

Wat vereist binair zoeken van de invoer?

  1. ADe array mag niet meer dan 1000 elementen hebben
  2. BDe array moet gesorteerd zijn
  3. CDe array mag alleen positieve getallen bevatten
  4. DDe lengte van de array moet een macht van twee zijn
4.Gemiddeld

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

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

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

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

  1. AO(n)
  2. BO(n³)
  3. CO(n²)
  4. DO(n log n)
7.Moeilijk

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

  1. A3-SAT, waarbij elke clausule precies drie literalen heeft
  2. BAlgemene SAT op formules in conjunctieve normaalvorm
  3. CCircuitvervulbaarheid
  4. D2-SAT, waarbij elke clausule hoogstens twee literalen heeft
8.Moeilijk

Wat is de looptijd van het algoritme van Dijkstra met een binaire heap op een graaf met V knopen en E kanten?

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

Antwoordenblad

  1. 1. A · Verdeel en heers
  2. 2. A · O(n)
  3. 3. B · De array moet gesorteerd zijn
  4. 4. D · Kies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
  5. 5. A · O(n log n)
  6. 6. C · O(n²)
  7. 7. D · 2-SAT, waarbij elke clausule hoogstens twee literalen heeft
  8. 8. C · O((V + E) log V)

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