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

Hoe werkt selection sort?

  1. AHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
  2. BHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan
  3. CHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  4. DHet splitst de array in helften en voegt die samen
2.Makkelijk

Welke notatie beschrijft een ondergrens voor de groei?

  1. AΘ (grote theta)
  2. BΩ (grote omega)
  3. Co (kleine o)
  4. DO (grote O)
3.Makkelijk

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

  1. AQuicksort
  2. BMergesort
  3. CBubblesort
  4. DInsertion sort
4.Gemiddeld

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

  1. AAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet
  2. BLogaritmen worden altijd afgerond op gehele getallen
  3. CHet grondtal doet er alleen toe voor kleine n
  4. DLogaritmen met verschillende grondtallen verschillen alleen een constante factor
5.Gemiddeld

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

  1. ABellman-Ford is in alle gevallen vereist
  2. BDiepte-eerst zoeken (DFS)
  3. CHet algoritme van Dijkstra
  4. DHet algoritme van Kruskal
6.Gemiddeld

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

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

Als je beide eindpunten van elke kant in een maximale koppeling neemt, krijg je een knoopoverdekking. Hoe goed is deze overdekking?

  1. AHoogstens twee keer zo groot als een minimale knoopoverdekking
  2. BHoogstens log n keer het minimum
  3. CVan onbekende kwaliteit vergeleken met het optimum
  4. DAltijd een minimale knoopoverdekking
8.Moeilijk

Welke bewering over P en NP is juist?

  1. AElk probleem in P zit ook in NP
  2. BNP betekent "niet polynomiaal"
  3. COplossingen van NP-problemen kunnen niet snel worden geverifieerd
  4. DEr is bewezen dat P ≠ NP

Antwoordenblad

  1. 1. C · Het zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
  2. 2. B · Ω (grote omega)
  3. 3. A · Quicksort
  4. 4. D · Logaritmen met verschillende grondtallen verschillen alleen een constante factor
  5. 5. C · Het algoritme van Dijkstra
  6. 6. B · O(n)
  7. 7. A · Hoogstens twee keer zo groot als een minimale knoopoverdekking
  8. 8. A · Elk probleem in P zit ook in NP

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