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 notatie beschrijft een bovengrens voor de groei?

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

Hoe heet groei van O(2ⁿ)?

  1. ALineair
  2. BPolynomiaal
  3. CExponentieel
  4. DLogaritmisch
3.Makkelijk

Wat vereist binair zoeken van de invoer?

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

Met munten van 1, 3 en 4 en een bedrag van 6: hoeveel munten gebruikt de gulzige methode "grootste munt eerst", vergeleken met het optimum?

  1. AGulzig gebruikt 3 munten; het optimum is 2
  2. BGulzig gebruikt 4 munten; het optimum is 3
  3. CGulzig gebruikt 3 munten; het optimum is 3
  4. DGulzig gebruikt 2 munten; het optimum is 2
5.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 gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
  3. CInsertion sort is in het slechtste geval O(n log n)
  4. DRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
6.Gemiddeld

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

  1. AO(n + k)
  2. BO(n log n + k log n)
  3. CO(k n log n)
  4. DO(nk)
7.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. CHet stopprobleem zou beslisbaar worden
  4. DElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
8.Moeilijk

Waarom kan het algoritme van Dijkstra verkeerde resultaten geven als sommige kantgewichten negatief zijn?

  1. AHet werkt alleen op ongerichte grafen
  2. BEen knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven
  3. CHet raakt bij elke negatieve kant in een oneindige lus
  4. DNegatieve getallen kunnen niet in een prioriteitswachtrij worden opgeslagen

Antwoordenblad

  1. 1. D · Grote O (Big O)
  2. 2. C · Exponentieel
  3. 3. C · De array moet gesorteerd zijn
  4. 4. A · Gulzig gebruikt 3 munten; het optimum is 2
  5. 5. A · Insertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
  6. 6. B · O(n log n + k log n)
  7. 7. D · Elk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
  8. 8. B · Een knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven

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